0

I have problems with proving this equation: $$ \sum_{k=0}^n s_1(n,k)\cdot 2^{k} = (n+1)!$$ where $s_1(n,k)$ is the Stirling number of first kind.

Gary
  • 31,845
Nerwena
  • 117
  • Note that this is true if $s_1(n,k)$ denotes the unsigned Stirling numbers of first kind. What definition are you using for $s_1(n,k)$? For example, the algebraic definition trivially implies this identity. – Gary Mar 26 '20 at 09:15
  • For me it counts permutations of n - element set with k cycles. Though I'm interested in algebraic proof too. What do you mean by algebraic definition? It is that recurrence equation? – Nerwena Mar 26 '20 at 09:23
  • The algebraic definition is as follows: $$ x(x + 1) \cdots (x + n - 1) = \sum\limits_{k = 0}^n s_1 (n,k)x^k . $$ – Gary Mar 26 '20 at 09:27
  • Oh, thank you! This is birlliant, I mean it hadn't came up to my mind to use this equation with raising factorial! Everything's clear now :) – Nerwena Mar 26 '20 at 09:37

1 Answers1

1

Here’s a combinatorial proof: Given a permutation $\pi$ of $[n]$ with $k$ cycles in cycle notation, write the least element of each cycle first, then construct a permutation of $[n+1]$ by forming a cycle beginning with $n+1$ and choosing for each cycle in $\pi$, in the order of descending first (i.e. least) elements, whether to append it to the cycle. That’s $k$ independent binary choices, so $2^k$ possibilities. You get each permutation of $[n+1]$ exactly once in this way: You can go in the other direction by taking a permutation of $[n+1]$, writing it in cycle notation with $n+1$ as the first element in its cycle, and splitting that cycle at every element that’s less than all preceding elements.

joriki
  • 238,052