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).
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 |
solutions
