2
$\begingroup$

Number of terms in $(a_1+a_2+a_3+\cdots+a_k)^n$ is $${n+k-1 \choose k-1}$$ I know that this is stars and bars but How does this theorem applies here ? Thank you for answering.

$\endgroup$

closed as off-topic by Guy Fsone, ahulpke, Namaste, user99914, kimchi lover Jan 27 '18 at 1:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Guy Fsone, ahulpke, Namaste, kimchi lover
If this question can be reworded to fit the rules in the help center, please edit the question.

0
$\begingroup$

Think about how to multiply out the terms. If $n=2$ (i.e., we're multiplying two groups of terms), $(a_1 + a_2 + \dots + a_k)(a_1 + a_2 + \dots + a_k) = a_1a_1 + a_1a_2 + \dots + a_1a_k + a_2a_1 + \dots + a_ka_k$. Each term come from picking one term from the first group, one from the second, and multiplying them together. If $n=3$, the terms look like $a_1a_1a_1$, $a_1a_1a_2$, etc..

In general, each term is generated by picking one term from each of the $n$ groups, so it looks like $a_1a_1a_2a_3a_3a_3a_5$ with $n$ terms total. Combining terms with the same base, this becomes$a_1^{i_1}a_2^{i_2}\cdots a_k^{i_k}$. Since each term $a_j$ is repeated $i_j$ times in the original format, and the original format had a total of $n$ terms, we have $i_1 + i_2 + \dots + i_k = n$. We have $n$ units to divide between the $k$ exponents. This should look more like classic stars and bars now: imagine we choose the $k$ exponents in the following manner. We have $n$ stars and $k-1$ bars to arrange in a line. After arranging them, we let $i_1$ be the number of stars before the first bar, $i_2$ be the number of stars between the first bar and the second bar, etc. The number of ways to arrange the stars and bars is exactly the same as the number of ways to choose the exponents.

$\endgroup$
  • $\begingroup$ Thanks again but I can't understand the first and second line. $\endgroup$ – Abbas Jan 26 '18 at 18:10
  • $\begingroup$ What do you mean by picking up $a_j$ in $n$ sums? $\endgroup$ – Abbas Jan 26 '18 at 18:11
  • $\begingroup$ @Abbas I've added an example; is it helpful? $\endgroup$ – BallBoy Jan 26 '18 at 18:14
  • $\begingroup$ I just cant understand the first thing you have metioned. ''we know that each term is in the form of....'' $\endgroup$ – Abbas Jan 26 '18 at 18:17
  • $\begingroup$ @Abbas It's a generalization of the FOIL rule (en.wikipedia.org/wiki/FOIL_method) for sums with more than two terms. Are you familiar with the FOIL rule? $\endgroup$ – BallBoy Jan 26 '18 at 18:18
0
$\begingroup$

We know that each term is in the form $$a_1^{i_1}a_2^{i_2}\cdots a_k^{i_k}$$ with $$i_1 + i_2 + \dots + i_k = n$$

thus the problem reduce to find the number of partition of n as sum of $k$ integers $\ge$ 1.

The trick to solve the problem is to consider $n+k-1$ boxes which you can fill with $k-1$ balls, with no more than one balls for each box, in this way the remaining empty boxes correspond to the partition thus we have

$${n+k-1 \choose k-1}$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.