Given two digits, why are there are $ 2^n \minus{} 2$ ways to arrange them in an $ n$-digit number?

It sort of looks like considering if the two digits where the two digits in base 2 but I understand why we subtract 2 from that.

Original Problem
http://www.artofproblemsolving.com/Wiki/index.php/2004_AIME_II_Problems/Problem_4

It's because the solution considers the separate cases of (1) all the digits are the same number (2) all the digits are one of two [i]distinct[/i] numbers. There are $ 2^n$ ways to arrange two digits in a number with $ n$ digits, but we have to subtract $ 2$ to take care of the two numbers which are just all the same number, namely $ \underbrace{\overline{AAAA\cdots A}}_{n\, \text{digits}}, \underbrace{\overline{BBBB \cdots B}}_{n\, \text{digits}}$.

The reason why the solution splits it into these cases is to easily handle the case when one of the two numbers is $ 0$.


algebra
polynomial
calculus
derivative
geometric sequence
calculus computations

maclaurin' series,HELP!                                                                  -kh
our assignment is about atmospheric pressue using the term p = A e                                        -kh
we've gone through arithmetical and geometric progression then through the power series for e
But,the next task is "using Maclaurin's Theorem,obtain
                                 -kh                                              3
the power series for e         up to and including the term h

PLEASE HELP,Thanks,Stuart.

Maybe they want $ Ae^{\minus{}kh}\equal{}\sum_{n\equal{}0}^{\infty}A\frac{(\minus{}k)^nh^n}{n!}$.  :maybe:

Which, for small $ h,$ is $ A\minus{}Akh\plus{}$ (smaller terms).

(That's what "up to and including the term h" probably means.)

[quote="watford73"]hi,is it not something along the lines of e to the power of -kh = f(0) -f ' + kh 2 / 2! or something?[/quote]

You're thinking of a maclaurin polynomial in the form:

$ f(x) \equal{} f(0) \plus{} \frac {f'(0)x}{1!} \plus{} \frac {f''(0)x^{2}}{2!} \plus{} \frac {f'''(0)x^{3}}{3!} \plus{} \cdots \plus{} \frac {f^{(n)}(0)x^{n}}{n!}$

but for $ e^{x}$ we have $ (e^{x})^{(n)} \equal{} e^{x}$ (for all $ n \in \mathbb{N}$) which is 1 at $ x \equal{} 0$, thus

$ e^{x} \equal{} 1 \plus{} x \plus{} \frac {x^{2}}{2} \plus{} \frac {x^{3}}{6} \plus{} \frac {x^{4}}{24} \plus{} \cdots \plus{} \frac {x^{n}}{n!}$

$ e^{ \minus{} kh} \equal{} 1 \minus{} kh \plus{} \frac {k^{2}h^{2}}{2} \minus{} \frac {k^{3}h^{3}}{6} \plus{} \frac {k^{4}h^{4}}{24} \minus{} \cdots \plus{} \frac {k^{n}h^{n}}{n!}$

$ Ae^{ \minus{} kh} \equal{} A \minus{} Akh \plus{} \frac {Ak^{2}h^{2}}{2} \minus{} \frac {Ak^{3}h^{3}}{6} \plus{} \frac {Ak^{4}h^{4}}{24} \minus{} \cdots \plus{} \frac {Ak^{n}h^{n}}{n!}$

Hi, I was on before about Maclaurins series and polynominals, the answer I gratefully received was;

e –kh = 1 – kh + k2 h2 / 2! – k3 h3 / 3!  Etc..

this is what I’m looking for, however I have to show how I got this through the process of differentiation,do you multiply through by k? or kh?
 I have to show this process by
f(x)=e-kh  so,

f(0)=1

f‘(0)x=-kh

f’’(0)= ?? or is it f’’(0)/2!=???

help! It’s gotta be in for Thursday, thanks for your time..

Substitute $ x$ by $ \minus{}kh$. Then notice that for every even exponent, the term will be positive while for every odd exponent, the term will be negative.

prime, you've gotta break it down a little more simple than that! do we multiply through by k? is e to the -kh constant? when should we bring in the polynominal??


parameterization
geometry
geometric transformation
integration
induction
calculus
probability and stats

Similar to [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=174061]this problem involving two random variables with exponential distribution.[/url]

Let $ E_1, E_2, \ldots, E_n$ be iid random variables with exponential distribution of the same parameter $ \lambda > 0$. Let $ F_1 \le F_2 \le \ldots \le F_n$ be the ordering of $ E_1, E_2, \ldots, E_n$, i.e. $ F_1$ is the smallest value among $ E_1, E_2, \ldots, E_n$. $ F_2$ is the second smallest and so on.

Prove that the $ n$ spacings $ F_1, F_2 \minus{} F_1, F_3 \minus{} F_2, \ldots, F_n \minus{} F_{n\minus{}1}$ are independent random variables with exponential distribution with parameters $ n\lambda, (n\minus{}1)\lambda, \ldots, \lambda$.

(It is sufficient to show that \[ P( F_1 \ge b_1, F_2 \minus{} F_1 \ge b_2 , \ldots , F_n \minus{} F_{n\minus{}1} \ge b_{n})\] \[ \equal{} \exp[\minus{}\lambda(n b_1 \plus{} (n\minus{}1) b_2 \plus{} \ldots \plus{} b_{n})]\] for all $ b_1 \ge 0 , \ldots , b_{n} \ge 0$)

A very close relative of a question I like to ask people: how long will it take, on average, for every single atom of a sample of a radioisotope to decay?

First approach (Bijection method)

Rearrange $ n b_1 \plus{} (n \minus{} 1) b_2 \plus{} \ldots \plus{} b_{n}$ to get $ c_1 \plus{} c_2 \plus{} \ldots \plus{} c_n$ where $ c_i \equal{} \sum_1^i b_k$ to realize that it suffices to show that the two events $ A: \equal{} (F_1 \ge b_1, F_2 \minus{} F_1 \ge b_2 , \ldots , F_n \minus{} F_{n \minus{} 1} \ge b_{n})$ and $ B: \equal{} (E_1 \ge c_1, E_2 \ge c_2, \ldots, E_n \ge c_n)$ have the same probability. These two events looks like somehow connected.

Let's try $ n \equal{} 2$ case first. Draw the two regions in the plane corresponding to the two events $ A$ and $ B$. (Let $ A' \subset \mathbb{R}^2$ be the set of all values of $ (E_1, E_2)$ that makes $ A$ happen. Define $ B'$ similarly. Compare the regions $ A'$ and $ B'$). $ A'$ consists of two connected pieces and we notice that if we move the lower piece and attach it to the upper piece we get $ B'$. We have a transformation $ T$ from $ A'$ to $ B'$ : $ T(x_1,x_2) \equal{} (x_1,x_2)$ if $ x_1 < x_2$ and $ T(x_1,x_2) \equal{} (x_1 \minus{} b_2, x_2 \plus{} b_2)$ if $ x_1 > x_2$. Since $ T$ is a piece-wise translation that preserves $ x_1 \plus{} x_2$, we have \[ P(A) \equal{} \int_{A'} \lambda^2 \exp( \minus{} \lambda(x_1 \plus{} x_2)) dx_1 dx_2 \equal{} \int_{B'} \lambda^2 \exp( \minus{} \lambda(x_1 \plus{} x_2)) dx_1 dx_2 \equal{} P(B)\].

To generalize the above argument to all $ n$ (higher dimensions), we hope we can find a piece-wise translation $ T: A' \to B'$ that preserves $ x_1 \plus{} \ldots \plus{} x_n$ and is a bijection (up to null sets) and can be described as a combinatorial operation on the sequence $ (x_1, \ldots , x_n) \in A'$ (as opposed to that $ T$ is described geometrically : "move this 100-dimensional piece to there and move that 100-dimensional piece to here ...")

If $ (x_i)_1^n$ is in $ A'$, there is a permutation $ \pi$ (depending on $ (x_i)_1^n$) such that $ (x_{\pi(i)})_1^n$ is an increasing sequence with jumps lower bounds $ (b_i)_1^n$. Write $ x_{\pi(i)} \equal{} c_i \plus{} d_i$ so that $ (d_i)_1^n$ is a non-negative increasing sequence. Define $ T(x) \equal{} y$ where $ y_i \equal{} c_i \plus{} d_{\pi^{ \minus{} 1}(i)}$. $ y$ is in $ B'$ and $ (y \minus{} c)_{\pi(i)}$ is increasing. This $ T$ is an invertible piece-wise translation and coincides with $ n\equal{}2$ case.

Second approach (Mathematical induction)

Suppose we have $ n$ radioactive particles of the same type, each of them has exponential distribution of decay time with the same parameter $ \lambda$. The time $ F_1$ it takes for a decay to occur among the given $ n$ particles has exponential distribution with parameter $ n \lambda$. The remaining $ n \minus{} 1$ particles are not affected and they are memoryless so we proceed with mathematical induction on the number of particles. This is an intuitive argument but not a real proof.

To make a real proof out of the argument, we need to either use the concept of conditional expectation or imitate the argument with a direct calculation of distributions. The former way, i don't know how to do it. The latter way, wlog assume $ \lambda \equal{} 1$ and suppose what we want to prove is true for $ n \minus{} 1$ particles, define $ R_n(b_1, \ldots, b_n)$ as the set of all $ (x_1, \ldots, x_n)$ such that $ y_1 \ge b_1, y_2 \minus{} y_1 \ge b_2, \ldots, y_n \minus{} y_{n \minus{} 1} \ge b_n$ where $ y_1 \le \ldots \le y_n$ are the ordering of $ x_1,\ldots,x_n$.

Consider
\[ \int_{R_n(b_1,\ldots,b_n)} e^{ \minus{} x_1 \minus{} \ldots \minus{} x_n} dx_1 \ldots dx_n
\]
If $ (x_1, \ldots, x_n)$ is in $ R_n(b_1,\ldots,b_n)$ and if we assume wlog that $ x_1$ is the smallest among $ x_1, \ldots, x_n$ then $ (x_2, \ldots, x_n)$ is in $ R_{n \minus{} 1}(x_1 \plus{} b_2, b_3, \ldots, b_n)$. Conditionalize on $ x_1$ to reduce the above integral to $ n \minus{} 1$ particles case, the above integral is equal to
\[ n \int_{b_1}^\infty e^{ \minus{} x_1} \int_{(x_2, \ldots, x_n)\in R_{n \minus{} 1}(x_1 \plus{} b_2, b_3, \ldots, b_n)} e^{ \minus{} x_2 \minus{} \ldots \minus{} x_n} dx_2 \ldots dx_n \, dx_1
\]


Let be $ a\ge b\ge c>0$ . Show that :

$ \frac{a^2\minus{}b^2}{c}\plus{}\frac{c^2\minus{}b^2}{a}\plus{}\frac{a^2\minus{}c^2}{b}\ge 3a\minus{}4b\plus{}c$

[quote="alex2008"]Let be $ a\ge b\ge c > 0$ . Show that :

$ \frac {a^2 \minus{} b^2}{c} \plus{} \frac {c^2 \minus{} b^2}{a} \plus{} \frac {a^2 \minus{} c^2}{b}\ge 3a \minus{} 4b \plus{} c$[/quote]
We have: $ LHS \equal{} (a\minus{}b)(\frac{a\plus{}b}{c}\plus{}\frac{a\plus{}b}{b})\plus{}\frac{(b^2\minus{}c^2)(a\minus{}b)}{ab}  \ge 4(a\minus{}b) \ge 3(a\minus{}b) \ge RHS$
Then,we have Q.E.D
Equality holds when $ a\equal{}b\equal{}c$ :)


Let a, b and c positive real numbers < 1
Find maximum value of  (a-bc)(b-ca)(c-ba)

hello, we have
$ (a\minus{}bc)(b\minus{}ca)(c\minus{}ba)\le \frac{1}{64}$ and the equal sign will attained at $ a\equal{}b\equal{}c\equal{}\frac{1}{2}$.
Sonnhard.

[quote="Dr Sonnhard Graubner"]hello, we have
$ (a \minus{} bc)(b \minus{} ca)(c \minus{} ba)\le \frac {1}{64}$ and the equal sign will attained at $ a \equal{} b \equal{} c \equal{} \frac {1}{2}$.
Sonnhard.[/quote]
Let $ f(a,b,c) \equal{} (a\minus{}bc)(b\minus{}ca)(c\minus{}ba)$.
First assume that $ c\minus{}ab,b\minus{}ca,c\minus{}ab > 0$: (Else $ f(a,b,c) < 0$)
$ f(a,b,c) \le f(\sqrt{ab},\sqrt{ab},c) \iff$
$ (a\minus{}bc)(b\minus{}ca)(c\minus{}ba) \le (\sqrt{ab}\minus{}\sqrt{ab}c)(\sqrt{ab}\minus{}\sqrt{ab}c)(c\minus{}ba) \iff$
$ (a\minus{}bc)(b\minus{}ca) \equal{} ab(1\minus{}c)^2 \iff$
$ ab\minus{}b^2c\minus{}a^2c\plus{}abc^2 \le ab \minus{} 2abc \plus{} abc^2 \iff$
$ c(a\minus{}b)^2 \ge 0$
Using SMV we get $ f(a,b,c) \le f(\sqrt[3]{abc}, \sqrt[3]{abc}, \sqrt[3]{abc})$
$ f(x,x,x) \equal{} (x(1\minus{}x))^2 \le \left ( \frac{1}{4} \right )^3 \equal{} \frac{1}{64}$

[quote="kuing"][quote="Mathias_DK"][quote="Dr Sonnhard Graubner"]hello, we have
$ (a \minus{} bc)(b \minus{} ca)(c \minus{} ba)\le \frac {1}{64}$ and the equal sign will attained at $ a \equal{} b \equal{} c \equal{} \frac {1}{2}$.
Sonnhard.[/quote]
Let $ f(a,b,c) \equal{} (a \minus{} bc)(b \minus{} ca)(c \minus{} ba)$.
First assume that $ c \minus{} ab,b \minus{} ca,c \minus{} ab > 0$: (Else $ f(a,b,c) < 0$)
[/quote]

but if $ a \minus{} bc < 0,b \minus{} ca < 0,c \minus{} ab > 0$ the $ f(a,b,c)$ still $ > 0$... :maybe:[/quote]
$ a \minus{} bc,b \minus{} ca < 0 \Rightarrow a \minus{} bc \plus{} b \minus{} ca < 0 \iff (a \plus{} b) < c(a \plus{} b) \iff c > 1$ which is not possible. Hence at most one of the terms is negative.
Sorry. Didn't write it because i thought it was obvious  :oops:

[quote="Mathias_DK"][/quote][quote="kuing"][quote="Mathias_DK"][quote="Dr Sonnhard Graubner"]hello, we have
$ (a - bc)(b - ca)(c - ba)\le \frac {1}{64}$ and the equal sign will attained at $ a = b = c = \frac {1}{2}$.
Sonnhard.[/quote]
Let $ f(a,b,c) = (a - bc)(b - ca)(c - ba)$.
First assume that $ c - ab,b - ca,c - ab > 0$: (Else $ f(a,b,c) < 0$)
[/quote]

but if $ a - bc < 0,b - ca < 0,c - ab > 0$ the $ f(a,b,c)$ still $ > 0$... :maybe:[/quote][quote="Mathias_DK"]
$ a - bc,b - ca < 0 \Rightarrow a - bc + b - ca < 0 \iff (a + b) < c(a + b) \iff c > 1$ which is not possible. Hence at most one of the terms is negative.
Sorry. Didn't write it because i thought it was obvious  :oops:[/quote]

Indeed, that's obvious, at least, there are very easy to know that ... is I was not thinking clearly...  :blush:

[quote="Differ"][quote="Mathias_DK"]Using SMV we get $ f(a,b,c) \le f(\sqrt [3]{abc}, \sqrt [3]{abc}, \sqrt [3]{abc})$[/quote]

What does SMV stand for?[/quote]
Stronger Mixing Variables: http://reflections.awesomemath.org/2006_6/2006_6_mixing.pdf


function
algorithm
search
graph theory
combinatorics unsolved
combinatorics

Hey all,
i have not formally studied graph theory, but have acquired bits and pieces from here and there :oops:. i can express the problem i am dealing with in terms of finding the matching possibilites of a fully connected N-partite Equitable Graph. i need to know if there is a way to find this. i think it is just a simple permutation calculation, but would appreciate somebody with more experience commenting.
secondly, each matching gives me a solution to an objective function that i want to maximize. are there algorithms that will help me apart from doing an exhaustive search (complete enumeration) or is this the only way.

thx for any help

I wish I could answer, but my knowledge of the Graph Theory is minimal :( . I'm posting this only to ask you not to post the same message twice in the neighboring forums: they are visited by the same set of people and it doesn't improve your chances to get an answer in the slightest. So, I'm leaving your post in the Unsolved Problem section (since it seems that you do not know a solution yourself) and deleting your other identical post.  :)