## The Statistics of Counterintelligence

How many different 5 letter 'words' can be constructed from the
letters of the word 'statistics'? (In this context a "word" isn't
necessarily an English word. It merely signifies a string of five
letters.) To answer this question, note that the word 'statistics'
defines the partition [3,3,2,1,1] of 10. Each 5-letter word must be
a sub-partition of this, meaning that 5 is split into a sum of five
non-negative parts, each no greater than the corresponding element
of the given partition of 10. These sub-partitions contribute the
following numbers of distinct words:
[3,2]: {2,1} {2,1} {5,2} = 40
[3,1,1]: {2,1} {4,2} 5!/3! = 240
[2,2,1]: {3,2} {3,1} (5) {4,2} = 270
[2,1,1,1]: {3,1} {4,3} 5!/2! = 720
[1,1,1,1,1]: {5,0} 5! = 120
-----
total = 1390
where {m,n} signifies the binomial coefficient "m choose n".
There's also a generating function for this type of problem, where the
order of the elements is important. It's call an exponential generating
function. For example, the number of 5-letter words that can be formed
from 'statistics' is the coefficient of x^5/5! in the function f(x)
defined by the product of
/ \ 2 / x^2 \ / x^2 x^3 \ 2
f(x) = ( 1 + x ) ( 1 + x + --- ) ( 1 + x + --- + --- )
\ / \ 2 / \ 2 6 /
The first squared factor corresponds to the fact that two of the
letters ('a' and 'c') can have either 0 or 1 appearance. The middle
factor signifies that one of the letters ('i') can have 0,1, or 2
appearances. The squared right-hand factor represents the fact that
two of the letters can have 0, 1, 2, or 3 appearances. Expanding
this out gives
f(x) = 1 + 5x + (23/2)x^2 + (49/3)x^3 + (193/12)x^4 + (139/12)x^5
+ (449/72)x^6 + (5/2)x^7 + (13/18)x^8 + (5/36)x^9 + (1/72)x^10
so the coefficient of x^5/5! is (139/12)(5!) = 1390. By the same
method we can compute that there are 61751760 nine-letter words that
can be formed from the letters of 'transubstantiation', and there
are 4012995 seven-letter than can be made from the letters of
'counterintelligence'.

Return to MathPages Main Menu