4
$\begingroup$

This is a follow up on my earlier MO post. Let's recall the sets

$$\mathbf{K}_n=\{\mathbf{k}\in\mathbb{Z}^n: k_i\geq0, k_1+\cdots+ k_n=n, k_1+\cdots k_i\leq i, \text{for all $1\leq i\leq n$}\}$$

and $\mathcal{B}_n$: $\mathbf{t}=(t_1,\dots,t_n)\in\mathcal{B}_n$ iff $t_1>0$; $t_i\geq0$ are integers for all $i$; when $\mathbf{t}$ is read (cyclically) $t_1\rightarrow t_2\rightarrow\cdots\rightarrow t_n\rightarrow t_1$, each $t_i\neq0$ is followed by $t_i-1$ zeroes. Clearly, each $t_i\leq n$.

For example, $\mathbf{B}_4=\{4000,3001,2020,2011,1300,1201,1120,1111\}$, $\mathcal{B}_2=\{20, 11\}$ and $\mathcal{B}_3=\{300, 201, 120, 111\}$.

Notice that $\vert \mathbf{K}_n\vert=\frac1{n+1}\binom{2n}n$ and $\vert \mathcal{B}_n\vert=2^{n-1}$.

Another notation is $\#(\mathbf{t})$ stands for the number of zeroes in $\mathbf{t}\in\mathbf{B}_n$.

I would like to ask:

QUESTION. Is there a bijective or conceptual proof for the below identities? $$\sum_{\mathbf{t}\in\mathbf{B}_n}(-1)^{\#(\mathbf{t})}\binom{n}{t_1,\dots,t_n}1^{t_1}\cdots n^{t_n} =\sum_{\mathbf{k}\in\mathbf{K}_n}\binom{n}{k_1,\dots,k_n} =(n+1)^{n-1}.$$

Remark. Equality between the middle and the right-hand terms is contained in the work of Pitman and Stanley (see page 21).

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ The second identity follows from Raney lemma: if we consider the sequence $(0,k_1,k_2,\ldots,k_n)$ for every $\mathbf{k}\in \mathbf{K}_n$ and all its acyclic shifts, we get any sequence $(p_0,\ldots,p_n)$ of non-negative integers which sum up to $n$ exactly once. Thus the sum equals $\frac1{n+1}\sum {n+1\choose p_0,\ldots,p_n}=(n+1)^{n-1}$. $\endgroup$
    – Fedor Petrov
    Commented Apr 17, 2023 at 15:00
  • 1
    $\begingroup$ As for bijective proof, it seems possible that the number of trees on $\{0,1,\ldots,n\}$ with exactly $k_i$ edges from $i$ to $\{0,\ldots,i-1\}$ equals ${n\choose k_1,\ldots,k_n}$. $\endgroup$
    – Fedor Petrov
    Commented Apr 17, 2023 at 15:02
  • 1
    $\begingroup$ (warning: this conjecture about trees is not correct, for example, for a sequence $(1,0,2)$.) $\endgroup$
    – Fedor Petrov
    Commented Apr 17, 2023 at 15:49
  • $\begingroup$ The second identity is standardly proved by counting parking functions, $k_i$ representing the number of times $n+1-i$ occurs. $\endgroup$
    – Philippe Nadeau
    Commented Apr 17, 2023 at 20:12

0

Reset to default

You must log in to answer this question.