Use combinatorics to prove $L\left(n,k\right)=\sum_{j=0}^{n}{ n\brack j}{j\brace k}$

Question

How to combinatorially prove $$L\left(n,k\right)=\sum_{j=0}^{n}{ n\brack j}{j\brace k}$$

Where $L\left(n,k\right),{ n\brack j},{j\brace k}$ denote Lah numbers, Stirling numbers of the first kind, Stirling numbers of the second kind respectively.

---

One may use the following explicit formula to derive the relation:

$${j\brace k}=\frac{1}{k!}\sum_{i=0}^{k}\binom{k}{i}\left(-1\right)^{i}\left(k-i\right)^{j}$$

However, I don't know how to prove such a relation using combinatorics.

Answer 1

Hint: Take a partition $\pi=\{B_1,\cdots ,B_k\}$ counted by the Lah number, meaning each block $B_i$ has its own ordering. Let $B_k=x_{k,1}\cdots x_{x,b_k}$ where $b_k=|B_k|$ and consider the following algorithm:

You go from left to right recording the minimal element that you see. So, for example if $B_k=2,5,3,1$ then the minimal elements recorded are $2,3,1$ from left to right. Decompose $B_k$ by taking cycles exactly on those elements, so send $B_k\mapsto (2,5)(3)(1).$ Do this for all the blocks and you will get a collection of $j$ cycles. Notice that these cycles can be represented by the minimal element of each cycle and notice that in the structure of $\pi$ each cycle belongs to a block, this induces a partition counted by ${j\brace k}$ and if we put all cycles together these induces a permutation with $j$ cycles, counted by ${n\brack j}$.

For example:

Let $\pi = 2,5,8,1,3\, |\, 4\,|\, 7,6$ then we will get $(258)(13)|(4)|(7)(6)$ by doing the algorithm and so we have a partition induced by the minimal elements of each cycle as $\{\{2,1\},\{4\},\{7,6\}\}$ and a permutation, meaning $(258)(13)(4)(7)(6).$ Notice that we can recover the ordered partition from these decomposition.

Answer 2

I am new to the forum, so please let me know how to improve my way of answering.

First, in a sequence of natural numbers $a_1 , ... ,a_n$ we say that we achieve a record at time $k = 1,...,n$, if $a_k > a_i$ for all i < k.
To clarify the equation, we look at the case $L(4,2)$. For this case, we get the following equation:
$L(4,2) ={ 4\brack 2}{2\brace 2} + { 4\brack 3}{3\brace 2} + { 4\brack 4}{4\brace 2}$.
We know, that $L(4,2)$ is the number of ways to order a 2-partition of a 4-element set. Such ordered partitions have a certain structure that can be expressed through the amount of times a record is achieved in a subset when going trough the subset from left to right. There is obviously only three different ways to distinguish all the ordered 2-partitions by their number of total records: 2 records achieved, 3 records achieved or 4 records achieved. 1 record achieved isn't possible, since we have a 2-partition and start counting records anew in each ordered subset. More than 4 isn't possible, since we only have 4 numbers. If you look closely, these three possibilities are already present in our equation: the lower left and upper right number in each summand correspond to each possibilty, while the upper left number (4) corresponds to the amount of numbers that we compare for records, and the lower right number (2) corresponds to the number of subsets in which these records might occur, and are therefore fixed.
Let's look at this more closely! First, we look at the first part of each summand in our equation, the number of ways to form cycles, so the Stirling numbers of the first kind. We can count the number of records by writing the ordered partition as a cycle. We do this by establishing a rule to start a new cycle when a new record is achieved. This can happen in two ways. Either, we encounter a new record inside of an ordered subset or we enter a new subset of our original partition, which is always a new record because we only compare for records inside of a subset. The latter part of our rule is necessary in order to distinguish between $\lbrace (4), (3,2,1) \rbrace$ and $\lbrace (4,3), (2,1) \rbrace$, which correspond to $(4)(321)$ and $(43)(21)$ consecutively. Without the latter part of the rule, they would both correspond to $(4321)$.
With this rule established, we can count the ordered partitions with k-records by the number ${ 4\brack k}$ for $k=2,3,4$. But as you might have guessed from looking at our original equation, something is missing. For example, look at the following three ordered partitions that each have 3 records:
$\lbrace (1,2), (4,3) \rbrace$,$\lbrace (1), (2,4,3) \rbrace$ and $\lbrace (2), (1,4,3) \rbrace$
They all correspond to the cycle $(1)(2)(43)$, since disjoint cycles commute. The reason is that our rule does not distinguish between breaking a cycle and achieving a new record inside of a ordered subset. So we basically need to multiply by the number of ways to achieve 3 records in a ordered 2-partition. But this is counted by distributing the 3 records into the 2 possible subsets, or to be precise, the number of ways to partition a 3-element set into two subsets, which is represented by ${3\brace 2}$. Thus, we arrive at the equation $L(4,2) ={ 4\brack 2}{2\brace 2} + { 4\brack 3}{3\brace 2} + { 4\brack 4}{4\brace 2}$. Since I have only explained the idea for $L(4,2)$, it doesn't count as a rigorous proof, although the idea holds for the general case. But I am pretty sure that there is a combinatorial proof of the underlying idea in the following paper by Kabluchko and Marynych: https://arxiv.org/pdf/2105.11365.pdf I am talking about the Combinatorial proof of Proposition 2.1 on page 6.

Regarding Phicars answer: I think you can try to come to the same conclusion by looking at minima instead of records, in a similar way that Phicar has suggested in his answer. When deciding if a new minimum has been achieved, you have to be careful to look at the numbers inside of a subset as a whole, meaning, Phicars example sequence of "$B_k = 2,5,3,1$" would not give minimal elements "$2,3,1$", but rather $2,1$, since 3 is smaller than 5, but not smaller than 2, which is the minimum of the sequence at this time. I will explain why that is necessary.
As we have seen, we can represent each ordered k-partition of a n-element set as a tuple where the first element is a cycle of n-elements and the second a set of k-sets. Two of the 36 possible ways to order a 2-partition of a 4-element set are {(1),(2,4,3)} and {(1),(3,2,4)}. If we use Phicars algorithm, these two elements would correspond to the following tuples, where the first entry is a cycle and the second a partition: [(1)(24)(3),{{1},{2,3}}] and [(1)(3)(24),{{1},{3,2}}]. But since disjoint cycles commute and the ordering in the partitions doesn't matter, these tuples are actually the same! Thus, the map is not bijective, and therefore it doesn't prove the equality. This explains why, when deciding if a new number is a minimum, we have to be careful to look at the numbers inside of a subset as a whole and not just compare successive numbers.