Let us map all combinations of letters ( both valid words and gibberish) by a single criterion: 1st letter and all other appearances of that letter will be replaced by a digit 1, the first letter distinct from the 1st will be replaced by 2 , and so will be all other appearances of that letter , etc
Thus onion => 12312, queue => 12323, coffee => ¨ 123344 etc.

Clearly both "clue" and "ship" will be represented by a number 1234 while both "will" and "bass" by 1233.

Let us denote by a(k) the number of possible numbers of k digits.
Then a(1)=1; a(2)=2; a(3)=5 etc

1. Provide sample valid words for 1234512 and 123242526272.
2. List all the possible numbers for 4-letter combinations of letters (both valid and unvalid words).
3. Evaluate a(4), a(5), a(6).
4. Find a formula (either recursive or direct) for a(k).

I considered 2., 3., and 4 only. One way of looking at it is to permute {1,1,1,1,2,2,2,3,3,4} with length 4, {1,1,1,1,1,2,2,2,2,3,3,3,4,4,5} with length 5 etc. Once the unwanted solutions are discarded,  the series produced is the Bell numbers, A000110  in Sloane. Another interesting result is that if if a record is kept of the valid strings containing the wanted solutions as they emerge, it looks like this:

{1,1},{1,2}.

{1, 1, 1} ,  {1, 1, 2} ,  
{1, 2, 1}, {1, 2, 2},{1, 2, 3}.

{1, 1, 1, 1}, {1, 1, 1, 2}   
{1, 1, 2, 1}, {1, 1, 2, 2}, {1, 1, 2, 3}   
{1, 2, 1, 1}, {1, 2, 1, 2}, {1, 2, 1, 3},    
{1, 2, 2, 1}, {1, 2, 2, 2}, {1, 2, 2, 3},   
{1, 2, 3, 1}, {1, 2, 3, 2}, {1, 2, 3, 3}, {1, 2, 3, 4}.

 {1, 1, 1, 1, 1}, {1, 1, 1, 1, 2},      
 {1, 1, 1, 2, 1}, {1, 1, 1, 2, 2}, {1, 1, 1, 2, 3},      
 {1, 1, 2, 1, 1}, {1, 1, 2, 1, 2}, {1, 1, 2, 1, 3},       
 {1, 1, 2, 2, 1}, {1, 1, 2, 2, 2}, {1, 1, 2, 2, 3},      
 {1, 1, 2, 3, 1}, {1, 1, 2, 3, 2}, {1, 1, 2, 3, 3}, {1, 1, 2, 3, 4},      
 {1, 2, 1, 1, 1}, {1, 2, 1, 1, 2}, {1, 2, 1, 1, 3},      
 {1, 2, 1, 2, 1}, {1, 2, 1, 2, 2}, {1, 2, 1, 2, 3},       
 {1, 2, 1, 3, 1}, {1, 2, 1, 3, 2}, {1, 2, 1, 3, 3}, {1, 2, 1, 3, 4},      
 {1, 2, 2, 1, 1}, {1, 2, 2, 1, 2}, {1, 2, 2, 1, 3}      
 {1, 2, 2, 2, 1}, {1, 2, 2, 2, 2}, {1, 2, 2, 2, 3},      
 {1, 2, 2, 3, 1}, {1, 2, 2, 3, 2}, {1, 2, 2, 3, 3}, {1, 2, 2, 3, 4},      
 {1, 2, 3, 1, 1}, {1, 2, 3, 1, 2}, {1, 2, 3, 1, 3}, {1, 2, 3, 1, 4},      
 {1, 2, 3, 2, 1}, {1, 2, 3, 2, 2}, {1, 2, 3, 2, 3}, {1, 2, 3, 2, 4},      
 {1, 2, 3, 3, 1}, {1, 2, 3, 3, 2}, {1, 2, 3, 3, 3}, {1, 2, 3, 3, 4},       
 {1, 2, 3, 4, 1}, {1, 2, 3, 4, 2}, {1, 2, 3, 4, 3}, {1, 2, 3, 4, 4},  {1, 2, 3, 4, 5}.

Lokking at the number of solutions in each string and their length, we can write this {1*2},{1*2,1*3},{1*2,3*3,1*4},{1*2,7*3, 6*4,1*5}; the series 1,1,1,1,3,1,1,7,6,1... has a triangular look to it and seems to be A008277 in Sloane. The formula there given is

S2(n, k) = k*S2(n-1, k)+S2(n-1, k-1), n>1. S2(1, k) = 0, k>1. S2(1, 1)=1.

I'm pretty sure that this problem is also somehow related to Ady's Find Formula (Posted on 2012-02-17), though indirectly.

 

Edited on July 18, 2012, 2:10 pm

Posted by broll on 2012-07-18 13:37:33