Four Island

I was going through some old posts on the Fourm (which is to say, all posts on the Fourm :3) because I was bored and I found a post in which I inadvertently did some discrete math in counting how many different badly-named clones of Gryphic there were, given that a badly-named clone of Gryphic has 7 letters, they have at least one letter in common, and that letter is in the same position in "Gryphic" and the badly-named clone. I appear to have used the Rule of Product and came up with the number 2,162,410,431. However, having now actually taken a class in discrete math, I can see that this is very wrong and in fact overcounts the number of possible Gryphics. And because I'm still bored, I'm going to write out a proof. :P

Let $latex L$ be the number of badly-named clones of Gryphic. First of all, we note that a badly-named clone of Gryphic has seven letters in its name, and at between 1 and 6 of those letters match those in "Gryphic." If 7 letters matched, then it would not be a badly-named clone, and if 0 letters matched, the clone would have no relation to Gryphic at all. Next, we partition on the number of letters that differ. If we let $latex A_n$ be the number of badly named clones of Gryphic with $latex n$ letters in common with "Gryphic," then by Rule of Sum:

$latex L = \sum\limits{i=1}^6Ai$

To construct a badly-named clone of Gryphic with $latex n$ letters matching, we first choose which $latex n$ letters should match (there are $latex \binom{7}{n}$ ways to do this), and then choose unmatching letters for the remaining $latex 7-n$ letters. If we let $latex B_n$ be the number of ways to choose the remaining $latex 7-n$ letters, then by Rule of Product:

$latex An = \binom{7}{n}Bn$ $latex L = \sum\limits{i=1}^6\binom{7}{i}Bi$

There are 26 letters in the alphabet, and for each of the $latex 7-n$ remaining letters, we have to choose a letter that is NOT the corresponding letter in the original name, "Gryphic." Therefore, for each of these positions, there are 25 possible other letters we could pick. By Rule of Product:

$latex Bn = 25^{7-n}$ $latex L = \sum\limits{i=1}^6\binom{7}{i}25^{7-i}$

We want to use the binomial theorem to simplify this expression, but the bounds of our summation are slightly off. To remedy this, we can expand the range of the summation, and then subtract the new terms (which are simple edge cases). Therefore:

$latex L = \sum\limits{i=0}^7\binom{7}{i}25^{7-i} - \binom{7}{0}25^7 - \binom{7}{7}25^0$ $latex L = \sum\limits{i=0}^7\binom{7}{i}25^{7-i} - 25^7 - 1$

Then, by the binomial theorem:

$latex \sum\limits_{i=0}^7\binom{7}{i}25^{7-i} = 26^7$ $latex L = 26^7 - 25^7 - 1 = 1928294550$

This makes logical sense. $latex 26^7$ represents all possible 7 letter words, $latex 25^7$ represents all 7 letter words that share no letter positions with "Gryphic," and 1 represents the number of words that are Gryphic. Therefore, there are 1,928,294,550 different possible badly-named clones of Gryphic, and in that original post four years ago, there must have been some clones of badly-named clones of Gryphic. Oh my. Imagine cleaning up after them. Ick.

Now, four years ago, I of course didn't know what the Rule of Product or even discrete math were, but it appears my line of thinking was that there had to be at least one letter in common, so choose which letter it should be (7 ways to do this) and then choose any other 6 letters, possibly even correct ones, for the other positions (26 ways to choose each letter, so $latex 26^6$ by Rule of Product). The reason we are allowed to pick correct letters for the other positions is because more than one (but less than 7, which I had not taken into consideration) letter is allowed to match. However, this overcounts because it is far too loose. Take, for instance, the edge case of actually forming the name "Gryphic." I originally subtracted one for this event, but it actually happens more than once. If we are to follow the above process, we can choose any of the 7 letters to be the same, and then for each of the remaining 6 letters, pick the correct letter. Therefore, there are 7 ways to actually choose the name "Gryphic," this being only one of the many ways the old formula overcounts.

Well, this has been your discrete math lesson that you never wanted. It was fun for me. Being on break is relaxing, but it's nice to think sometimes too, right? This was a perfect little exercise I could do that also had to do with Four Island. And Gryphic/Drifty is going to kill me. :D