Arrangments

[KidKat1]

How many arrangements of six 0's, five 1's, and four 2's are there in which
The first 0 precedes the first 1, which precedes the first 2?

I tried to break this problem down into a problem where you could use the addition principle, but there are just too many cases. I not really sure where to go, the only thing that I can think is that only 0's can come before the first 1 and only 0's and 1's can come before the first 2. But I'm not sure how that can help. Any Ideas would be helpful. Thanks!

 

[galactus]

We can construct the various cases and sum them up.

We have 15 digits of zeros, ones, and twos.

Place a 0 first and then arrange 14 digits.

Different cases:

After placing the 0, place a 1, then a 01, then a 001, etc.

So, we have: \(\displaystyle \L\\\underbrace{\frac{13!}{5!4!4!}}_{\text{5-0's, 4-1's, 4-2's}}+\overbrace{\frac{12!}{4!4!4!}}^{\text{4-0's,4-1's4-2's}}+\underbrace{\frac{11!}{3!4!4!}}_{\text{3-0's,4-1's,4-2's}}+\overbrace{\frac{10!}{2!4!4!}}^{\text{2-0's,4-1's,4-2's}}+\underbrace{\frac{9!}{1!4!4!}}_{\text{1-0,4-1's,4-2's}}+\overbrace{\frac{8!}{0!4!4!}}^{\text{0-0's,4-1's,4-2's}}=140140\)

Check this out. I could hav easily led myself down the primrose path.

Maybe pka will be along to either confirm or deny. I always get nervous when calculating these infernal counting problems.

 

[pka]

I have not worked on this.
But I think I would do the oppsite.
Where does 1 come before a zero?
Where does 2 come before a one?

 

[KidKat1]

I don't think that works either because it doesn't take the two's into consideration because you could have 012 and then fill the rest or you could have 0012 or 0102 or you could have all the ones and zeros and no twos until the last 4 digits

 

[Count Iblis]

I can see a straightforward way to solve the problem, but I don't have time to work it out. What you do is you consider a sequence for which the constrained part starts with n1 zeroes and n2 ones and then 1 two. n1 can range from 1 to 6 and n2 can range from 1 to 5. Calculate as a function of n1 and n2 how many sequences there can be. I think it is

(15 - n1 - n2 - 1)!/[(6-n1)! (5-n2)!3!]

We want to sum this over all possible values n1 and n2 can take. Define new variables m1 = 6 - n1; m2 = 5 - n2. Then the summand is

(m1 + m2 + 3)!/(m1!m2!3!)

You can rewrite it as:

(m1 + m2)!/(m1!m2!) * (m1 + m2 + 3)!/[(m1 + m2)! 3!]


Sum this by first keeping m1 + m2 fixed: You put m1 + m2 = M and then you sum over the possible values M can take.

 

[Denis]

140140 confirmed as correct: bruted thru a program (used 1's, 2's, 3's)

low : 111111222223333
high: 123333222211111

gross candidates: 1st digit = 1, 2nd digit < 3, sum digits = 28, 4 digits = 3
removals:
examine from left to right;
remove if "3" hit before "2"

 

[Count Iblis]

I see that my solution was again too complicated You only need to put in the first zeroes and a one as Galacticus did. The summation can be performed in closed form. You get

\(\displaystyle \frac{8!}{4!^{2}}{14\choose 9}\)

To see this, the summation in Galacticus's posting is up to the factor \(\displaystyle 1/4!^{2}\) :

\(\displaystyle \L\sum_{n=0}^{5}\frac{(n+8)!}{n!}\).

But this is the eight derivative of the function

\(\displaystyle \L f(x)= \sum_{n=0}^{5}x^{n+8}\)

evaluated at \(\displaystyle x = 1\). Summing the geometric series gives:

\(\displaystyle f(x)= x^{8}\frac{x^{6}-1}{x-1}\)

We are, of course, not going to differentiate this 8 times and take the limit \(\displaystyle x\rightarrow 1\), we are far too lazy for that. Instead let's do a series expansion about the point \(\displaystyle x = 1\). We put \(\displaystyle u = x-1\). The coefficient of \(\displaystyle u^{8}\) is the desired result divided by 8!. In terms of u the function is:

\(\displaystyle \L \frac{(1+u)^{14}-(1+u)^{8}}{u}\)

So, we need the coefficient of \(\displaystyle u^{9}\) from the numerator, but this can only come from the first term. This means that the summation is:

\(\displaystyle 8!{14 \choose 9}\)

 

[Count Iblis]

From the answer

\(\displaystyle {8\choose 4}{14\choose 9}\)

we can see a simple way to solve the problem

You place the first zero at the first postion. Then you have 5 zeroes, five ones and 4 two's left. You then place the five zeroes at the remaining 14 positions. There are \(\displaystyle {14 \choose 5}= {14 \choose 9}\) ways to do that. Then you place a one at the first empty spot and then the remaining one's and two's are placed in the remaining open places for which there are \(\displaystyle {8\choose 4}\) possibilities.

 

[Denis]

b = blank

bbbbb01 : 00000 1111 2222, 00000 1112 1222, ....., 2222 1111 00000
bbbb001 : b0000 1111 2222
bbb0001 : bb000 1111 2222
bb00001 : bbb00 1111 2222
b000001 : bbbb0 1111 2222
0000001 : bbbbb 1111 2222

That's the way galactus did it, and to me is the PERFECT way
(probably ONLY way) to show a student "how it works".