Coin Flip

[westin]

hi, this is a Math Count problem. Answer is 16/91

Can someone help as I don' know how to start. thansk

 

[pka]

View attachment 29573

Chris flips twelve heads and four tails. That can be done in [imath]\dfrac{16!}{12!\cdot 4!}=1820[/imath] ways.
Given exactly twelve heads in sixteen how can the four tails be disturbed so that no five of the heads are in a row?

 

[westin]

HHHHTHHHHTHHHTHT
HHHHTHHHHTHHHTTH
........

The answer should be find percentage not containing 5 tosses in a row then divide by the possible ways 16 coins can land and throw away those that don’t have exactly 12 heads(using your formula = 1820)

however, I cannot figure out how to calculate the percentage not containing 5 tosses in a row. =(

 

[Cubist]

I can't think of a nice quick way to do this. However, you could make a table of how many heads there are to the left and right of each tails. To keep the row count low, have the quantities on each row strictly ascending AND then work out how many ways they can be permuted. Complete the following...

 T T T T    # ways to permute
0 0 4 4 4    10
0 1 3 4 4    60
0 2 2 4 4    30
0 ? ? ? ?     ?
0 ? ? ? ?     ?
1 ? ? ? ?     ?
1 ? ? ? ?     ?
1 ? ? ? ?     ?
1 ? ? ? ?     ?
2 ? ? ? ?     ?
2 2 2 3 3     ?
        TOT 320

320/1820 = 16/91

 

[westin]

Thanks Cubist.

0 0 4 4 4: 5!/((3!)(2!) = 10;
0 1 3 4 4: 5!/(2!) =60;
0 2 2 4 4: 5!/(2!)(2!) = 30
0 2 3 3 4: 5!/(2!) = 60
...
...
2 2 2 3 3: 5!/((3!)(2!)) = 10

I understand more now. thank you. this is a great way to tackle this question.

I am wondering is there a faster solution. Since this is a Math Count question, the most time for it is maybe only 5 minutes. It would be great if someone can help to think of an even faster solution. Again, thank you Cubist for the help!!!!

 

[Cubist]

I am wondering is there a faster solution. Since this is a Math Count question, the most time for it is maybe only 5 minutes.

If you have a good memory, then you could try to remember the technique shown in full on this page link to stackexchange. Formula is...

[math] \sum_{q=0}^{\min(n, \lfloor N/(r+1) \rfloor)} (-1)^q \times \binom{n}{q} \times \binom{N - q(r+1)+n-1}{n-1} [/math]where (compared to stars and bars) N is the total number of stars, n is the number of buckets (or bars+1), and r is an upper limit of stars in any bucket

Your problem would require the following calculations (with N=12, n=5, r=4)...

q     (-1)^q  * choose(n,q) * choose(N - q*(r+1)+n-1, n-1)
0        1    *   1         *          1820                   =  1820
1       -1    *   5         *           330                   = -1650
2        1    *  10         *            15                   =   150
                                                            SUM   320

--

FYI: Here's the completed table from the post#4 method, which probably wouldn't take very long to complete once you get going - but this method is quite prone to the error of accidentally missing a row!

 T T T T    # ways to permute
0 0 4 4 4    10
0 1 3 4 4    60
0 2 2 4 4    30
0 2 3 3 4    60
0 3 3 3 3     5
1 1 2 4 4    30
1 1 3 3 4    30
1 2 2 3 4    60
1 2 3 3 3    20
2 2 2 2 4     5
2 2 2 3 3    10
        TOT 320