NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/sci/math/10275

Internet Message Format | 1992-08-14 | 3.2 KB

Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!netnews.upenn.edu!netnews.noc.drexel.edu!king.mcs.drexel.edu!dmagagno
From: [e-mail] (David Magagnosc)
Newsgroups: sci.math
Subject: Re: Still another problem.
Message-ID: <[e-mail]>
Date: 14 Aug 92 14:21:49 GMT
References: <[e-mail]> <[e-mail]>
Organization: Drexel University
Lines: 82

In article <[e-mail]> [e-mail] (Peter Marksteiner) writes:
>Bill Taylor writes:
>
>
>>Prove that
>>
>>               n     n     n    n
>>     1  /     2     3     4    5        \
>>     - |  1 + -- +  --  + -- + -- +....  |
>>     e  \     1!    2!    3!   4!       /
>>
>>  is an integer for all positive integer n.
>
>Define a differential operator D = (d/dx x), i.e. multiply by x and
>differentiate.  Apply this operator n times to exp(x). It is easy to see
>that the result is exp(x) times a polynomial in x with integer coefficients.
>By expanding exp(x) in powers of x we see that it is also equal to
>
>            n       n        n       n
>           2       3   2    4   3   5   4
>       1 + -- x +  -- x   + -- x  + -- x  +....
>           1!      2!       3!      4!
>
>Now take x=1, and the result follows.
>
>             Peter Marksteiner
>             Vienna University Computer Center
>             [e-mail]

This is a very nice proof, but I will say that I am a little surprised
that no one has posted the (correct) value.  Since it follows very
easily from this approach, permit me to summarize.

Let

    D^(n)(exp(x)) = p_n(x) exp(x)

define the polynomials p_n(x).  Then p_n(x) is the sum of terms

    S(n,i+1) x^i

where S(n,i) are the Stirling numbers of the second kind, equal
to the number of partitions of an n element set into i (nonempty)
subsets.  Setting  x = 1,  we see that the desired value is the
number of ways of partitioning an  n+1  element set into any number
of subsets.  The sequence begins  1, 2, 5, 15, 52, ...

To verify the form of the p_n(x), we may construct a recurrence
relation using the operator D and compare it to the known relation
for S(n,i).  Alternatively, we may explicitly determine the
coefficient of  x^m / m!  in the product  q_n(x) exp(x), where
q_n(x) is the polynomial with the Stirling coefficients (and we
want to see that p_n = q_n).  This coefficient is the sum of terms

    (m+1)! S(n+1,i+1) / (m-i)! (m+1)

each of which is the number of functions from an  n+1  element set
to an  m+1  element set with the size of the range equal to  i+1,
divided by  m+1.  Summing, this is then total number of functions
from an  n+1  element set to an  m+1  element set, divided by  m+1,
or
    (m+1)^(n+1) / (m+1) = (m+1)^n

Since this agrees with the coefficients in the original,  q_n = p_n,
and the result follows.


While we're at it, prove that the following sum is always an
integer:

     n    n    n    n
    1    2    3    4
    -- + -- + -- + -- + ...
     1    2    3    4
    2    2    2    2

and find reasonable generalizations.

D. Magagnosc
--
496620796F752063616E207265616420746869732C20796F752063616E206265636F6D65206120
636F6D70757465722070726F6772616D6D657220616E6420676574206120676F6F64206A6F622E