# combinations of permutations?

• Nov 9th 2009, 03:52 AM
billym
combinations of permutations?
I have a string of length 14 made up of 0s, 1s, and 2s. I'm trying to find the number of strings with an odd number of 2s.

So I want to sum the number of strings I can make for each odd value $\displaystyle k$ between 1 and 14.

I can't figure out if for each odd number of 2s, i should use $\displaystyle P(12,k)$ or $\displaystyle C(12,k)$ multiplied by $\displaystyle 2^{12-k}$.

I think I should use C since I am just looking for the number of possible combinations of size k, i.e. the places where the 2's will be...

(EDIT: I meant "arghh... are these combinations or permutations?)
• Nov 9th 2009, 04:32 AM
HallsofIvy
Quote:

Originally Posted by billym
I have a string of length 14 made up of 0s, 1s, and 2s. I'm trying to find the number of strings with an odd number of 2s.

So I want to sum the number of strings I can make for each odd value $\displaystyle k$ between 1 and 14.

I can't figure out if for each odd number of 2s, i should use $\displaystyle P(12,k)$ or $\displaystyle C(12,k)$ multiplied by $\displaystyle 2^{12-k}$.

I think I should use C since I am just looking for the number of possible combinations of size k, i.e. the places where the 2's will be...

Yes, these are "combinations" since you are treating all "2"s as the same.

And, of course, the distinction between "0" and "1" is irrelevant. The number of ways you can have a string of 1 "2" and 13 "other" is $\displaystyle \left(\begin{array}{c}14 \\ 1\end{array}\right)= 14$. The number of ways you can have 3 "2"s and 11 "other" is $\displaystyle \left(\begin{array}{c}14 \\ 3\end{array}\right)$$\displaystyle = \frac{14!}{3!11!}= \frac{14(13)(12)}{6}= 364$, etc. The number of ways you can write and odd number of "2"s and fill out the remaining places with "other" is $\displaystyle \sum_{n= 0}^6 \left(\begin{array}{c}14 \\ 2n+1\end{array}\right)$.
• Nov 9th 2009, 05:24 AM
billym
I can see how the "other" spaces are irrelevant when you are finding the combinations of 2s, but aren't they relevant when you are calculating the number of... uh... "tales"?

For example, since 21111111111111 and 20000000000000 are different strings, shouldn't this work:

$\displaystyle \sum_{n= 1,3,5,...}^{13} \left(\begin{array}{c}14 \\ n\end{array}\right)2^{14-n}$
• Nov 9th 2009, 06:31 AM
Plato
Quote:

Originally Posted by billym
I can see how the "other" spaces are irrelevant when you are finding the combinations of 2s, but aren't they relevant when you are calculating the number of... uh... "tales"?

For example, since 21111111111111 and 20000000000000 are different strings, shouldn't this work:

$\displaystyle \sum_{n= 1,3,5,...}^{13} \left(\begin{array}{c}14 \\ n\end{array}\right)2^{14-n}$

Yes that works.
However, I think most of us would prefer this summation:
$\displaystyle \sum\limits_{n = 0}^6 {\binom{14}{2n+1} 2^{13 - 2n} }$
• Nov 10th 2009, 06:21 PM
awkward
Quote:

Originally Posted by billym
I have a string of length 14 made up of 0s, 1s, and 2s. I'm trying to find the number of strings with an odd number of 2s.

So I want to sum the number of strings I can make for each odd value $\displaystyle k$ between 1 and 14.

I can't figure out if for each odd number of 2s, i should use $\displaystyle P(12,k)$ or $\displaystyle C(12,k)$ multiplied by $\displaystyle 2^{12-k}$.

I think I should use C since I am just looking for the number of possible combinations of size k, i.e. the places where the 2's will be...

(EDIT: I meant "arghh... are these combinations or permutations?)

Here is an alternative approach via generating functions which is interesting because it gives the answer in a different form.

Let $\displaystyle a_r$ be the number of strings of length r composed of 0s, 1s, and 2s with an odd number of 2s, and let f be the exponential generating function (EGF) of $\displaystyle a_r$, i.e.
$\displaystyle f(x) = \sum_{r=0}^{\infty}\frac{1}{r!} a_r x^r$.

Then
$\displaystyle f(x) = (1 + x + \frac{1}{2!} x^2 + \frac{1}{3!} x^3 + \dots)^2 \; (x + \frac{1}{3!} x^3 + \frac{1}{5!} x^5 + \dots)$
$\displaystyle = (e^x)^2 \; (1/2) \; (e^x - e^{-x})$
$\displaystyle = (1/2) \; (e^{3x} - e^x)$

The answer to our problem is the coefficient of $\displaystyle \frac{1}{14!} x^{14}$ in f(x), which is
$\displaystyle (1/2) \; (3^{14} - 1)$.

More generally, the number of strings of length r is
$\displaystyle a_r = (1/2) \; (3^r - 1)$.

The simplicity of this result suggests that there should be a simple combinatorial method of obtaining it.