Bell Polynomials of the Second Kind

Recursive algorithm for computing Bell polynomials of the second kind

Purpose:
Given a list of input values (x_{1},x_{2},...,x_{N}), the script returns a matrix of Bell polynomials B_{n,k} for n=0,...,N and k=0,...,K.

Syntax:
OutMatrix = IncompleteBellPoly(Nin,Kin,DataList)
where
B_{n,k} = OutMatrix(n+1,k+1)
n=0,...,Nin
k=0,...,Kin (Kin<=Nin)
DataList = (x_{1},x_{2},...,x_{Nin})

Latest Modification Date:
April 3, 2007

Discussion:
Given Taylor expansion coefficients of a function g(t) {g_{0},g_{1},g_{2},...} with g_{0}=0,
B_{n,k}(g_{0},g_{1},...,g_{n-k+1}) is the nth Taylor coefficient of the kth derivative of g(t)/(k!) in terms of {g_{0},g_{1},g_{2},...}
\frac{1}{k!} g^{k}(t) = \sum_{n=0}^{\infty} B_{n,k} \frac{t^{n}}{n!}

The Bell polynomials can be computed efficiently by a recursion relation
B_{n,k} = \sum_{m=1}^{n-k+1} \binom{n-1}{m-1} g_{m} B_{n-m,k-1}
where
B_{0,0} = 1;
B_{n,0} = 0; for n=>1
B_{0,k} = 0; for k=>1

The coefficients can be stored in a lower triangular matrix. The elements of the kth column are the Taylor coefficients of the kth derivative of g(t)/k!.

In application, the polynomials arise in multiple contexts in combinatorics. They also can be found in Riordan's formulation of di Bruno's formula for computing an arbitrary order derivative of the composition of two functions
\frac{d^{n}}{dt^{n}} g(f(t)) = \sum_{k=0}^{n} g^{k}(f(t)) B_{n,k}(f^{1}(t),f^{2}(t),...,f^{n-k+1}(t))

Script Check:
If DataList=1 for all entries, B_{n,k} = S(n,k) = Stirling number of the second kind for (n,k)

Failure Return:
OutMatrix is undefined if the code fails. An error statement is issued and the function exits.

References:
Ferrell S. Wheeler, Bell Polynomials, ACM SIGSAM Bulletin, vol. 21, issue 3, pp.44-53, 1987.

Warren P. Johnson, The curious history of Faa di Bruno's formula, The American mathematical monthly, vol. 109, no. 3, pp. 217-234, March 2002.

http://en.wikipedia.org/wiki/Bell_polynomials