FMM4B

Friday Morning Math Problem

The Cthulhus Monogram

Ph'nglui Mglw'nafh Cthulhu Uaaah Gothanyth and their partner Nyarlathotep Cthulhu Azathoth R'lyeh (the Cthulhus), who live next door to the Zetas, are also expecting a new baby, and want to copy the Zetas' monogram idea (alphabetical monogram, no repeated letters). According to Cthuvian tradition, a baby will have either 4 or 5 names, and any name except for the first name may be the family name. (For example, ABCD would be a valid monogram, but AACD and CFGH are not.)

How many possible monograms are there for the little Cthulhu baby?

Solution

Divide all possible monograms into those with 4 names and those with 5 names. Now consider the case of a 4 letter monogram. C (for Cthulhu) can appear as the second or third letter, but cannot appear as the first (because of Cthuvian tradition) and cannot appear as the last (because there are more names than letters preceding C). The case where C is the second letter is similar to the original problem with baby Zeta. The last two slots can take on all letters between D and Z in alphabetical order, for a total of 22 + 21 + 20 + ... = 253 monograms. But, the first letter can be either A or B, which doubles the number of possibilities, for a total of 506 monograms. The case where C is the third letter is trivial - the first two letters must be A and B, which leaves one letter that must be D through Z, for a total of 23 monograms. The number of 4-letter monograms is 529. Now consider the case of a 5 letter monogram. C can appear as the second or third letter, but cannot appear as the first letter, or as the fourth or fifth letter (because there aren't enough letters preceding C). Consider the case of C as the second letter, -C---. We have two possible letters for the first slot, so we will multiply our possibilities for the last 3 slots by 2 in the end. The first slot can be any letter between D and Z, but let's pick one and try and see the pattern. Suppose that the third letter in the monogram is D. Then let us suppose that the second slot is E. Then the last slot can be F through Z, or 20 possible letters. If the next to last slot was F instead of E, the last slot would have to be G through Z, or 19 possible letters. So the number of possibilities, if we pick D as the third letter of the monogram, is 20 + 19 + 18 + ... = 20*21/2. Now suppose that the third letter in the monogram is E. Then the next to last slot can be F through Z. Let's suppose it's F. Then the last slot can be G through Z, for a total of 19 letters. If we change the next to last slot from F to G, now there are 18 letters left for the last slot. Repeating this procedure gives us 19 + 18 + 17 + ... = 19*20/2. So we are trying to add up (20*21/2) + (19*20/2) + (18*19/2) + (17*18/2) + ... which, in math speak, is \sum_{n=1}{s} \sum_{k=1}{n} k which (by some magic*) reduces to 1/3(s)(s+1)(s+2) for a grand total of 3080. And for the final case when the monogram is 5 letters long, C is in the third spot, which leaves one possibility for the first two letters (AB). By the method in the Baby Zeta problem, we can deduce the number of possibilities for the last two letters of the monogram start with DE, which, when enumerated, are 22 + 21 + 20 + ... = 21*22/2 = 231. The grand total for 4-name baby Cthulhu is 529, The grand total for 5-name baby Cthulhu is 3311, and the grand whopping total is 3840.