File Exchange

## Bell Polynomials of the Second Kind

version 1.0.0.0 (2.83 KB) by Moysey Brio

### Moysey Brio (view profile)

Recursive algorithm for computing Bell polynomials of the second kind

Updated 04 Apr 2007

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

Harry Commin

### Harry Commin (view profile)

I needed to alter the code to allow for vector inputs (producing a 3D array output). It may be useful for others if this functionality were added.

Harry Commin

### Harry Commin (view profile)

I have found this very useful for implementing Faa di Bruno's formula.

I thought the function inputs were a bit confusing for this, since I don't think it's useful to restrict Nin or Kin in this case. Therefore, for the nth derivative, we just use:

B = IncompleteBellPoly(n,n,g_derivatives);

and then use B(n,k) as required.

John D'Errico

My thanks to the author for the repairs. I'll repeat my statement about how much I like the background information, references, and additional comments about incomplete Bell polynomials.

John D'Errico

In many ways, this is a model code. There are a few imperfections, although nothing to get terribly upset over. First, what did I like?

Extensive help, that describes how to use the code, as well as background for what Bell polynomials are and where they used. References are provided. There is error checking, although I was surprised that error was not used, instead using fprintf.

The things I thought could be improved were...

There is no H1 line. This is the FIRST line of the help. It is a one line description of the code, including a few useful keywords, and used by lookfor, to allow the user who perhaps forgets the name of this function and needs to find it for later use.

I also found a bug, or rather mlint found a bug in this code. When an error is generated, this code may return its variable in one path as "Outmatrix" instead of "OutMatrix". This points out the value of mlint. This and 4 other minor items were pointed out by mlint.

Finally, I'll note that this code is looped, with an internal call to nchoosek each time. This can be simply replaced and sped up by a simple computation of the coefficients, since nchoosek(n,k) and nchoosek(n,k+1) are simply related to each other.

As I said, all relatively minor flaws, and I'll happily raise my rating here that one extra notch to a 5 when corrected.

 4 Apr 2007 1.0.0.0 Incorporated user suggestions. Particularly, changes were made to the help and to the method by which errors are handled.
##### MATLAB Release Compatibility
Created with R2006b
Compatible with any release
##### Platform Compatibility
Windows macOS Linux