All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
1232 is HERE (Posted on 2012-07-18) Difficulty: 3 of 5
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).

No Solution Yet Submitted by Ady TZIDON    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips 2,3, and 4, possible approach | Comment 1 of 2

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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information