1
$\begingroup$

I'm aware of the connection between Pascal's triangle and the binomial theorem, and how each edge, left and right if we consider the triangle to be a graph, represents multiplying by $a$ or $b.$ But how do we relate this to combinatorics?

$\endgroup$
  • 1
    $\begingroup$ When you foil $(a+b)\cdots(a+b)$, you need to choose $k$ out of $n$ of the factors to pick an $a$ from, and the rest will be $b$s. There are $\binom{n}{k}$ ways of choosing $k$ out of $n$ things. $\endgroup$ – arctic tern Aug 25 '16 at 16:31
  • 1
    $\begingroup$ In some presentations, it's the definition of $\dbinom nk$ (whence its name of binomial coefficient). $\endgroup$ – Bernard Aug 25 '16 at 16:38
0
$\begingroup$

There are $n$ factors of $a+b$ in $(a+b)^n$ and each can contribute an $a$ or a $b$. To get the number of ways those factors can multiply to $a^kb^{n-k}$ we choose $k$ of the factors to contribute an $a$ (and the remaining $n-k$ contribute $b$). That show that there are exactly $\binom{n}{k}$ ways, so that is the coefficient.

$\endgroup$
  • 7
    $\begingroup$ what does mean : "There are $n$ factors of $a+b$ in $(a+b)^n$ and each can contribute an $a$ or a $b$" ? It's difficult to understand why an incomprehensible answer can be accepted (and upvoted) (-1) $\endgroup$ – idm Aug 25 '16 at 23:58
  • $\begingroup$ Um, it means that $(a+b)^n = \underbrace{(a+b)(a+b)\dots(a+b)}_{n \text{ times}}$ and that when multiplying, each factor contributes an $a$ or a $b$. Was that really unclear? $\endgroup$ – Michael Biro Aug 26 '16 at 1:41
3
$\begingroup$

By definition $$(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}.$$

Why this formula ? Let $A$ a set with $a$ elements and $B$ a set with $b$ element s.t. $A\cap B=\emptyset$. $(a+b)^n$ is the number of function from $\{1,...,n\}\longrightarrow A\cup B.$ But you can count them as following : The number of function that send $k$ elements of $\{1,...,n\}$ in $A$ is $$\binom{n}{k}a^kb^{n-k}$$ since you can take $k$ element from $\{1,...,n\}$ with $\binom{n}{k}$ possibilities, and each of those $k$ element has $a$ possibilities in $A$. After, the $n-k$ other are sent on $B$, and each element has $b$ possibilities in $B$. Notice that you can choose $n-k$ other element with $\binom{n-k}{n-k}=1$ possibility (in other way, you don't have the choice). If we denote $f_k$ a function that send $k$ element of $\{1,...,n\}$ in $A$ (and the other in $B$), finally, $$(a+b)^n=\sum_{k=0}^n|\{f_k:\{1,...,n\}\to A\cup B\}|=\sum_{k=0}^n\binom{n}{k}a^kb^{n-k}.$$

To finish, even if I understood what you tried to mean, to talk about the $k-$th coefficient of $(a+b)^n$ has no sense. It would have sense if you would have ask the $k-$th coefficient of $(a+b)^n$ in $\mathbb R[a]$ (or in $\mathbb R[b]$, but it's not the same coefficient).

$\endgroup$
0
$\begingroup$

Write the whole product:

$$(a+b)^n=(a+b)(a+b)\cdot\ldots\cdot(a+b)$$

To get the coefficient of $\;a^k\;$ in the above, you have to take all the possible products of $\;a\;$ with itself $\;k\;$ times, which is just the same as choosing all the subsets with $\;k\;$ elements in a set with $\;n\;$ elements, as each such subset represents just one of the above products.

$\endgroup$
0
$\begingroup$

$$(a+b)^n=\underbrace{(a+b)(a+b)\cdots(a+b)}_{\text{n times}}$$ To get a term of the form $a^kb^{n-k}$ we need to choose an $a$ out of the $n$ factors $k$ times and a $b$ out of the remaining $(n-k)$ factors $(n-k)$ times. Hence the coefficient of $a^kb^{n-k}$ in the expansion is $$\binom{n}{k}\binom{n-k}{n-k}=\binom{n}{k}$$ As an example consider $$ \begin{align} (a+b)^3 &=(a+b)(a+b)(a+b)\\ &={aaa}+{aab+aba+baa}+{abb+bab+bba}+bbb\\ &=\binom{3}{3}a^3+\binom{3}{2}a^2b+\binom{3}{1}ab^2+\binom{3}{0}a^0b^3 \end{align}$$

$\endgroup$

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.