Fun combinatorial problem

[pozorvlak]

This morning, I got an email from (of all things) a pianist, which had been relayed to the department at large by the Head of Department. He was trying to develop a more rigorous warm-up routine for pianists. Specifically:

One of my exercises involves fingers 1-2-3-4. To succeed in playing smoothly at the piano, and to produce equality in the fingers, the following rules must be observed (each 'rule' has a direct technical application at the piano):

each combination must be 6 digits long ; the same number can be used more than once, but never consecutively ; all 4 numbers must be used at least once ; and the combination must not end on 1 or 2.

I have tried my best to work out the possibilities (I have around 30 so far), but I know there must be an equation for this. I just can't see it!

You may like to have a go at this yourself: once you've done that, here's the email I sent him back:

Hi Kris,

My Head of Department passed on your email to (amongst others) me - you've probably had a much better reply from people who actually do this sort of thing for a living (combinatorics isn't my field), but here's my two penn'orth. Thanks for the problem, by the way, which was good fun :-)

> each combination must be 6 digits long ; the same number can be
> used more than once, but never consecutively ; all 4 numbers must
> be used at least once ; and the combination must not end on 1 or 2.

OK, let's warm up by considering /all/ 6-digit sequences of the numbers 1 to 4. We have four choices for the first number, then four for the second, then four for the third, then... so we have 4*4*4*4*4*4 = 4^6 = 4096 possible sequences. Apologies if this is old hat to you, but it helps with understanding the trickier steps to come.

Now, for your second condition, that the same number can't occur twice consecutively. As before, we have four choices for the first number; but now, we have only three for the second, because we can't take the number we chose first. For the third, we again have three choices, because we can take any number apart from the second one. So we have 4*(3^5) = 972 choices.

The third condition's a bit trickier, but not too hard. We want only the sequences that use all four numbers. What we have is a formula for the number of sequences that use four, three, two or one number(s). But looking a bit harder at our formula, we see that we can also use it to give the number of sequences that use three or fewer numbers, or two or fewer numbers: for instance, the number of sequences using only the numbers 1,2 and 3 (without consecutive digits equal) is 3 (for the first digit) * 2^5 (for the subsequent digits). We can then get the sequences that use only three out of {1,2,3,4} by multiplying this by the number of ways of choosing 3 things from 4 things, which is (4!/3!(4-3)!) by a standard result. What we want is

[sequences using 4,3,2 and 1] - [sequences using 1,2,3 or 1,2,4 or 1,3,4 or 2,3,4] + [sequences using 1,2 or 1,3 or 1,4 or 2,3 or 2,4 or 3,4] - [sequences using 1 or 2 or 3 or 4]

This alternating sum works by over-counting followed by subtracting away the sequences we've counted too often. For instance, consider the sequence 121212. We count it as a sequence using 1,2,3 and 4, then remove it twice (as a sequence using 1,2,3 and 1,2,4) then add it back in once (as a sequence using 1,2). The net effect is that we don't count it at all. This technique is called the inclusion-exclusion principle, and I'm explaining it really badly - sorry! Anyway, this gives us

972 - 4*3*(2^5) + 6*2*(1^5) - 4*1*(0^5) = 600 sequences.

We now have only the fourth condition, that the sequences don't end in 1 or 2. By symmetry, half the sequences we've got so far will end with 1 or 2, so we just divide by 2 to get 300 possible sequences. I think this might be a bit too much to do as a warmup!

An interesting question might be to find a route through these sequences that's memorable - for instance, a rule for turning one sequence into the next by swapping digits or something. This is the kind of thing that church bell-ringers do, and there's some fascinating mathematics behind it, but I haven't studied it in detail.

Anyway, I hope that helped: attached is a list of all 300 sequences, which I generated by programming a computer to generate all 4096 sequences of 6 digits, then removing all the sequences that failed one or more of your conditions. I can send you the code if you like, but it's not terribly elegant :-)

[The code worked as follows: starting from a file piano that contained all 6-digit sequences using 1-4, I ran the following one-liners:
perl -ne 'print unless /(.)\1/' piano > piano2
perl -ne 'print unless /[12]$/' piano2 > piano3
perl -ne 'chomp; my %used; foreach my $char (split //) { $used{$char}++ }; print "$_\n" if scalar(keys(%used)) > 3' piano3 > piano4
wc piano4
and then sent him piano4.]

Now, what's the next problem?

For maximum points, provide a combinatorial argument establishing the number of such sequences, and an algorithm to enumerate them all. Bonus points if your algorithm traverses the space of warmup sequences in a manner that can be used by the pianist without resort to memorising vast numbers of sequences :-)

Comments

Goodiok

[(Anonymous)]

Hi

Very interesting information! Thanks!

Bye