1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jul 4 at 16:25
  • $\begingroup$ @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$. $\endgroup$ – doe Jul 4 at 18:11
  • $\begingroup$ Spellchecker. I typed increasing, and it got changed. Gerhard "Spellcheck Thinks It Is Helping" Paseman, 2019.07.04. $\endgroup$ – Gerhard Paseman Jul 4 at 18:45
  • $\begingroup$ $\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. $\endgroup$ – Richard Stanley Jul 4 at 19:10
2
$\begingroup$

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<b_k$, then $m>n$ by the same reasoning as above.

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

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}$$

$\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.