Showing this formula counts these things

Question

I'm writing an article, and I got stuck trying to prove that some numbers are positive. I have a relatively good intuition for guessing what an expression is counting, but in this case I'm not being able to show the formula is right.

First of all, let's introduce this numbers $c(\ell,n,m)$ which are defined for $\ell,n\geq 0$ and $0\leq m\leq n-1$.

$$c(\ell,n,m) \doteq \sum_{j=0}^{\ell} \sum_{i=0}^{n-m-1} (-1)^{i+j} \binom{n}{j} \binom{m+\ell-j}{m} {{j}\brack{j-i}} {{n-j}\brack{m+1+i-j}}$$

(where $\binom{x}{y}=0$ if $x<0$ or $y>x$, and the same happens with the bracketed terms which are unsigned Stirling numbers of the 1st kind).

My aim is to show that they are $\geq 0$, and to that purpose I claim the following: they are counting something. Let's see what:

For a set $\{1,2,\ldots,n\}$ we can consider all its partitions into $m+1$ nonempty blocks, all of which have some order. For example, if $n=3$ and $m+1=2$, we have $6$ possible partitions into $2$ blocks with an order inside the blocks, namely:

$$\{ (1,2), (3) \}, \{(2,1),(3)\}$$ $$\{ (1,3), (2) \}, \{(3,1),(2)\}$$ $$\{ (2,3), (1)\} , \{(3,2),(1)\}$$

Indeed the number of such partitions is known as the Lah number, $L(n,m+1)$. What I'm defining is a weight on this partitions. Let's call $\pi$ a partition of $\{1,\ldots,n\}$ into $m+1$ blocks. We define the weight of $\pi$ by the following:

$$ w(\pi) = \sum_{\text{blocks of } \pi}\#\text{elements in the block that are smaller than the first in the block}$$

So, for instance, $w(\{(2,1),(3)\}) = 1 + 0$, and $w(\{(1,3),(2)\}) = 0 + 0$

My claim is that $c(\ell,n,m)$ is the number of partitions of $\{1,\ldots,n\}$ of weight $\ell$ into $m+1$ blocks. I have written a program that verifies this, and it works perfectly.

For example, in the example above, $n=3$ and $m+1=2$, we have $c(0,n,m) = 3$ and $c(1,n,m)=3$ and indeed there are three partitions of weight 1 and three of weight 2 (always in $m+1=2$ blocks, those listed above).

However, I still couldn't prove that the identity of the beginning does indeed count what I'm claiming it counts.

It's more or less easy to get some "recurrences" on this numbers, but I can't manage to deduce an alternating sign expression as such above. Probably some inclusion-exclusion argument may kill it, but I'm not being able to see it.

Also, observe that these numbers are interesting on their own, in fact, if you count the partitions of weight $0$, you just get Stirling number of the first kind. If you sum over all possible weights, you obviously get the Lah numbers.

EDIT: As no one has said anything so far, I add a possible approach: it is easy to see that for any partition of weight $\ell$ we can produce some partitions of weight $\ell+1$ according to the number of blocks that we can use to increase the weight by one (by swapping the element on the top with the following in size). That gives a recurrence, but I'm not being able to see how to produce the alternating sign and the expression I propose.

Answer 1

Here is a proof using (formal) generating functions. The Lah number $L(n,m+1)$ $$L(n,m+1)=\frac{n!}{(m+1)!}[x^n] \bigg(\frac{x}{1-x}\bigg)^{m+1}$$ counts the number of unordered partitions of the set $\{1,\ldots,n\}$ into $m+1$ nonempty, linearly ordered "blocks". Above $\frac{x}{1-x}=\sum_{k\geq 1} x^k$ is the exponential generating function (egf) for sequences. Let $s$ be an ordinary marker for weight. To get the bivariate generating function (with $s$ marking the weight) we should replace $x^k$ with $\frac{x^k}{k}(1+s+\ldots+s^{k-1})$. (Since $(k-1)!$ of the $k!$ orderings of $\{1,\ldots,k\}$ have first element $w+1$, i.e. weight $w$, and get marked with $s^w$.)

Recall further that the egf for the Stirling numbers of the first kind is given by $ { n\brack k} =n! [x^n] \frac{\left(\log(\frac{1}{1-x})\right)^k}{k!}$.

Now, replacing $\frac{x}{1-x}$ with $\sum_{k\geq 1} \frac{x^k}{k}(1+\dots +s^{k-1})=\frac{\log(\frac{1}{1-x})-\log(\frac{1}{1-sx})}{1-s}$ and extracting coefficients gives \begin{align*}%c(\ell,n,m) &\frac{n!}{(m+1)!}\,[s^\ell x^n]\Bigg(\frac{\log(\frac{1}{1-x})-\log(\frac{1}{1-sx})}{1-s}\Bigg)^{m+1}\\ &=\frac{n!}{(m+1)!}\,[s^\ell x^n]\frac{1}{(1-s)^{m+1}}\sum_{k=0}^{m+1} {m+1 \choose k}(-1)^k\big (\log(\frac{1}{1-x})\big)^{m+1-k} \big(\log(\frac{1}{1-sx})\big)^k\\ &=n!\,[s^\ell x^n]\frac{1}{(1-s)^{m+1}}\sum_{k=0}^{m+1}(-1)^k\Bigg(\frac{\big (\log(\frac{1}{1-x})\big)^{m+1-k}}{(m+1-k)!}\Bigg) \Bigg(\frac{\big(\log(\frac{1}{1-sx})\big)^k}{k!}\Bigg)\\ &=n!\,[s^\ell]\frac{1}{(1-s)^{m+1}}\sum_{k=0}^{m+1}(-1)^k\sum_{j=0}^n [x^{n-j}]\Bigg(\frac{\big (\log(\frac{1}{1-x})\big)^{m+1-k}}{(m+1-k)!}\Bigg) [x^j]\Bigg(\frac{\big(\log(\frac{1}{1-sx})\big)^k}{k!}\Bigg)\\ &=[s^\ell]\frac{1}{(1-s)^{m+1}}\sum_{k=0}^{m+1}\sum_{j=0}^n (-1)^k {n\choose j}s^j {j \brack k} {n-j \brack m+1-k}\\ &=\sum_{k=0}^{m+1}\sum_{j=0}^n (-1)^k {n\choose j}{m+\ell-j \choose m} {j \brack k} {n-j \brack m+1-k}\\ &=\sum_{j=0}^{\ell}\;\;\sum_{k=m+1-n+j}^j (-1)^k {n\choose j}{m+\ell-j \choose m} {j \brack k} {n-j \brack m+1-k}\\ &=\sum_{j=0}^{\ell}\;\;\sum_{i=0}^{n-m-1} (-1)^{j-i} {n\choose j}{m+\ell-j \choose m} {j \brack j-i} {n-j \brack m+1-j+i}\\ &=c(\ell,m,n) \end{align*} This shows both: your interpretation is correct, and the $c(\ell,n,m)$ are nonnegative.

Answer 2

Too long for a comment, but not an answer.

Denote by $A(\ell,n,m)$ the set of partitions of $\{1,\dots,n\}$ of weight $\ell$ into $m+1$ blocks, $f(\ell,n,m)=|A(\ell,n,m)|$. They are of two types:

1) $1$ is not the first element in its block. Such partitions are obtained by taking $A(\ell-1,n-1,m)$ (well, for the set $\{2,3,\ldots,n\}$) and inserting 1 to any of $n-1$ possible positions. So here we get $(n-1)f(\ell-1,n-1,m)$ partitions.

2) $1$ is the first element of its block. We should fix the other elements of this block, let $k\in \{0,1,\ldots,n-1\}$ be the number of other elements of the block, then the block may be fixed by $\frac{(n-1)!}{(n-k-1)!}$ ways, other $n-k-1$ elements should be partitioned onto $m$ blocks with weight $\ell$, thus we get $$\sum_{k=0}^{n-1}\frac{(n-1)!}{(n-k-1)!}f(\ell,n-k-1,m-1)$$ partitions.

Therefore (denoting $n-k-1=s$) we get a recurrence $$f(\ell,n,m)=(n-1)f(\ell-1,n-1,m)+\sum_{s=0}^{n-1}\frac{(n-1)!}{s!}f(\ell,s,m-1), \,\, (1)$$

replacing $n$ to $n-1$ we get $$f(\ell,n-1,m)=(n-2)f(\ell-1,n-2,m)+\sum_{k=0}^{n-2}\frac{(n-2)!}{s!}f(\ell,s,m-1).$$ Multiplying by $(n-1)$ and subtracting from (1) we get a recurrence with finitely many terms: $$ f(\ell,n,m)=(n-1)f(\ell-1,n-1,m)+(n-1)f(\ell,n-1,m)-\\(n-1)(n-2)f(\ell-1,n-2,m) +f(\ell,n-1,m-1). $$

So it remains to prove the same recurrence for $c(\ell,n,m)$. I guess it may be easier to do if interpret $c(\ldots)$ as coefficients or whatever they come from. For your expression with double sum, I would try use the recurrences like $\binom{n}k=\binom{n-1}k+\binom{n-1}{k-1}$, $k\binom{n}k=n\binom{n-1}{k-1}$, ${n\brack k}={n-1\brack k-1}+(n-1){n-1\brack k}$ many times and rearranging the terms.After several trials this should work.