4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Silly question, but have you tried OEIS (oeis.org)? $\endgroup$ – Sam Hopkins Nov 6 '19 at 18:27
  • $\begingroup$ Are these connected to the numbers from your previous question mathoverflow.net/q/344887 ? $\endgroup$ – Max Alekseyev Nov 6 '19 at 21:32
  • $\begingroup$ Yes, but the relation is somewhat involved. Probably the details would harm the combinatorial argument for this part. $\endgroup$ – Luis Ferroni Nov 6 '19 at 22:27
  • $\begingroup$ To be precise, this statement is weaker than the other, but still useful for my main purpose, and it seems easier to do, given the fact I think I did a major part by guessing what it is counting. $\endgroup$ – Luis Ferroni Nov 6 '19 at 22:33
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Indeed this seems to work. I admire the fact that you actually went over it, I thought of the same approach but I got stuck almost instantaneaously. Congratulations and thank you! $\endgroup$ – Luis Ferroni Nov 12 '19 at 17:51
  • 2
    $\begingroup$ It seems like this argument was used in Corollary 3.13 of arxiv.org/abs/1911.10146v1. You should acknowledge MathOverflow, and certainly the answerer, if so. $\endgroup$ – Sam Hopkins Nov 25 '19 at 1:44
  • $\begingroup$ At the least you should answer your other positivity question (or add a link to the answer there). $\endgroup$ – esg Nov 26 '19 at 17:35
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.