Skip to main content
3 of 3
Add details for one of the question.
Honglu
  • 1.1k
  • 6
  • 16

A combinatorial identity

I hope this is a suitable MO question. In a research project, my collaborator and I came across some combinatorial expressions. I used my computer to test a few numbers and the pattern was suggesting the following equation for fixed integers $K\geq n>0$.

$$\dfrac{K!}{n!K^{K-n}}\sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!}=\displaystyle {K-1\choose n-1}.$$

We tried to think of a proof but failed. One can probably move these $K!, n!$ to the right and rewrite the RHS, or maybe move $K!$ into the summation to form combinatorial numbers like $K\choose k_1,k_2,\dotsc,k_n$. We don't know which is better.

The questions are:

  1. Anyone knows a proof for this identity?
  2. In fact the expression that appears in our work is $\sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \sigma_p(k_1,\dotsc,k_n) \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!}$, where $p$ is a fixed integer and $\sigma_p(\dotsc)$ is the $p$-th elementary symmetric polynomial. The equation in the beginning simplifies this expression for $p=0,1$. Is there a similar identity for general $p$?

----------Update----------

Question 2 is perhaps too vague, and I'd like to make it a bit more specific. Probably I should have written this down in the beginning, but I feared this is too long and unmotivated. But after seeing people's skills, I'm very tempted to leave it here in case somebody has remarks. In fact, question 2 partly comes from the effort to find a proof for the following (verified by computer).

$$ \frac{1}{K!} \prod_{r=1}^{K} (r+1 -x)= \sum_{n=1}^K \frac{(-1)^n}{n!} \left[ \sum_{p=0}^n K^{n-p} \prod_{r=1}^p (x +r-4) \left( \sum\limits_{ \begin{subarray}{c} k_1+\dotsb+k_{n}=K \\ k_i \geq 1 \end{subarray}} \sigma_p(k_1,\dotsc,k_{n}) \prod\limits_{i=1}^n \dfrac{k_i^{k_i-2}}{(k_i-1)!} \right) \right], $$ Where $x$ is a fixed number (in our case, an integer).

Honglu
  • 1.1k
  • 6
  • 16