Counting heads
February 4, 2015 at 8:35 AM by Dr. Drang
My older son came home from school yesterday with a combinatorial problem that he and I both messed up because it seemed simple and we went too fast. A simple Python script didn’t make that mistake.
The problem, minus some irrelevant details, is this: Eight people are sitting around a circular table. Each has a coin. They all flip their coins. What is the probability that no two adjacent people will get heads?
This is an enumeration problem. There are possible coin sequences, each with equal likelihood. We need to count how many of these sequences have no adjacent heads.
To me, the most straightforward way to go about this is to first figure out how many sequences there are for zero heads, one head, two heads, and so on, and then work out the number of nonadjacent sequences for each head count. When doing this by hand, the head counts are easy to get from Pascal’s triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
The last line gives the head counts: there’s one sequence of zero heads, eight sequences of one head, 28 sequences of two heads, 56 sequences of three heads, and so on.
Obviously, if there are no heads, there can’t be any adjacent heads. Therefore, the one sequence with zero heads is one we want in our enumeration. Similarly for all eight sequences with one head. That gives us a total of nine so far.
Of the 28 sequences with two heads, most of them won’t have adjacent heads, so it’s easier to count the ones that do. There are eight of them, when the heads are at positions 1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-8, and 8-1. That leaves 20 sequences with no adjacent heads from this set, for a total of 29 so far.
Let’s skip over the sequences with three heads, because that’s where my son and I messed up. We’ll come back to it.
Of the 70 sequences with four heads, only two have no adjacent heads: one where the heads are at the even-numbered table positions and one where they’re at the odd-numbered positions. That brings our total up to 31.
It should be clear that every sequence with five or more heads must have at least two adjacent heads, so we can stop now and go back to the three-head sequences.
Our plan for three-head sequences was to follow the logic we used on two-head sequences: figure out the number of sequences that do have adjacent heads and subtract that from 56. If we start by looking the sequences with heads at positions 1 and 2, we see that the third head can be at any of the other six positions and we’ll still have adjacent heads. Similar reasoning applies when there are heads at 2 and 3, 3 and 4, and so on. So we figured there must be sequences with adjacent heads and therefore only 8 three-head sequences without adjacent heads, bringing the total to 39.
You probably see where we went wrong. Yes, there are six three-head sequences with heads at 1 and 2 and also six three-head sequences with heads at 2 and 3, but the subtotal is 11, not 12, because one of the sequences (heads at positions 1, 2, and 3) shows up in both. There are, in fact, only 40 unique three-head sequences with adjacent heads, so we should have gotten 16 from this step, not 8. That puts the total at 47.
Scripts don’t rush through their work the way people do. They don’t double-count or skip. Of course, they have to be set up correctly in the first place, but I was lucky in that regard, because I’d already written a script for generating sequences of coin flips. All I had to do was tweak it for this application.
python:
1: #!/usr/bin/python
2:
3: f = 8
4: flips = list('-' * (f))
5: seqs = []
6:
7: def sequpdate(flips):
8: global seqs
9: heads = flips.count('H')
10: circle = flips[-1] + ''.join(flips)
11: if circle.find('HH') == -1:
12: seqs.append('%d heads: %s' % (heads, ''.join(flips)))
13:
14: def sequence(m):
15: global flips
16: if m == 1:
17: flips[-m] = 'T'
18: sequpdate(flips)
19: flips[-m] = 'H'
20: sequpdate(flips)
21: else:
22: flips[-m] = 'T'
23: sequence(m-1)
24: flips[-m] = 'H'
25: sequence(m-1)
26:
27: sequence(f)
28: print '%d sequences' % len(seqs)
29: seqs.sort()
30: print "\n".join(seqs)
Most of the code is explained in the earlier post. In essence, the script generates an eight-character string representing every one of the 256 possible sequences. It checks each of them for the “HH” substring—if the substring is missing, there are no adjacent heads for that sequence, and it gets saved. When the script is done, we count the number of saved no-adjacent-head sequences and print them out. The output looks like this:
47 sequences
0 heads: TTTTTTTT
1 heads: HTTTTTTT
1 heads: THTTTTTT
1 heads: TTHTTTTT
1 heads: TTTHTTTT
1 heads: TTTTHTTT
1 heads: TTTTTHTT
1 heads: TTTTTTHT
1 heads: TTTTTTTH
2 heads: HTHTTTTT
2 heads: HTTHTTTT
2 heads: HTTTHTTT
2 heads: HTTTTHTT
2 heads: HTTTTTHT
2 heads: THTHTTTT
2 heads: THTTHTTT
2 heads: THTTTHTT
2 heads: THTTTTHT
2 heads: THTTTTTH
2 heads: TTHTHTTT
2 heads: TTHTTHTT
2 heads: TTHTTTHT
2 heads: TTHTTTTH
2 heads: TTTHTHTT
2 heads: TTTHTTHT
2 heads: TTTHTTTH
2 heads: TTTTHTHT
2 heads: TTTTHTTH
2 heads: TTTTTHTH
3 heads: HTHTHTTT
3 heads: HTHTTHTT
3 heads: HTHTTTHT
3 heads: HTTHTHTT
3 heads: HTTHTTHT
3 heads: HTTTHTHT
3 heads: THTHTHTT
3 heads: THTHTTHT
3 heads: THTHTTTH
3 heads: THTTHTHT
3 heads: THTTHTTH
3 heads: THTTTHTH
3 heads: TTHTHTHT
3 heads: TTHTHTTH
3 heads: TTHTTHTH
3 heads: TTTHTHTH
4 heads: HTHTHTHT
4 heads: THTHTHTH
There is one subtlety of checking for adjacent heads that can’t be overlooked: positions 1 and 8 are adjacent at the table and they must be made adjacent in the sequence string, too. That’s done in Line 10 of the sequpdate function. It makes a new string, circle that inserts a copy of the eighth flip before the first flip, which makes the new string nine characters long. With that extension, every adjacent pair on the table is represented by an adjacent pair in the string, and searching for “HH” works correctly.
“Brute force” is a phrase often used to describe using a computer program to run out calculations like this. It’s true that solving a problem this way doesn’t result in an elegant formula that can be reused, but it does result in an algorithm that can be reused. Also, by making it easy to generate solutions for different sized tables, the script could be used to assist someone in developing an elegant formula through induction. That someone won’t be me, though. In the grand tradition of textbook writers, I leave that as a exercise for the reader.
Update 2/5/15 8:53 AM
A few people actually did look into the formula. Aristotle Pagaltzis shows that the recurrence relation matches that of the Fibonacci sequence:
@drdrang f(x)=no adjacent heads w/ x people: f(2)=3 f(3)=4 f(4)=7 f(5)=11 f(6)=18 f(7)=29 f(8)=47 f(9)=76 …Look familiar? f(x)=f(x-1)+f(x-2)
— Aristotle (@apag) Thu Feb 5 2015 6:45 AM
The sequence itself isn’t the Fibonacci because the starting values are different. That’s where Pete Carlton comes in:
@drdrang Looks like the number of no-adjacent-heads sequences for N people is the N+1th Lucas number
oeis.org/A000032
(Turns out.)
— Pete Carlton (@pmcarlton) Thu Feb 5 2015 5:35 AM
The Online Encyclopedia of Integer Sequences is one of those wonderful internet sites that serve an extremely niche audience extremely well.
I also got an email from Mark Berger who pointed me to this Groovy script and this Ruby script of his, both of which generate the sequence of coin flips in a much smarter way than my script does. They deserve a followup post of their own.
