Timeline for How can we prove this combinatorial identity?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2023 at 20:12 | comment | added | Philippe Nadeau | The second identity is standardly proved by counting parking functions, $k_i$ representing the number of times $n+1-i$ occurs. | |
| Apr 17, 2023 at 15:49 | comment | added | Fedor Petrov | (warning: this conjecture about trees is not correct, for example, for a sequence $(1,0,2)$.) | |
| Apr 17, 2023 at 15:02 | comment | added | Fedor Petrov | 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}$. | |
| Apr 17, 2023 at 15:00 | comment | added | Fedor Petrov | 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}$. | |
| Apr 17, 2023 at 14:18 | history | edited | T. Amdeberhan | CC BY-SA 4.0 |
added 104 characters in body
|
| Apr 17, 2023 at 14:10 | history | edited | T. Amdeberhan | CC BY-SA 4.0 |
added 104 characters in body
|
| Apr 17, 2023 at 14:05 | history | asked | T. Amdeberhan | CC BY-SA 4.0 |