Stirling Number of the First Kind: Recurrence relation

Question

Stirling Number of the First Kind

My instructor has defined Stirling Number of the First kind as follows:

Let $n\in N,$ then a $k-$partition on $n$ is a $k$ tuple $(x_1,x_2\ldots,x_k) \;x_i \in N$ and$\;\;x_1\geq x_2 \ldots \geq x_k$ with $\sum_{i}x_i = n$

Then, the Stirling number of first kind, $s(n,k)$ denotes the number of such $k-$tuples partition on $n$.

However, after browsing the web to get more exposure on this, I couldn't find this definition. Everywhere, the Stirling Number of first kind is defined in terms of cycles, which is confusing right now.

My instructor further gave the recurrence relation followed by Stirling number of first kind as:

$s(n,k)= s(n-1,k-1) + s(n-1,k)$

I understood the above relation as follows :

In the $k-$tuple, either $x_k=1$ or $x_k \neq 1$.

Case $1$: When $x_k=1$, the remaining $(x_1,x_2,\ldots, x_{k-1})$ gives a $(k-1)-$tuple partition on $(n-1)$. So any such $k-$tuples partition on $n$ in as many ways as $(k-1)$-tuples partition on $(n-1)$ which is equal to $s(n-1,k-1)$

Case $2$: $x_k \neq 1 \rightarrow x_k \geq 2$

To achieve such $k$-tuple partition on $n$, I will first find $k-$tuple partition on $(n-1)$ [such $k-$tuples partition on $(n-1)$ in $s(n-1,k)$ ways], and then add $1$ to $x_k$. So from here I get $s(n,k)$

By rule of sum, I get the above relation.

But page on wikipedia gives a different recurrence relation

So what is the ambiguity here? Or is my recurrence relation above incorrect? If it is so, what is the problem in my argument?

Please explain in detail.

Answer 1

I think there are two major things wrong with what has been said.

The Stirling number of the first kind, $s(n,k)$, denotes the number of such $k$-tuples partition on $n$.

The standard definition of the Stirling numbers of the first kind is the number of permutations of $\{1,2,\dots,n\}$ which break into exactly $k$ disjoint cycles. No one (besides your professor) uses the Stirling number of the first kind to refer to the number of tuples $(x_1,x_2,\dots,x_k)$ with $x_1\ge x_2\ge \dots \ge x_k$ and $\sum_i x_i=n$. Wikipedia also uses that definition: for that definition, the recurrence $$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)$$ is correct.

---

However, even in your professor's definition of $s(n,k)$, the recurrence

$s(n,k)=s(n-1,k-1)+s(n-1,k)$

is incorrect. The correct recurrence is $$ s(n,k)=s(n-1,k-1)+s(n-k,k). $$ In case 2, in your post, you have $x_k\ge 2$, so all of the entries $x_i$ are at least two. If you then subtract one from each entry, you get the tuple $(x_1-1,x_2-1,\dots,x_k-1)$, whose entries are positive integers and who sum to $n-k$. This is counted by $s(n-k,k)$.

The problem with your argument is that if you start with a $k$-tuple partition of $n-1$, and then you add $1$ to $x_k$, you might violate the condition $x_{k-1}\ge x_k$. For example, $(3,1,1)$ is a $3$-tuple partition of $5$, but $(3,1,2)$ is not a valid partition of $6$, since $1\not\ge 2$.