1. ## Line 'em up!

There are 34 people in line to get into a theater. Admission cost is 5 dollars.
Of the 34 people, 28 have only a 5 dollar bill and 6 have only a 10 dollar bill.
To complicate matters, the ticket office has an empty cash register.
In how many ways can the people line up so that change is available when needed?

Example with 4 people, 2 (a and b) with 5's and 2 (c and d) with 10's:
a b c d
a b d c
b a c d
b a d c
a c b d
a d b c
b c a d
b d a c
So 8 ways...

2. ## Re: Line 'em up!

You only need to look at the first 11 positions. There are 34! arrangements without restriction.
There are $6\times 33!$ arrangements that fail because the first person has only a 10.
There are $28\times 6\times 5 \times 31!$ ways that the first person has a 5 and the second and third both have 10s.
Next we want 5,10,5,10,10,anything (because any other arrangement that fails in the first 5 people was already counted above)
$28\times 6\times 27 \times 5 \times 4 \times 29!$
We see the pattern:
$$\displaystyle 34!- \sum_{n=1}^6\dfrac{28!}{(29-n)!}\cdot \dfrac{6!}{(6-n)!}\cdot (35-2n)!$$

The chances that if people line up randomly, there will be enough change for everyone is $\dfrac{4621}{5797} \approx 80\%$.

3. ## Re: Line 'em up!

Thanks Slip. And that's basically the same as:
u = 28
v = 6
a = ? (arrangements)

a = (u + v)! * [(u + 1 - v)/(u + 1)]
= 234 150 150 962 444 663 430 869 931 786 240 000 000

which is the exact number of ways the people can line up...right?

Btw, a / 34! = ~.7931 (close to 80% as you're showing).

Question:
what if the 28 fivers are undistinguishable, so are the 6 teners?

4. ## Re: Line 'em up!

Originally Posted by DenisB
Question:
what if the 28 fivers are undistinguishable, so are the 6 teners?
$\dbinom{34}{6}-\dbinom{33}{5}-\dbinom{31}{4}-\dbinom{29}{3}-\dbinom{27}{2}-\dbinom{25}{1}-\dbinom{23}{0} = 1,072,072$

5. ## Re: Line 'em up!

Originally Posted by DenisB
Thanks Slip. And that's basically the same as:
u = 28
v = 6
a = ? (arrangements)

a = (u + v)! * [(u + 1 - v)/(u + 1)]
= 234 150 150 962 444 663 430 869 931 786 240 000 000

which is the exact number of ways the people can line up...right?

Btw, a / 34! = ~.7931 (close to 80% as you're showing).
One of us is using the wrong formula. Consider when the breakdown is 17 to 17. Then, my formula gives:

$$\displaystyle 34!-\sum_{n=1}^{17}\dfrac{17!}{(18-n)!}\cdot \dfrac{17!}{(17-n)!}(35-2n)! \approx \dfrac{34!}{3}$$

while your formula gives $\dfrac{34!}{18}$.

6. ## Re: Line 'em up!

Whoops...forgot to include u>v

7. ## Re: Line 'em up!

u=18,v=16 with my method gets around $.36*34!$ but your method gets $34!(3/19)$ which is less than half of what I get. How did you come up with the $34!(u+1-v)/(u+1)$?

8. ## Re: Line 'em up!

Take it easy on me Slip, I'm just an old guy trying to learn!

I came up with that from here (similar old problem):
https://en.wikipedia.org/wiki/Bertra...ballot_theorem

And now I'm at the stage where solution is:

Soooo...enlighten me!

9. ## Re: Line 'em up!

Well, I'm now pretty well convinced answer is 1,066,648.

And this is formula:
a = (u+v)C(u) * (u+1-v)/(u+1) = 34C28 * 23/29 = 1344904*23/29 = 1066648

10. ## Re: Line 'em up!

Originally Posted by DenisB
Take it easy on me Slip, I'm just an old guy trying to learn!

I came up with that from here (similar old problem):
https://en.wikipedia.org/wiki/Bertra...ballot_theorem

And now I'm at the stage where solution is:

Soooo...enlighten me!
I did not say I was right and you were wrong. I said one of us was using the wrong formula, and I did not understand where yours came from. Nor do I understand why my formula is not correct. I must be overcounting somehow.

11. ## Re: Line 'em up!

Let's make it a lineup of 10 this way: u = fivers = 7 and v = teners = 3
Let u be represented with 1's and v with 2's:
then total lineups = 120, from 1 1 1 1 1 1 1 2 2 2 to 2 2 2 1 1 1 1 1 1 1
(p = position)
1: eliminate cases where p1 = 2 : that's 36 cases; left = 120-36 = 84
2: eliminate cases where p2=p3=2: that's 7 cases; left = 84 - 7 = 77
3: eliminate cases where p3=p4=p5=2: that's 1 case; left = 77 - 1 = 76
4: eliminate cases where p2=p3=p5=2: that's 1 case; left = 76 - 1 = 75 ***

*** perhaps you missed this case?

My formula will give 75.
Not sure what yours will give; probably 76?

12. ## Re: Line 'em up!

Originally Posted by DenisB
Let's make it a lineup of 10 this way: u = fivers = 7 and v = teners = 3
Let u be represented with 1's and v with 2's:
then total lineups = 120, from 1 1 1 1 1 1 1 2 2 2 to 2 2 2 1 1 1 1 1 1 1
My formula will give 75.
This form is a much more workable problem than the original
Arranging the string $FFFFFFFTTT$ in $\dbinom{10}{3}=120$ ways.
I agree with your answer of $75$. But I counted dircctly, no elimations.
Here are the possible strings to count:
1) $FFF~\_~\_~\_~\_~\_~\_~\_$ i.e. beginning with three fives.
2) $FTFF~\_~\_~\_~\_~\_$ i.e. beginning with three fives & one T.
3) $FFTF~\_~\_~\_~\_~\_$ i.e. beginning with three fives & one T.
4) $FTFTF~\_~\_~\_~\_~\_$ i.e. beginning with three fives & two T.
5) $FFTTF~\_~\_~\_~\_~\_$ i.e. beginning with three fives & two T.

For #1, there are $\dbinom{7}{3}=35$ acceptable such strings. SEE HERE

For each of 2) & 3) there are $\dbinom{6}{2}=15$ acceptable such strings.

For each of 4) & 5) there are $\dbinom{5}{1}=5$ acceptable such strings.

That adds to $75$.

13. ## Re: Line 'em up!

Quite clear and elegant; merci Plato.