Multivariate Stirling Polynomials

Tutorial and Examples

Copyright © by Alfred Schreiber, 2013
Updated: 2013-10-25

Package command overview

MultivariateStirlingP1[n,k] 
	returns the multivariate Stirling polynomial (Subscript[S, n,k]) of the first kind in n-k+1 indeterminates
	
MultivariateStirlingA[n,k] 
	returns the rational function (Subscript[A, n,k]) defined by ((X[1])^(-(2n-1)))× MultivariateStirlingP1[n,k]
	
MultivariateStirlingP2[n,k] 	
	returns the multivariate Stirling polynomial (Subscript[B, n,k]) of the second kind in n-k+1 indeterminates (= partial Bell polynomial)
	
SetVariablesTo[{var1, var2, ...}]
	generates a rule set that converts indeterminates X[1], X[2],... into var1, var2,...	
	
SubIndexed[m]
	generates a special rule set that converts X[1],...,X[m] into (Subscript[X, 1]),...,(Subscript[X, m])	
	
AssociateBellPolynomial[n,k]
	returns the partial Bell polynomial (Subscript[B, n,k])(0,X[2],...,X[n+k+1])  with 0 substituted in place of X[1]
	
LahPolynomial[n,k]
	returns the multivariate Lah polynomial (Subscript[L, n,k]) in n-k+1 indeterminates
	
CauchyPolynomial[n,k]
	returns the multivariate Cauchy polynomial (Subscript[C, n,k]) in n-k+1 indeterminates

Warning

The symbol X is used as the basis letter denoting indeterminates; it is protected within this package, 
that is, you cannot change its value:

X=4;

However ...

{X[1],X[2],X[3]}/.SetVariablesTo[{-5,7}]

Read in the package file

In order to evaluate the cell below, both files "MultivariateStirlingPolynomials.m" and "MultivariateStirlingPolynomialsExamples.nb" must have been copied into your working directory.

SetDirectory[NotebookDirectory[]];
<<MultivariateStirlingPolynomials`

Something new about a classical topic

The multivariate Stirling polynomials of the first kind—as I would like to call this new class of polynomials—are closely connected to the well-known Bell polynomials. This became clear to me when I studied higher Lie derivatives of scalar functions and Faà di Bruno's chain rule.

"It would be surprising if anything new could be said about such a classical topic ..."

Huang / Marcantognini / Young: Chain Rules for Higher Derivatives. 
The Mathematical Intelligencer 28/2 (2006)

Generate Stirling polynomials of the second kind

Let's start with some well-known stuff. 
Multivariate Stirling Polynomials (MSPs) of the second kind are the same as partial Bell Polynomials ((Subscript[B, n,k])).
Here comes the Bell polynomial (Subscript[B, 6,4]):

MultivariateStirlingP2[6,4]

If you don't like the indeterminates notated as X[1],X[2],..., try this:

MultivariateStirlingP2[6,4]/.SetVariablesTo[{x,y,z}]

or that:

MultivariateStirlingP2[6,4]/.SubIndexed[6-4+1]

Replacing all indeterminates by 1, gives the sum of the coefficients:

MultivariateStirlingP2[6,4]/.SetVariablesTo[{1,1,1}]

Recall that this is a Stirling number of the second kind:

StirlingS2[6,4]

Finally, let's create a nice triangular matrix of partial Bell polynomials:

BMatrix=Table[Table[MultivariateStirlingP2[i,j],{j,1,4}],{i,1,4}];
BMatrix/.SubIndexed[4]//MatrixForm

Generate Stirling polynomials of the first kind

The polynomial family (Subscript[S, n,k]), 1≤k≤n, is —as a whole— new. 
Here comes their 5-th generation consisting of the members (Subscript[S, 5,i]) (1≤i≤5):

Table[MultivariateStirlingP1[5,i],{i,1,5}]//TableForm

Replacing every X[j] by 1, again yields Stirling numbers:

%/.SetVariablesTo[{1,1,1,1,1}]

These, however, are signed Stirling numbers of the first kind:

Table[StirlingS1[5,i],{i,1,5}]

Now, let's create an SMatrix analogous to the preceding BMatrix:

SMatrix=Table[Table[MultivariateStirlingP1[i,j],{j,1,4}],{i,1,4}];
SMatrix/.SubIndexed[4]//MatrixForm

A fundamental law of inversion

The product of both matrices comes as a surprise:

SMatrix.BMatrix//Simplify//MatrixForm

This gives evidence to the fact that (Subscript[A, n,k]):=((Subscript[X, 1])^(-(2n-1)))(Subscript[S, n,k]) and (Subscript[B, n,k]) meet a condition strongly generalizing the well-known inversion law of the Stirling numbers of the first and second kind:

AMatrix = Table[Table[MultivariateStirlingA[i, j], {j, 1, 4}], {i, 1, 4}];
AMatrix//MatrixForm

Then, the inversion law for multivariate Stirling polynomials is as follows:

AMatrix.BMatrix//Expand//MatrixForm

Of course, also the following holds:

BMatrix.AMatrix//Expand//MatrixForm

The main result

Theorem 6.1 in my paper on Multivariate Stirling Polynomials of the First and Second Kind (to appear) states that for all n≥k≥1 the following equation holds:

(Underoverscript[(Subscript[S, n,k])=∑, (                    r=k-1), (                    n-1)])(((-1))^(n-1-r))(({{2n-2-r}, {k-1}}))(Subscript[X, 1]^r)(Subscript[B, 2n-1-k-r,n-1-r])(0,X[2],...,X[n-k+1])

Let's try an instance:

n=7;k=3;
MultivariateStirlingP1[n,k]/.SubIndexed[n-k+1]
Sum[(((-1))^(n-1-r))Binomial[2n-2-r,k-1]((X[1])^r)AssociateBellPolynomial[2n-1-k-r,n-1-r],{r,k-1,n-1}]/.SubIndexed[n-k+1]//Expand

Lagrange inversion

In the special case k=1 we get the remarkable result that (Subscript[S, n,1]) can be used to invert a power series p(x)=(Subscript[a, 1])x+(Subscript[a, 2])(x^2)+(Subscript[a, 3])(x^3)+... ((Subscript[a, 1])≠ 0).  More precisely: Let (Subscript[b, n]):=((Subscript[a, 1])^(-(2n-1)))(Subscript[S, n,1])((Subscript[a, 1]),...,(Subscript[a, n])). Then, (Subscript[b, n]) is the n-th coefficient of the inverse of p(x), that is, we have (p^(-1))(x)=(Subscript[b, 1])x+(Subscript[b, 2])(x^2)+(Subscript[b, 3])(x^3)+..., where p((p^(-1))(x))=(p^(-1))(p(x))=x.

Relatives of the Bell polynomials

Whenever we replace the indeterminates X[j] in (Subscript[B, n,k]) by a multiplum (Subscript[c, j])X[j] (for all j=1,2,...,n-k+1), we obtain a polynomial closely related to the original Bell polynomials. Let's call it a relative of (Subscript[B, n,k]).

Cauchy polynomials

For (Subscript[c, j])=(j-1)! the result looks like this:

CauchyPolynomial[7,4]/.SubIndexed[7-4+1]

Why "Cauchy"?
Have, for instance, a look at the first coefficient! 105 is the number of permutations having 1 cycle of length 1 and 3 cycles of length 2. This condition is mirrored by the monomial (Subscript[X, 1]) (Subscript[X, 2]^3). Cauchy has found a famous expression that computes these numbers. Of course, the sum of all these counts the number of permutations (here: of 7 elements) consisting of 4 cycles. This is the signless Stirling number of the first kind c(7,4):

CauchyPolynomial[7,4]/.SetVariablesTo[{1,1,1,1}]

StirlingS1[7,4]

Lah polynomials

Counting linearly ordered subsets (blocks or parts of a partition) instead of cycles, gives the Lah numbers (named after Ivo Lah) as coefficients. The resulting polynomials may be called Lah polynomials. Here (Subscript[c, j])=j! for j=1,2,...,n-k+1.

LahPolynomial[6,2]

Consider the sum of all coefficients, that is: the signless Lah number corresponding to this polynomial:

LahPolynomial[6,2]/.SetVariablesTo[Table[1,{5}]]

This result is the number of ways a set of n=6 elements can be partitioned into k=2 nonempty linearly ordered subsets.
It can be simply expressed by the combinatorial term: ((n!)/(k!))(({{n-1}, {k-1}})).

n=6;k=2;
n!*Binomial[n-1,k-1]/k!

Space for your experiments