# How can we prove this combinatorial identity?

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

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}.$$
• 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}$. Commented Apr 17, 2023 at 15:00
• 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}$. Commented Apr 17, 2023 at 15:02
• (warning: this conjecture about trees is not correct, for example, for a sequence $(1,0,2)$.) Commented Apr 17, 2023 at 15:49
• The second identity is standardly proved by counting parking functions, $k_i$ representing the number of times $n+1-i$ occurs. Commented Apr 17, 2023 at 20:12