7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The Mathematica documentation center is literally the best documentation manual I have ever seen in my entire life. There is no better way to learn Mathematica than to click Help > Wolfram Documentation and just surf through the pages and tutorials. Literally every function has an entire document filled with examples and explanations of use. There are also many tutorials for beginning to learn the software; one such page that you may find useful is located at guide/HowToTopics, which contains a list of topics which beginners should learn. $\endgroup$ – DumpsterDoofus Oct 17 '14 at 13:30
  • $\begingroup$ Also, there is a StirlingS2 function which is built-in, and which calculates Stirling numbers of the second kind. Is that what you are looking for? $\endgroup$ – DumpsterDoofus Oct 17 '14 at 13:32
  • $\begingroup$ Not quite...There are specifically special kind of Stirling Numbers called Associated Stirling Numbers which place parameters on the number of elements in a partitioned set. For example, 2-associated SN, denoted $S_2(n,k)$ partition $n$ elements into exactly $k$ subgroup with at least $2$ elements in the $k$ subgroups. The specific case with $2$ is the case I am interested in. Also, they can be denoted $S_n(n,k)=b(n,k)$ by Riordan. $\endgroup$ – Eleven-Eleven Oct 17 '14 at 13:49
8
$\begingroup$

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

table of associated Stirling numbers

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}]

plot of GF

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

plot of GF

References:

  1. L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.