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.