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'.
```