Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You have double counted the ways to get to 2. $\binom{26}{2}$ and $\binom{26}{24}$ are counting the same thing. And what happens at 13? –  Ross Millikan Mar 13 '11 at 15:57
    
Ross, you're exactly right, at 13 you are splitting into 2 partitions of the same size. I realized that too after sleeping it over. –  Aleksandr Levchuk Mar 13 '11 at 18:48
    
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$ –  Ross Millikan Mar 13 '11 at 18:52

1 Answer 1

up vote 3 down vote accepted

You're probably looking for the Bell numbers.

share|improve this answer
    
I need a slight variation of the Bell numbers. In bell numbers $B_3 = 5$ as $\{a, b, c\}$ partitions into (#1) $\{\{a\}, \{b\}, \{c\}\}$, (#2) $\{\{a\}, \{b, c\}\}$, (#3) $\{\{b\}, \{a, c\}\}$, (#4) $\{\{c\}, \{a, b\}\}$, and (#5) $\{\{a, b, c\}\}$. I need $B'_3 = 4$ because for my case partition #1 {{a}, {b}, {c}} is not meaningful - I need the size of the derived alphabet to be strictly less. –  Aleksandr Levchuk Mar 13 '11 at 7:41
1  
Then subtract 1. –  Yuval Filmus Mar 13 '11 at 7:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.