They were dark times in the Kingdom of Verdoon. A band of fierce Rogues was terrorizing the local hamlets. King Buford was very displeased — he had no other option but to send out a legion of Brave Knights and Loyal Knights to round up the Rogues and deliver them to the castle dungeons.
So he chose seven of his bravest Brave Knights, and seven of his most loyal Loyal Knights, and dispatched them across Mount Kerchoo to the hamlet of Dunken, where the Rogues were last reported to have been wreaking havoc.
The Knights were capable Knights, and soon rounded up seven of the fiercest Rogues, including their leader, Thorn Yackley. Now they had the difficult task of escorting the Rogues back through the narrow, winding path over Mount Kerchoo.
The Rogues were so fierce, no single sword could subdue any of them, nor could a single mace. But they were no match for both a sword and a mace.
Now the Brave Knights carried a single sword, and the Loyal Knights a single mace. So on the trek back to the castle — where they had to walk single file, the path was so narrow — it was vital that each Rogue be flanked by both a Brave Knight and a Loyal Knight in the event the Rogue tried to escape.
The question: In how many ways could the Brave Knights, Loyal Knights, and the Rogues be lined up so that on the treacherous way back, each Rogue was flanked by both a Brave Knight and a Loyal Knight?
(For this problem, consider the Brave Knights indistinguishable from each other; similarly for the Loyal Knights and Rogues.)
Recently, I had been challenged to create a lesson which involved problem-solving with binomial coefficients. But I didn’t want to create just any lesson — I wanted something interesting and novel.
Now if you’ve ever taught combinatorics and counting, you know that there is a deluge of problems about binomial coefficients — from choosing committee members, sitting people around a circular table, lining up books on shelves, etc. So it’s not an easy task to come up with something you think might be new.
That was the genesis of Knights and Rogues. Of course it may very likely not be new, since it really is difficult to come up with a combinatorics problem no one has thought about before. But I did ask a colleague who knows a lot about problem solving, and he hadn’t seen it before.
The story is just to get students interested. Combinatorially, we could state the problem as follows:
Given p 0’s, q 1’s, and r 2’s, in how many ways can you line them up so that each 2 is surrounded by both a 0 and a 1?
It turns out that there is a lot going on in this problem. With three parameters, the analysis is far from straightforward.
There are a few restrictions on the parameters. For example, we need 
or else there wouldn’t be enough Brave Knights and Loyal Knights to flank the Rogues. For example, if p = 2, q = 1, and r = 3 (so that q just falls short of the above inequality), you can see the problem — the one 1 can flank at most two 2’s, and so there is one 2 without an adjacent 1. But if increase q to 2, we can have either the sequence 0212021 or 1202120.
Of course it is possible to consider specific examples, but it is also possible to consider infinite families of parameters — we’ll look at the case p = 2, q = n, and r = 2 to give you an idea of the reasoning involved.
Now when n = 1, there is only one possibility: 02120. But when n is larger than 1, we need to look at two separate cases: when the 2’s are separated by more than one 0/1, so that we are looking at two blocks of 021 or 120. When the 2’s are separated by exactly one 0/1, we only have the options 02120 or 12021. We need to count each case separately.
Let’s look at the first case. We have two blocks of either 021 or 120. This uses up the two 1’s but there are n – 2 1’s left over. So we have n things to arrange: two blocks, and n – 2 1’s. This may done in
ways, since we first choose the 2 places for the blocks, but then multiply by 4 since each block has two possibilities: 021 or 120.
In the second case, if the 2’s are only separated by one number, we may have a block of 02120 and n – 1 1’s to place, giving n possibilities. With a block of 12021, we have the block, one 0, and n – 2’s to place, which can be done in
ways (since the order of the block and the one 0 matters). Adding these three cases together results in
possible lineups for the Knights and Rogues.
Interestingly, these are the octagonal numbers (A000567 in the OEIS). I have no idea why, though….
What I like about this problem is that parameterizing p, q, and r in different ways produces seemingly very different results. One interesting parameterization is p = q = r = n. It turns out that this sequence — at least the first several values, which I used the computer to generate and didn’t work out by hand — is also in the OEIS (A141147), and the description is the
number of linear arrangements of n blue, n red and n green items such that the first item is blue and there are no adjacent items of the same color (first and last elements considered as adjacent).
I find this particularly intriguing since in Knights and Rogues, 0’s and 1’s can be adjacent — but even though 2’s are not adjacent, it is not possible to have any block be 020 or 121, although these are counted in A141147. Finding a bijection between the two linear arrangements would be a very interesting problem.
I hope you enjoyed reading about Knights and Rogues! Again, this is another example of mathematics as it happens — I came up with this problem within the past few weeks, and I’ve just scratched the surface of this interesting puzzle. I hope it’s actually a new problem, but I won’t be surprised if I get a comment like, “Oh, I saw that problem in…..” Generating new, novel mathematics problems is not an easy task…..
And incidentally, the answer to the initial problem is 80,096. Did you get it?
Creativity in Mathematics 
One thought on “Knights and Rogues”