0
$\begingroup$

If $k$ and $n$ are positive integers, how do I give a simple closed form expression for the sum $\sum_{a_1+···+a_k=n} {n \choose a_1,...,a_k}$

I'm not sure the process of finding a closed form expression and I think understanding this general case will help for explicit questions like ${9 \choose a, b, c}$

$\endgroup$
3
$\begingroup$

By the multinomial theorem, the sum in question evaluates to $(1 + 1 + \cdots + 1)^n = k^n$. For $k = 2$ this reduces to the famous binomial identity $\sum_a \binom n a = 2^n$.

More explicitly: For $k = 2$ we get $\sum_a \binom n a = \sum_a \binom n a 1^a 1^{n-a} = (1+1)^n = 2^n$. And for $k = 3$ we get $\sum_{a_1+a_2+a_3 = n} \binom {n} {a_1,a_2,a_3}1^{a_1} 1^{a_2} 1^{a_3} = (1+1+1)^n = 3^n$.

$\endgroup$
  • $\begingroup$ so does that mean the closed form of i.e. $\sum_{a+b+c=7} {7 \choose a, b, c}$ is $(1+...+1)^7$ ? $\endgroup$ – user3427042 Apr 26 at 6:30
  • 1
    $\begingroup$ Yes, with $3$ $1$'s. So $3^7$. $\endgroup$ – Yakov Shklarov Apr 26 at 6:31

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.