# combinatorics of coin tosses

12 tosses of a fair coin result in an outcome of 6 heads and 6 tails.

How many sequences of such a result can have at most 4 successive outcomes of one kind ?

I have obtained what I believe is the correct answer as 924 - 84 = 840, by considering various sequences to be excluded

(a) 6-6 of a kind (b) 6-5 of a kind (c) 5-5 of a kind (d) only one 6 of a kind (e) only one 5 of a kind

However, this seems a very crude and tedious method. I am seeking help whether this can be done by inclusion-exclusion, or by some other slick way.

-

Here is yet another way. It is still applicable when the number of H's and T's are changed or the maximal number $4$ in the question is changed:

Given a sequence of H's and T's, for example HTHHHHTTHTTT, note that H's and T's are partitioned. In the example, the (ordered) partition $p_H$ for H's is $1 + 4 + 1$, whereas it is $p_T = 1 + 2 + 3$ for T's. Note that the number of parts $l(p_H)$ and $l(p_T)$ of $p_H$ and $p_T$ are either the same or differ by 1. In the example, they are both 3. If they are the same, there are two possible ways to interlace H's and T's. If they differ by 1, there is only one way.

So, consider the partitions of 6. 6 = 6

= 5 + 1 = 4 + 2 = 3 + 3

= 4 + 1 + 1 = 3 + 2 + 1 = 2 + 2 + 2

= 3 + 1 + 1 + 1 = 2 + 2 + 1 + 1

= 2 + 1 + 1 + 1 + 1

= 1 + 1 + 1 + 1 + 1 + 1

Taking the order into account, there are 3 partitions having 2 parts, 10 partitions having 3 or 4 parts, 5 partitions having 5 parts and finally 1 partition having 6 parts, satisfying the criterion that no TTTTT and HHHHH must show up.

For $l(p_H), l(p_T)$ = 2, 2 we have $2.3.3 = 18$ sequences

For $l(p_H), l(p_T)$ = 2, 3 or 3, 2 we have $2.3.10 = 60$ sequences

For $l(p_H), l(p_T)$ = 3, 3 we have $2.10.10 = 200$ sequences

For $l(p_H), l(p_T)$ = 3, 4 or 4, 3 we have $2.10.10 = 200$ sequences

For $l(p_H), l(p_T)$ = 4, 4 we have $2.10.10 = 200$ sequences

For $l(p_H), l(p_T)$ = 4, 5 or 5, 4 we have $2.5.10 = 100$ sequences

For $l(p_H), l(p_T)$ = 5, 5 we have $2.5.5 = 50$ sequences

For $l(p_H), l(p_T)$ = 5, 6 or 6, 5 we have $2.5.1 = 10$ sequences

and finally

For $l(p_H), l(p_T)$ = 6, 6 we have $2.1.1 = 2$ sequences

So there are $18 + 60 + 200 + 200 + 200 + 100 + 50 + 10 + 2 = 840$ sequences.

-
I really like the generalisation. I was unsuccessfully toying with the idea of using "stars and bars" somehow, which has materialised in an "interleaving" avatar, which can be used to work out inclusions or exclusions, as convenient. Thanking you and all others who have extended their valuable help. – true blue anil Jun 14 '12 at 13:00

Here's another solution. It's not very slick, but it works.

First, let's find the number of arrangements with 5 or more consecutive heads. Consider the eight symbols: T, 5T, H,H,H,H,H,H. These can be put into 8!/6!=56 distinct orders. For 14 of these, the symbols T and 5T are neighbors. Now, for example if we expand 5T into TTTTT in either "5T T HHHHHH" or "T 5T HHHHHH" we get the same result. Compensating for that, the number of arrangements with 5 or more consecutive heads is 42+14/2 = 49. Similarly, the number of arrangements with 5 or more consecutive tails is 49.

How many arrangements have both 5 or more consecutive heads and 5 or more consecutive tails? We can arrange the four symbols 5T,T,5H,H in 24 different ways.

1. For eight of these arrangements, the heads and tails are separated, e.g., T 5H 5T H. Each of these counts once when expanded.

2. For eight of these arrangements, either heads or tails are separated but not both, e.g., T 5H H 5T. Each of these counts twice when expanded.

3. For eight of these arrangements, neither the heads nor tails are
separated, e.g., H 5H 5T T. Each of these counts four times when expanded.

Therefore, the number of arrangements with both 5 or more consecutive heads and 5 or more consecutive tails is 8/1+8/2+8/4=14.

-
Relooking at your approach, i find that it can be generalised for n heads, n tails with a max of (n-2) succesive outcomes of a kind as – true blue anil Jun 19 '12 at 6:59
(continued) C(2n,n) - 2(n+1)^2 + 14, which makes this approach extremely useful. Thanks ! – true blue anil Jun 19 '12 at 7:09
I'm glad that you find it useful. It's a fun problem! – Byron Schmuland Jun 19 '12 at 12:35

Here's another way. Let $a_n$ be the number of sequences in $n$ tosses of a coin in which there are at most 4 consecutive outcomes of one kind. Then by simple counting $a_1=2$, $a_2=4$, $a_3=8$, $a_4=16$, and $a_5=30$. With a little thought you can get the recurrence relation $$a_n=2a_{n-1}-a_{n-5}$$ Now there are two ways you can go. You can just use this recurrence to grind out $a_6=2\times30-2=58$, $a_7=2\times58-4=112$, and so on until you get up to $a_{12}$. Or you can use standard techniques to solve the (homogeneous, linear, constant-coefficient) recurrence, but I think it gets messy for this one. Well, that's what computers are for!

EDIT: OP has remembered that the outcome is to be 6 heads and 6 tails, so the above is irrelevant. So let's do inclusion-exclusion instead.

We start with $12\choose6$. We subtract all the ways of having 5 (or more) consecutive heads. That's 56, because the first of the 5 consecutive heads can be in any one of 8 locations, and, once you've fixed the first of the 5 consecutive heads, you've got 7 remaining tosses, of which 1 is supposed to be heads. There are also 56 ways of having (at least) 5 consecutive tails; subtract those as well.

Now add back in all the ways of having two instances of 5 consecutive heads. The only way for that to happen is to have 6 consecutive heads, and there are 7 ways for that to happen. Similarly, 7 ways to have two instances of 5 consecutive tails.

Also add in all ways of having 5 consecutive heads and 5 consecutive tails. If the heads are 1 through 5, there are 3 places for the tails, and 2 ways to fill in the other two slots; if the heads are 2 through 6, 2 places for tails, 2 ways to fill; heads 3 through 7, 1 place for tails, 2 ways to fill, making 12 ways with the runs of heads preceding the run of tails; another 12 the other way around.

Now we have to subtract out all the ways that meet three conditions. By the way, if you're getting the impression that there's nothing slick about inclusion-exclusion, at least for this problem, you're right, but it's what the customer wanted, and we've come this far, so let's go for it. We can have 6 consecutive heads and (at least) 5 consecutive tails, 4 ways (heads starting at 1, 2, 6, or 7), or 6 consecutive tails and 5 (or more) consecutive heads, another 4 ways.

Finally, we have to add back in the 2 ways of meeting four conditions; 6 heads followed by 6 tails, or the other way around.

So the answer would appear to be $${12\choose6}-56-56+7+7+12+12-4-4+2$$ whatever that is.

MORE EDIT: I figured out where I went wrong. In the next-to-last case, meeting three conditions, 6 heads and 5 (or more) tails can happen 6 ways, not 4. With the 6 heads starting at 1, the 5 tails can start at 7 or 8, and with the six heads starting at 7, the five tails can start at 1 or 2. Add in the heads starting at 2 or at 6 and you get 6 ways, not 4. This makes the final calculation $${12\choose6}-56-56+7+7+12+12-6-6+2$$ which is 840, in agreement with everyone else.

-
The procedure you suggest gives an answer of 2980, whereas all possible sequences are only C(12,6) = 924. There seems to be a communication gap somewhere ! – true blue anil Jun 13 '12 at 7:50
@Gerry Myerson : I'm so sorry. In the original question, I needed to mention that the outcome of the 12 tosses is 6 heads and 6 tails. – true blue anil Jun 13 '12 at 8:50
So, what are you waiting for? Edit that into the question! Now! – Gerry Myerson Jun 13 '12 at 10:08
@Gerry: I got a count of 840 against 844 that you are getting. Let me recheck. The answers should tally. – true blue anil Jun 13 '12 at 11:37
@Gerry: I have rechecked and get the same # for exclusions as before. (a) 6-6 of a kind:2 (b) 6-5 of a kind: 4 (c) 5-5 of a kind:8 (d) only one 6 of a kind: 6 (e) only one 5 of a kind: 64. 924 - 84- 840.The only count that is tedious is the last one. I had written "inclusion-exclusion or by some other slick way", hoping that I-E would be slick. I wonder if there is a slick way ? – true blue anil Jun 13 '12 at 12:22