Classical combinatorial numbers · Definition

Stirling number of the first kind

enumerative combinatoricsclassical combinatorial numbers

Before you start you need to know

They arise when expanding products of linear factors and when counting cycles in permutations. They connect polynomial algebra with counting combinatorics.

Definition

The Stirling number of the first kind \(c(n,k)\) counts the permutations of \(n\) elements that have exactly \(k\) cycles.

\[x(x+1)\cdots(x+n-1)=\sum_{k=0}^{n} c(n,k)\,x^{k}\]

They satisfy \(c(n,n)=1\), \(c(n,0)=0\) for \(n\ge 1\), and \(c(n,1)=(n-1)!\), and the entries of each row sum to \(n!\). They obey the recurrence \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\) with \(c(0,0)=1\).

For \(n=3\), the permutations with a single cycle are the two 3-cycles, so \(c(3,1)=2\). Two cycles occur in three ways, a transposition plus a fixed point, so \(c(3,2)=3\); and the identity gives \(c(3,3)=1\).

A common mistake is confusing them with Stirling numbers of the second kind, which count partitions into nonempty blocks. The two families can agree on small values but not in general, so always check the definition.

Think about it

Why is \(c(n,k)=0\) when \(k>n\)?

Each cycle contains at least one element and the cycles are disjoint, so there cannot be more cycles than elements.

Exercises 10

  1. What does the number \(c(n,k)\) count?
  2. The permutations of \(\{1,2,3\}\) with a single cycle are the 3-cycles. What is \(c(3,1)\)?
  3. What is \(c(n,n)\) for every \(n\ge 1\)?
  4. What is \(c(n,0)\) for \(n\ge 1\)?
  5. What is \(c(n,1)\)?
  6. Use \(c(4,1)=6\), \(c(4,2)=11\), \(c(4,3)=6\) and \(c(4,4)=1\). What is the sum of the row \(n=4\)?
  7. With \(c(4,2)=11\) and \(c(4,1)=6\), use \(c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)\) to find \(c(5,2)\).
  8. Expand \(x(x+1)(x+2)=\sum_k c(3,k)\,x^k\). What is \(c(3,2)\)?
  9. Using the row \(n=4\), where \(c(4,1)=6\), \(c(4,2)=11\), \(c(4,3)=6\) and \(c(4,4)=1\), compute \(\sum_{k=1}^{4} k\,c(4,k)\).
  10. A claim says \(c(n,k)=c(n-1,k-1)+c(n-1,k)\) always holds. For which pair \((n,k)\) does the equality actually hold?

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.