# Counting the number of sequences with these properties.

The following question was given on an exam I wrote, and I would like to see if anyone can identify any problems with my solution. I would also be very interested if anyone has a more elegant solution.

Note: if my solution is too long to look over, I won't mind if you ignore it and volunteer your own solutions to the question.

Question: How many sequences of 21 coin flips consisting of 15 tails and 6 heads satisfy the following three properties:

1) the first and last coin flip results in tails;

2) there are no consecutive occurrences of heads;

3) every sequence of consecutive tails has odd length.

Below is an outline of my solution:

We suppose the first and last coin flip results in a tails and count the number of sequences of 19 coin flips with 13 tails and 6 heads (and adjust the above conditions appropriately).

Case #1: There is a head immediately after the first tails and immediately before the last tails. The number of such sequences is given by counting how many ways we can choose the size of the "gap" between consecutive heads. Since we require that consecutive sequences of tails have odd length, we must have that the gaps between successive heads are of odd length. In particular, they may take the values $\{1, 3, 5, 7\}$. Solving this is equivalent to distributing 13 identical objects into 5 distinct boxes such that no box is empty. This is given by ${(13-5)+5-1\choose (13-5)}= {12 \choose 8} = {12 \choose 4}$.

Case #2: There is a head immediately before the last tails, but there is some odd-length sequence of consecutive tails at the start of the sequence. Since we fixed the first tail, there must be some even-length sequence of tails following the first tail. We observe that the length of this sequence is, at most, 8 (otherwise we have an occurrence of consecutive heads). So then the length of this initial sequence of tails (not counting the first tail we fix) takes values in $\{2, 4, 6, 8\}$. The number of sequences of this form is given by: $\displaystyle\sum_{k}{(13-k-5)+5-1\choose (13-k-5)}$, for $k \in \{2,4,6,8\}$.

Case #3: This case is the same as the previous one, except we consider those sequences where there is a head immediately after the first tails, and some odd-length sequence of tails at the very end (counting the last tail we fix).

Case #4: In this final case, we consider all such sequences where there is some even-length sequence of consecutive tails immediately after the first tail and immediately before the last tail. As by our previous remark, these two sequences cannot have a combined length of greater than 8. So then the possible lengths of these initial and terminal sequences of consecutive tails is given by the ordered pairs $(2,2), (2, 4), (4,2), (4,4)$. So then if we index these lengths, we have $j \in \{4, 6, 8\}$, and the number of such sequences is given by ${(13-j-5)+5-1\choose (13-j-5)}$ for each $j \in \{4, 6, 8\}$ except that for $j=6$ we multiply by two since there are two such possibilities.

A simpler way to think about it is to imagine a head added at the left end. Then attach a tail to the right of each head to avoid two heads in a row. Connect the remaining $8$ tails into four pairs, which you can put to the right of any existing tails or another pair. You are now looking for weak compositions of four into seven parts. A standard stars and bars computation shows this is ${7+4-1 \choose 4}=210$

Ooops, this is the problem without the fact there are no two consecutive heads.(i´ll leave it though)

This is the same as chosing 6 heads, in a number n of blocks of consecuive heads. with the condition that the distances between blocs be odd and the first block starts at an even position.

Suppose we have a given selection of n blocks. In how many ways can we position these n blocks? the distance between each block is at least 2 and the first block is in position at least 2. Also the last block must end in an even position. If we chose the position of the first head and the spaces between blocks then we are done. This is the same as chosing $s_1,s_2,s_3...s_n$ where $2s_1$ is the position of the first tail and $2s_i+1$ is the distance between blocks $i-1$ and $i$.

Note that we need the last heads to be in an even position. Check that if the position of the first elements is 2s_1 then the position of the last element is $2s_1+2s_2+...2s_n+2(n-1)+6=2s_1+2s_2+...2s_n+2n+4$ Meaning this condition is always satisfied

So now what we have to count is the number of different lists of non negative integers$(s_1,s_2,s_3....s_{n})$ such that $2(s_1+s_2+s_3...+s_n+n+2)\leq20\rightarrow (s_1+s_2+s_3....s_n)\leq8-n$

Using the stars and bars method gives us this is $\sum_{k=0}^{8-n}\binom{k+n-1}{n-1}$

And we want $\sum_{n=1}^{8}(\sum_{k=0}^{8-n}\binom{k+n-1}{n-1})$

I tink thee is an identity to reduce the first sum, but I can't remember.