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

 1232 is HERE (Posted on 2012-07-18)
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.)
 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
PRINT : PRINT ct: PRINT

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
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 1123211233 11234 12111 12112 12113 12121 12122 12123 12131 12132 12133 12134 1221112212 12213 12221 12222 12223 12231 12232 12233 12234 12311 12312 12313 1231412321 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 111223111231 111232 111233 111234 112111 112112 112113 112121 112122 112123 112131112132 112133 112134 112211 112212 112213 112221 112222 112223 112231 112232112233 112234 112311 112312 112313 112314 112321 112322 112323 112324 112331112332 112333 112334 112341 112342 112343 112344 112345 121111 121112 121113121121 121122 121123 121131 121132 121133 121134 121211 121212 121213 121221121222 121223 121231 121232 121233 121234 121311 121312 121313 121314 121321121322 121323 121324 121331 121332 121333 121334 121341 121342 121343 121344121345 122111 122112 122113 122121 122122 122123 122131 122132 122133 122134122211 122212 122213 122221 122222 122223 122231 122232 122233 122234 122311122312 122313 122314 122321 122322 122323 122324 122331 122332 122333 122334122341 122342 122343 122344 122345 123111 123112 123113 123114 123121 123122123123 123124 123131 123132 123133 123134 123141 123142 123143 123144 123145123211 123212 123213 123214 123221 123222 123223 123224 123231 123232 123233123234 123241 123242 123243 123244 123245 123311 123312 123313 123314 123321123322 123323 123324 123331 123332 123333 123334 123341 123342 123343 123344123345 123411 123412 123413 123414 123415 123421 123422 123423 123424 123425123431 123432 123433 123434 123435 123441 123442 123443 123444 123445 123451123452 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             23             54             155             526             2037             8778             41409             2114710            11597511            67857012            421359713            2764443714            19089932215            138295854516            1048014214717            8286486980418            68207680615919            583274220505720            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

 Search: Search body:
Forums (0)