Defining Associated Stirling Numbers of the Second Kind

Question

First, I'm new to Mathematica. I spent my undergraduate programming with Maple, and my computer crashed and I lost it. Fortunately, my university offers free Mathematica downloads to students, so here I am. Is there a best online source for the basics for defining functions, writing programs, etc for a novice Mathematica user?

Now, the meat and potatoes. I am investigating associated Stirling numbers of the second kind (which counts the number of ways to partition $n$ objects into exactly $j$ subsets with at least $t+1$ elements), and I want to look into generating functions for these numbers. I have seen the reference page on combinatorial functions in Mathematica which includes the Stirling numbers, Bell polynomials, etc. Does there exist a function not mentioned here that can generate these associated Stirling numbers, and if not, what is the best way to define this particular function?

Answer 1

You can define the $r$-associated Stirling numbers of the second kind with the following recurrence relation (wiki):

$$S_r(n+1, k)=k\ S_r(n, k)+\binom{n}{r-1}S_r(n-r+1, k-1)$$

The corresponding definition (with necessary special cases) in Mathematica is

ClearAll[S];
S[_, 0, 0] = 1;
S[r_, n_, 1] /; n >= r = 1;
S[r_, n_, k_] /; r > 0 && n > 0 && k > 0 && n >= k r := 
   S[r, n, k] = k S[r, n - 1, k] + Binomial[n - 1, r - 1] S[r, n - r, k - 1]
S[___] = 0;

Here I use Condition (/;) and memoization (What does the construct f[x_] := f[x] = ... mean?).

Example for $r = 2$ (it is correct^[1])

Table[S[2, n, k], {k, 6}, {n, 12}] // Grid

The generating function is^[1]

$$ \sum_{k,n\ge1}S_r(n,k)u^k\frac{t^n}{n!} = \exp[u\exp(t)(1-Q(r,t))] $$

where $Q(r,t) = \Gamma(r,t)/\Gamma(r)$ is the regularized incomplete gamma function.

Let us check it. The straightforward summation up to nmax is

ClearAll[G]
G[r_, u_, t_, nmax_] := 1 + Sum[S[r, n, k] u^k t^n/n!, {n, nmax}, {k, nmax}]

1 is written separately to avoid problems with 0^0. The exact definition is

G[r_, u_, t_] := Exp[u Exp[t] (1 - GammaRegularized[r, t])]

Plots:

Plot3D[{G[1, u, t], G[2, u, t], G[3, u, t]}, {u, -1, 1}, {t, -1, 1}]

Plot3D[{G[1, u, t, 20], G[2, u, t, 20], G[3, u, t, 20]}, {u, -1, 1}, {t, -1, 1}]

References:

1. L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.

Answer 2

Since ybeltukov already showed the usual recursive way to generate the associated Stirling numbers, let me just show that one can use the bivariate generating function from Comtet directly in SeriesCoefficient[]:

With[{r = 2}, 
     Table[n! SeriesCoefficient[Exp[u Exp[t] GammaRegularized[r, 0, t]],
                                {t, 0, n}, {u, 0, k}], {k, 6}, {n, 12}]]
   {{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {0, 0, 0, 3, 10, 25, 56, 119, 246, 501, 1012, 2035},
    {0, 0, 0, 0, 0, 15, 105, 490, 1918, 6825, 22935, 74316},
    {0, 0, 0, 0, 0, 0, 0, 105, 1260, 9450, 56980, 302995},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 945, 17325, 190575},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10395}}

Note the use of the three-argument form of the regularized incomplete gamma function.