2
$\begingroup$

Please help me count.

I have an alphabet with 26 English letters. I can reduce it to 25 letters by representing two of the letters (e.g. O and X) with a new letter (e.g. $\otimes$).

25

To get down to a 25 letter alphabet I have $26 \choose 2$ possibilities. So 325 possible reductions to alphabet of size 25.

2

Getting down to an alphabet of size 2 is also pretty easy - I just need to count all possible ways of dividing the alphabet into 2 partitions. That would be $26 \choose 1$ + $26 \choose 2$ + ... + $26 \choose 13$. In the same way I can reduce my alphabet to any size from 1 to 25. That's 38,754,731 (computed in R like this sum(choose(26,1:13))).

The Rest

How can do the counting for size 3 or 24?

What is the total number of such alphabet reductions?

  • 0
    So you have to divide the $\binom{26}{13}$ cases by 2. A simpler way to look at it is that you have to pick some subset to be the first one, everything else goes in the second, and neither the first or second can be empty. This is $2^{26}-2$ choices for the first set, but you have counted every split exactly twice. So the number of ways is $2^{25}-1$2011-03-13

1 Answers 1

3

You're probably looking for the Bell numbers.

  • 1
    Then subtract 1.2011-03-13