# Monotonicity of $M$-sequence

Consider the following definition in the second page of this article:

For any two integers $$k,n\ge 1$$, there is a unique way of writing $$n=\binom{a_k}{k}+\binom{a_{k-1}}{k-1}+\dots+\binom{a_i}{i}$$ so that $$a_k > a_{k-1} > \dots > a_i\geq i > 0$$. Define $$\partial_{k-1}(n) = \binom{a_k}{k-1}+\binom{a_{k-1}}{k-2}+\dots+\binom{a_i}{i-1}.$$

Is it true that when $$k$$ is fixed, the function $$\partial_{k-1}(n)$$ is weakly increasing in $$n$$? It does not look straightforward to prove this directly, but I assume it has already been shown somewhere.

• Eventually it may be strictly decreasing. Note for n less than k the d function gives a value bigger than n, and for many large n it gives a value smaller than n. Gerhard "It Needs To Reverse Somewhere" Paseman, 2019.07.04. – Gerhard Paseman Jul 4 at 16:25
• @GerhardPaseman I don't think your latter statement implies that the sequence will eventually be strictly decreasing. For example, consider the sequence $2,3,4,4,4,5,6,7,\dots$. For $n\leq 3$ the function gives a value bigger than $n$, and for $n\geq 5$ it gives a value smaller than $n$. – doe Jul 4 at 18:11
• Spellchecker. I typed increasing, and it got changed. Gerhard "Spellcheck Thinks It Is Helping" Paseman, 2019.07.04. – Gerhard Paseman Jul 4 at 18:45
• $\partial_{k-1}(n)$ is the least possible number of $(k-1)$-element faces of an (abstract) simplicial complex with $n$ $k$-element faces, as follows from Theorem 1.1 of the proposer's link. From this monotonicity is obvious. – Richard Stanley Jul 4 at 19:10

The reason is that this ordering is lexicographic. We may induct on $$k$$. The base $$k=1$$ is clear. Assume that $$n>m$$ and \begin{align*} n=\binom{a_k}{k}+\binom{a_{k-1}}{k-1}+\ldots+\binom{a_i}{i},a_k>a_{k-1}>\ldots>a_i\geqslant i,\\ m=\binom{b_k}{k}+\binom{b_{k-1}}{k-1}+\ldots+\binom{b_j}{j},b_k>b_{k-1}>\ldots>b_j\geqslant j. \end{align*} If $$a_k>b_k$$, then $$\partial_{k-1}(n)\geqslant \binom{a_k}{k-1}\geqslant \binom{b_k+1}{k-1}=\binom{b_k}{k-1}+\binom{b_k}{k-2}=\\ \binom{b_k}{k-1}+\binom{b_k-1}{k-2}+\binom{b_k-1}{k-3}=\ldots=\\ \binom{b_k}{k-1}+\binom{b_k-1}{k-2}+\binom{b_k-2}{k-3}+\ldots+\binom{b_k-k+j+1}{j}+\binom{b_k-k+j+1}{j-1}\geqslant \\ \binom{b_k}{k-1}+\binom{b_{k-1}}{k-2}+\binom{b_{k-2}}{k-3}+\ldots+\binom{b_{j+1}}{j}+\binom{b_{j+1}}{j-1}>\partial_{k-1}(m).$$ If $$a_k=b_k$$, they cancel and we use induction. If $$a_k, then $$m>n$$ by the same reasoning as above.

• Do you mean $\partial_{k-1}(m)$ instead of $\partial_{k-1}(n)$ in the last line? – doe Jul 4 at 20:30
• @doe yes, fixed – Fedor Petrov Jul 4 at 20:33

It is not hard to show that $$0 \leq \delta_{k-1}(n)-\delta_{k-1}(n-1) \leq k-1$$ and to say when each possible jump happens.

Let me first alter the notation by setting $$a_j=j+t_j.$$

For any two integers $$k,n\ge 1$$, there is a unique way of writing $$n=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+t_i}{i}$$ so that $$i \geq 1$$ and $$t_k\geq t_{k-1} \geq \dots \geq t_i\geq 0$$.

Define $$\partial_{k-1}(n) = \binom{k+t_k}{k-1}+\binom{k-1+t_{k-1}}{k-2}+\dots+\binom{i+t_i}{i-1}.$$

CLAIM: Let $$n=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+t_i}{i}>1$$ as above.

If $$t_i = 0$$ then

• $$n=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+1+t_{i+1}}{i+1}+\binom{i}{i}$$

• $$n-1=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+1+t_{i+1}}{i+1}$$

• $$\delta_{k-1}(n)-\delta_{k-1}(n-1)=i$$.

If $$t_i>0$$ then

• $$n=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+1+t_{i+1}}{i+1}+\binom{i+t_i}{i}$$

• $$n-1=\binom{k+t_k}{k}+\binom{k-1+t_{k-1}}{k-1}+\dots+\binom{i+1+t_{i+1}}{i+1}+\binom{i+t_i-1}{i}+\binom{i-1+t_i-1}{i-1}+\cdots+\binom{1+t_i-1}{1}$$

• $$\delta_{k-1}(n)-\delta_{k-1}(n-1)=0$$.

Note that if the expansion above for $$n$$ is according to the requirements then the expansion claimed for $$n-1$$ also meets the requirement. That it is actually equal to $$n-1$$ is clear in the case $$t_i=0$$ and for the case $$t_i \gt 0$$ follows from this familiar fact:

For $$a \gt i$$ and $$i \geq 1$$ we have $$\binom{a}{i}=\binom{a-1}{i}+\binom{a-2}{i-1}+\cdots+\binom{a-i}{1}+\binom{a-i-1}{0}$$ Switching to the $$t$$ notation:$$\binom{i+t}{i}=\binom{i+t-1}{i}+\binom{i-1+t-1}{i-1}+\cdots+\binom{1+t-1}{1}+1$$

That $$\delta_{k-1}(n)-\delta_{k-1}(n-1)=i$$ when $$t_i=0$$ is clear and that $$\delta_{k-1}(n)=\delta_{k-1}(n-1)$$ when $$t_i \gt 0$$ follows from writing the same fact as

$$\binom{i+t}{i-1}=\binom{i+t-1}{i-2}+\binom{i-1+t-1}{i-2}+\cdots+\binom{1+t-1}{0}$$