How many 10 digit phone numbers have at least one of each odd digit?
This is actually the same question, so I know the solution. Now I want to solve this using generating functions. I've tried several ways to generate a function but none give me the same answer as on the question posted above (7731309000).
We know there are 5 odd numbers, and we need at least one of each. So we need to pick 5 odd numbers from a collection of 5. We can pick each number 1 to 6 times (since we take each one time). This should give us the following: $$(x + x^2 + x^3 + x^4 + x^5 + x^6)^5$$
Because we have to pick it at least once we get no "$1 +$" and we can pick at most 6 of each number.
Now, for the remaining 5 numbers we can do as follows:
For each number we get: $$(1+x^2+x^3+x^4+x^5)^5$$
This means that we can pick it once, twice,.. five times, and this for each number so we raise it to the power of 5.
So we need to find the coefficient of $x^{10}$ in $$(1+x^2+x3+x^4+x^5)^5 \cdot (x + x^2 + x^3 + x^4 + x^5 + x^6)^5$$
But this doesn't give me the same answer. It tells me the coefficient of $x^{10} = 476$
Ps: I know I have to work it out much more, but I use wolfram alpha to give me the coefficient immediatly, so I know i'm on the right path or not.
As Calvin points out, you need to take order into account; so you can set up an exponential generating function:
Since we have 5 odd digits which each appear at least once, and 5 even digits which appear any number of times, we get the exponential GF $$\bigg(\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\bigg)^5\bigg(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\bigg)^5=$$ $$(e^x-1)^5(e^x)^5=e^{5x}\bigg[e^{5x}-5e^{4x}+10e^{3x}-10e^{2x}+5e^x-1\bigg]=$$ $$e^{10x}-5e^{9x}+10e^{8x}-10e^{7x}+5e^{6x}-e^{5x}=$$ $$\displaystyle\sum_{n=0}^{\infty}\bigg[\frac{(10x)^n}{n!}-5\frac{(9x)^n}{n!}+10\frac{(8x)^n}{n!}-10\frac{(7x)^n}{n!}+5\frac{(6x)^n}{n!}-\frac{(5x)^n}{n!}\bigg].$$
The coefficient of $\frac{x^{10}}{10!}$ is given by $$10^{10}-5(9^{10})+10(8^{10})-10(7^{10})+5(6^{10})-5^{10}.$$