Skip to content

3.19 Stirling number

Pirates/coins distribution problem
→ Weak compositions of \(k\) in \(n\) parts.

\(k = x_1 + x_2 + \dots + x_n, \quad x_i \geq 0, \quad \forall i = 1, \dots, n.\) \(\binom{n+k-1}{k}\)​

→ (Strong) composition

\(k = x_1 + x_2 + \dots + x_n, \quad x_i \geq 1, \quad \forall i = 1, \dots, n.\)

Each \(x_i\) is at least 1
Rewriting: \((x_1 - 1) + (x_2 - 1) + \dots + (x_n - 1) = k - n.\)

Using stars and bars: \(\binom{k-n+n-1}{k-n}= \binom{k-1}{k-n}= \binom{k-1}{n-1}\)​

  1. Find the number of natural solutions to the equation \(x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 60\) in each of the following cases:

    1. for every \(i = 1, \dots, 6\) we have \(x_i \geq i - 1\)​

      \(x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 60.\)

      For all \(i\), \(x_i \geq i - 1\), leading to constraints: \(x_1 \geq 0, \quad x_2 \geq 1, \quad x_3 \geq 2, \quad x_4 \geq 3, \quad x_5 \geq 4, \quad x_6 \geq 5.\)Rewriting using new variables: \((x_1 - 0) + (x_2 - 1) + (x_3 - 2) + (x_4 - 3) + (x_5 - 4) + (x_6 - 5) = 45.\)Defining: \(y_1 = x_1 - 0, \quad y_2 = x_2 - 1, \quad y_3 = x_3 - 2, \quad y_4 = x_4 - 3, \quad y_5 = x_5 - 4, \quad y_6 = x_6 - 5.\)where \(y_i \geq 0\).

      Thus the result is \(\binom{50}{5}\)​ 2. \(x_1 \geq 2, x_2 \geq 5, 2 \leq x_3 \leq 7, x_4 \geq 1, x_5 \geq 3, x_6 \geq 2\).

      \(x_1 \geq 2, \quad x_2 \geq 5, \quad 2 \leq x_3 \leq 7, \quad x_4 \geq 1, \quad x_5 \geq 3, \quad x_6 \geq 2.\)

      Solution 1:

      Count independently the number of solutions for \(x_3 = 2, 3, 4, 5, 6, 7\) and add them.

      \(\binom{60 - 13 - 2}{4}+ \binom{60 - 13 - 3}{4}+ \binom{60 - 13 - 4}{4}+ \binom{60 - 13 - 5} {4}+ \binom{60 - 13 - 6}{4}+ \binom{60 - 13 - 7}{4}\)​

      Solution 2:

      \(\# \text{Solutions with }x_{3} \geq 2 \quad - \quad \# \text{Solutions with }x_{3} \geq 8.\)​

      \(\binom{60 - 13 - 2 + 5}{5} - \binom{60 - 13 - 8 + 5}{5}\)

  2. Compute the Stirling numbers of the second kind \(S(k,2)\), \(S(k,3)\), \(S(k,k-1)\).

    Stirling numbers of the second kind

    \(S(k, n) = \# \text{ of equivalence relations on a } k\text{-element set with exactly } n \text{ equivalence classes}\)

    \(S(k, n) = S(k-1, n-1) + n S(k-1, n)\)

    For \(k\geq 1\), there are \(2^k-2\) ways to choose a non-empty subsetimage​

    Using the division principle \(S(k,2) = \frac{2^k - 2}{2} = 2^{k-1} - 1\) since this is regardless of order

    \(S(k, k-1) = \binom{k}{2}\)image​

    How about \(S(k,k-2),S(k,3)\)?

    \(S(k,k-2)=\frac{C_{k}^{2}C_{k-2}^{2}}{2}+C_{k}^{3}\)

    For \(S(k,3)\), we need to put \(k\) different elements into three boxes, recall

    Then if the boxes are different and we disregard the restriction, there are \(3^k\) ways

    But we know the boxes can not be empty which means 1. there is one box is empty 2. there are two boxes are empty cannot happen

    Thus we need to use subtraction principle

    If one box is empty, it's same with \(3S(k,2)=3\cdot2^{k-1}\)

    Then the case of \(2\) has been subtract twice, we need to add them

    If two boxes are empty, it's \(3\times 1=3\) way

    Thus we will have \(3^{k}-3\times 2^{k-1}+3\), and we know the boxes are same.

    Thus the final answer is \(\frac{3^{k}-3\times2^{k-1}+3}{6}\)​

  3. Let \(\begin{aligned} h(k,n) = \sum_{\phi: [k-n] \to [n] \atop \phi \text{ is non-decreasing}}\prod_{j=1}^{k-n}\phi(j) \end{aligned}\) . Show that \(h(k,n) = S(k,n)\).

    Examples:

    \(h(4,2) = \sum_{\phi: [2] \to [2]}\prod_{j=1}^{2}\phi(j) = 1 \cdot 1 + 1 \cdot 2 + 2 \cdot 2 = 7\) where \(\phi\) is non-decreasing.

    \(\phi(1)=1,\phi(2)=1\), \(\phi(1) = 1, \phi(2) = 2\), \(\phi(1) = 2, \phi(2) = 2\)

    \(h(4,3)=\sum_{\phi:[1]\to[3]}\prod\phi(j)=6\)

    \(\phi(1) = 1 \Rightarrow 1 + 2 + 3 = 6.\)

    image​

  4. Show that the number \(\frac{(n!)!}{(n!) ^{(n-1)!}}\) is an integer for any \(n \in \mathbb{N}\).

    multinomial coefficient

    Consider \(\binom{n!}{\underbrace{n,n,...,n}_{(n-1)!\text{ terms}}}\)​