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