Find closed formula for $S(n,n-4)$.

Question

Find closed formula for $S(n,n-4)$.

These are stirling numbers of 2nd kind.

My attempt: I uses the recurrence relation $$S(n,k)=S(n-1,k-1)+kS(n-1,k)$$

$S(n,n-4)=S(n-1,n-5)+(n-4)S(n-1,n-4)=S(n-2,n-6)+(n-5)S(n-2,n-5)+(n-4)\{S(n-2,n-5)+(n-4)S(n-2,n-4)\}$

But it seems not helpful for me.How I can find closed formula for $S(n,n-4)$?

Answer 1

Working with the recursion looks cumbersome; to use the combinatoric interpretation seems easier: $S(n,k)$ gives the ways of placing $n$ distinguishable balls in $k$ undistinguishable urns with no empty urn. Then, for $k=n-4$, we have these possible distributions:

A. {5, 1 ,1 ...} : ${n \choose 5}$

B {4, 2 ,1 ...} : ${n \choose 4}{n-4 \choose 2}$

C. {3, 3 ,1 ...} : ${n \choose 3}{n-3 \choose 3} \frac{1}{2}$

D. {3, 2 , 2, 1 ...} : ${n \choose 3}{n-3 \choose 2} {n-5 \choose 2}\frac{1}{2}$

E. {2, 2 , 2, 2, 1 ...} : ${n \choose 2}{n-2 \choose 2} {n-4 \choose 2}{n-6 \choose 2}\frac{1}{4!}$

You just need to sum all those terms to get $S(n,n-4)$, excepting (for small $n$) the terms that are impossible (or simply using the convention ${a \choose b}=0$ for $a<b$) - and perhaps try to simplify a little all that...

For example, for the first "full" case, we get:

$S(8,4)=56+ 420 +280+ 840 + 105 =1701$

Answer 2

Stirling Numbers of the Second Kind have an explicit formula:

$$S(n, k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^{n}$$

Citation: http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

Answer 3

Here is a Mathematica procedure that produces (recursively) the polynomial closed formula for $S(n,n-k)$, up to $k=klim$. It involves Bernoulli numbers and sums of powers.

ClearAll; klim = 10; Y[0, x_] = 1;
Do[SS = 0;
  Do[HH = 0;
   Do[If[n == 0, PP = p - k, 
     PP = (BernoulliB[n + 1, p - k + 1] - BernoulliB[n + 1])/(n + 1)];
     HH = HH + CoefficientList[Y[j, v + j], v][[n + 1]]*PP, {n, 0, j}];
   SS = SS - HH*BernoulliB[k - j]/Factorial[k - j]; 
   SS = Factor[SS] , {j, 0, k - 1}];
  Y[k, p_] = Factor[SS], {k, 1, klim}];

Do[Mm = 1; Do[Mm = Mm*(x - j), {j, 0, k - 1}]; Z[k, x_] = Y[k, x]*Mm;
  Print["S(", n, ",", n - k, ") = ", Z[k, n]], {k, 1, klim}]

and the outcome up to $klim=10$:

$S(n,-1+n) = \frac{(-1+n) n}{2}$

$S(n,-2+n) = \frac{(-2+n) (-1+n) n (-5+3 n)}{24}$

$S(n,-3+n) = \frac{(-3+n)^2 (-2+n)^2 (-1+n)n}{48} $

$S(n,-4+n) = \frac{(-4+n) (-3+n) (-2+n) (-1+n) n (-502+485 n-150 n^2+15 n^3)}{5760}$

$S(n,-5+n) = \frac{(-5+n)^2 (-4+n)^2 (-3+n) (-2+n) (-1+n) n (38-23 n+3 n^2)}{11520}$

$S(n,-6+n) = \frac{(-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) n}{2903040} (-152696+171150 n-73801 n^2+15435 n^3-1575 n^4+63 n^5)$

$S(n,-7+n) =\frac{(-7+n)^2 (-6+n)^2 (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) n}{5806080} (6008-5182 n+1563 n^2-198 n^3+9 n^4)$

$S(n,-8+n) = \frac{(-8+n) (-7+n) (-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) n }{1393459200}(-51360816+62333204 n-31231500 n^2+8437975 n^3-1334760 n^4+124110 n^5-6300 n^6+135 n^7)$

$S(n,-9+n) = \frac{(-9+n)^2 (-8+n)^2 (-7+n) (-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) n}{2786918400} (1234224-1249444 n+499176 n^2-101807 n^3+11265 n^4-645 n^5+15 n^6)$

$S(n,-10+n) = \frac{(-10+n) (-9+n) (-8+n) (-7+n) (-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) n}{367873228800} (-10307425152+13175306672 n-7220722828 n^2+2242194592 n^3-436886945 n^4+55598235 n^5-4634322 n^6+244530 n^7-7425 n^8+99 n^9)$

Answer 4

Here is a solution by generating functions for verification purpose until something simpler appears.

Observe that there cannot be a set of size at least six because that leaves $n-6$ items which can form at most $n-6$ sets for a total of $n-5$ sets. Similarly for a set of length seven and so on.

The species of set partitions with sets of length at most five is is $$\mathfrak{P} (\mathcal{A}_1 \mathfrak{P}_{=1}(\mathcal{Z}) + \mathcal{A}_2 \mathfrak{P}_{=2}(\mathcal{Z}) + \cdots + \mathcal{A}_5 \mathfrak{P}_{=5}(\mathcal{Z})).$$

This gives the generating function $$G(z) = \exp\left(\sum_{q=1}^5 a_q \frac{z^q}{q!}\right) = \prod_{q=1}^5 \exp\left( a_q \frac{z^q}{q!} \right).$$

Now there are several cases.

First case.
A five-set and $n-5$ fixed points. This gives the generating function $$\frac{1}{(n-5)!} \left(\frac{z}{1!}\right)^{n-5} \exp\left(a_2 \frac{z^2}{2!}\right) \exp\left(a_3 \frac{z^3}{3!}\right) \exp\left(a_4 \frac{z^4}{4!}\right) \frac{1}{1} \left(\frac{z^5}{5!}\right)^1.$$ We can drop the contributions in $a_2, a_3, a_4$ as no such sets appear because there aren't any items left over, for an answer of $$\frac{1}{(n-5)!} \left(\frac{z}{1!}\right)^{n-5} \left(\frac{z^5}{5!}\right)^1.$$

Second case.
A four-set, a two-set and $n-6$ fixed points, for a contribution of $$\frac{1}{(n-6)!} \left(\frac{z}{1!}\right)^{n-6} \left(\frac{z^2}{2!}\right)^1 \left(\frac{z^4}{4!}\right)^1.$$

Third case. Two three-sets and $n-6$ fixed points, for a contribution of $$\frac{1}{(n-6)!}\left(\frac{z}{1!}\right)^{n-6} \frac{1}{2} \left(\frac{z^3}{3!}\right)^2.$$

Fourth case. A three-set, two two-sets and $n-7$ fixed points for a contribution of $$\frac{1}{(n-7)!} \left(\frac{z}{1!}\right)^{n-7} \frac{1}{2} \left(\frac{z^2}{2!}\right)^2 \left(\frac{z^3}{3!}\right)^1.$$

Fifth case. Four two-sets and $n-8$ fixed points for a contribution of $$\frac{1}{(n-8)!}\left(\frac{z}{1!}\right)^{n-8} \frac{1}{24} \left(\frac{z^2}{2!}\right)^4.$$

Adding the contributions from these generating functions we obtain $$\frac{z^n}{(n-5)!} \times \left(\frac{1}{120} + \frac{n-5}{48} + \frac{n-5}{72} + \frac{(n-5)(n-6)}{48} + \frac{(n-5)(n-6)(n-7)}{384} \right) \\ = \frac{z^n}{(n-5)!} \times \left(\frac{1}{384} n^3 - \frac{5}{192} n^2 + \frac{97}{1152} n - \frac{251}{2880}\right).$$

Performing coefficient extraction on this we obtain the answer $$n! [z^n] \frac{z^n}{(n-5)!} \times \left(\frac{1}{384} n^3 - \frac{5}{192} n^2 + \frac{97}{1152} n - \frac{251}{2880}\right) \\ = \frac{n!}{(n-5)!} \left(\frac{1}{384} n^3 - \frac{5}{192} n^2 + \frac{97}{1152} n - \frac{251}{2880}\right).$$

This is very similar to the computation at this MSE link.

Answer 5

Derived from Leonbloy’s answer : the same reasoning provides a closed polynomial formulation for $S(n,n-k)$ in general

Let $K=\{(a_1,...,a_k)\} $ the set of all k-uples made of $k$ non-negative integers $a_j$ such that $$\sum_{j=1}^{j=k}j a_j=k$$ The elements $a\in K$ define the partitions of the integer $k$. $$\sum_{j=1}^{j=k} a_j=s(a)$$ $s(a)$ is the number of summands in the partition $a$. Then (if I am not wrong) $$S(n,n-k)=\sum_{a\in K} \frac{\prod_{j=1}^{j=k+s(a)}(n-j+1)}{\prod_{j=1}^{j=k}(j+1)!^{a_j}{a_j!}}$$ Since it comes from enumeration, each term in the sum is itself an integer-valued polynomial, with degree ranging from $k+1$ to $2k$

EDIT a similar formula has already been published: Eq.(52) in this paper.