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.)
Solution solutions Comment 2 of 2 |

Part 1:

Using a program I had previously written to assist in solving cryptograms, I found for 1234512:

ANGLIAN ANGOLAN DEGRADE ENLIVEN ESCAPES HIBACHI INSULIN LEGIBLE NEPTUNE NEURONE REQUIRE RESPIRE RESTORE STALEST STYLIST TERMITE

It found nothing for 123242526272.

The program is more complex (involving suspected vowels and consonants and already-known letters) and so is not listed here.

Part 2:

DECLARE SUB addOn ()
DEFDBL A-Z
DIM SHARED lngth, s$, ct
lngth = 4
s$ = "1"
CLS
addOn
PRINT : PRINT ct: PRINT

SUB addOn
  h$ = ""
  FOR i = 1 TO LEN(s$)
    IF MID$(s$, i, 1) > h$ THEN h$ = MID$(s$, i, 1)
  NEXT
  n = VAL(h$)
  FOR i = 1 TO n + 1
    s$ = s$ + LTRIM$(STR$(i))
    IF LEN(s$) = lngth THEN
       PRINT s$; " ";
       ct = ct + 1
    ELSE
       addOn
    END IF
    s$ = LEFT$(s$, LEN(s$) - 1)
  NEXT

END SUB

finds 15 values:

1111 1112 1121 1122 1123 1211 1212 1213 1221 1222 1223 1231 1232 1233 1234

As a bonus, for length 5, its 52 are:

11111 11112 11121 11122 11123 11211 11212 11213 11221 11222 11223 11231 11232
11233 11234 12111 12112 12113 12121 12122 12123 12131 12132 12133 12134 12211
12212 12213 12221 12222 12223 12231 12232 12233 12234 12311 12312 12313 12314
12321 12322 12323 12324 12331 12332 12333 12334 12341 12342 12343 12344 12345
and for 6, its 203 are:
111111 111112 111121 111122 111123 111211 111212 111213 111221 111222 111223
111231 111232 111233 111234 112111 112112 112113 112121 112122 112123 112131
112132 112133 112134 112211 112212 112213 112221 112222 112223 112231 112232
112233 112234 112311 112312 112313 112314 112321 112322 112323 112324 112331
112332 112333 112334 112341 112342 112343 112344 112345 121111 121112 121113
121121 121122 121123 121131 121132 121133 121134 121211 121212 121213 121221
121222 121223 121231 121232 121233 121234 121311 121312 121313 121314 121321
121322 121323 121324 121331 121332 121333 121334 121341 121342 121343 121344
121345 122111 122112 122113 122121 122122 122123 122131 122132 122133 122134
122211 122212 122213 122221 122222 122223 122231 122232 122233 122234 122311
122312 122313 122314 122321 122322 122323 122324 122331 122332 122333 122334
122341 122342 122343 122344 122345 123111 123112 123113 123114 123121 123122
123123 123124 123131 123132 123133 123134 123141 123142 123143 123144 123145
123211 123212 123213 123214 123221 123222 123223 123224 123231 123232 123233
123234 123241 123242 123243 123244 123245 123311 123312 123313 123314 123321
123322 123323 123324 123331 123332 123333 123334 123341 123342 123343 123344
123345 123411 123412 123413 123414 123415 123421 123422 123423 123424 123425
123431 123432 123433 123434 123435 123441 123442 123443 123444 123445 123451
123452 123453 123454 123455 123456

Part 3:

As shown above, a(4)=15, a(5)=52 and a(6)=203.

Part 4:

First define b(k,n) as the number of word patterns of length k using exactly n different letters.

Obviously if n>k b(k,n)=0, and b(1,1)=1 and b(0,n) = b(k,0) = 0.

b(k,n) = n*b(k-1,n) + b(k-1,n-1)

where the first term represents the repetition of some preceding letter's digit and the second term represents the concatenation of a new letter's digit.

Then,

a(k) = Sigma{i=1 to k} b(k,i)

Evaluated by:

DEFDBL A-Z
DIM b(20, 20), a(20)
b(1, 1) = 1
FOR k = 2 TO 20
 FOR i = 1 TO k
  b(k, i) = i * b(k - 1, i) + b(k - 1, i - 1)
  a(k) = a(k) + b(k, i)
 NEXT i
 PRINT k, a(k)
NEXT k

Beyond 1, the values are:

k             a(k)
2             2
3             5
4             15
5             52
6             203
7             877
8             4140
9             21147
10            115975
11            678570
12            4213597
13            27644437
14            190899322
15            1382958545
16            10480142147
17            82864869804
18            682076806159
19            5832742205057
20            51724158235372

Sloane's OEIS's A000110 (Bell or exponential numbers: ways of placing n labeled balls into n indistinguishable boxes.) extends this to

21  474869816156751 
22  4506715738447323 
23  44152005855084346 

and sets

a(n+1) = Sum a(k)*C(n,k)

 


  Posted by Charlie on 2012-07-18 14:16:21
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 (2)
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