We would like to find the coefficient of a power of $x$ in a polynomial/series in $x$.
The importance of this will be clear when we study generating functions.
Notation: let $p(x)$ be a polynomial or a formal power series (fps) in $x$, denote by
$[x^n]p(x)$ the coefficient of $x^n$ in $p(x)$.
For example, $p(x) = x^4 - 3x^2 + 2x -1$. Then
$[x^0]p(x) = -1 \qquad [x]p(x) = 2 \qquad [x^2]p(x) = -3 \qquad [x^3]p(x) = 0$ and $[x^4]p(x) = 1$.
Here is a fundamental example involving a fps
$$\dfrac{1}{1-x} = 1 + x + x^2 + \cdots = \sum_{n \ge 0} x^n$$So, $[x^n]\dfrac{1}{1-x} = 1$ for all $n$.
Another common example involving fps is the expansion of the exponential function:
$$ e^x = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots = \sum_{n \ge 0} \frac{x^n}{n!}$$So, $[x^n](e^{x}) = \dfrac{1}{n!}$.
Here are a couple rules about the operator $[x^n]$:
$[x^n](p(x) + q(x)) = [x^n]p(x) + [x^n]q(x)$.
$[x^n](p(x)q(x)) = \sum_{i+j=n}[x^i]p(x)[x^j]q(x)$. In particular,
if $c$ is a constant, then $[x^n](cp(x)) = c[x^n]p(x)$ and
$[x^n](x^mp(x)) = [x^{n-m}]p(x)$.
The first rule is trivial. The 2nd rules is just the definition of multiplication for polynomial (series).
For example, what is the coefficient of $x^5$ in $x^3(x^4 - 3x^2 + 2x -1)$?
Well, one way to do it is multiplying out the product first, $$ x^3(x^4 - 3x^2 + 2x -1) = x^7 - 3x^5 +2x^4 -x^3 $$ so the coefficient of $x^5$ in the product $-3$.
But this is clearly an overkill if all we care is the coefficient of $x^5$.
So a better way of doing this is to ask which term in $p(x) = x^4 - 3x^2 + 2x -1$ will give a $x^5$ term when $p(x)$ is multiplied by $x^3$.
Well, since we the $x^2$ term in $p(x)$ will become the $x^5$ term in the product.
Thus, $[x^5](x^3p(x)) = [x^2]p(x) = [x^{5-3}]p(x)$
To see that the last rule is a special case of (where $q(x) = x^m$) the 2nd, note that
$[x^j](x^m) = \delta_{jm} := \begin{cases} 1 & j=m \\ 0 & j \neq m \end{cases}$
Here $\delta_{jm}$ is the Kronecker delta symbol.
and so, $$ [x^n](x^mp(x)) = \sum_{i+j = n} [x^i]p(x)[x^j](x^m) = \sum_{i+j=n} \delta_{jm}[x^i]p(x) = [x^{n-m}]p(x).$$
How are all these helping us in answering a question (in Binomial Coefficients) like:
What is the coefficient of $x^{11}$ in the expansion of $(x+2)^{17}+x^4(x+3)^{18}$?
To find the answer, we use the binomial theorem:
$$(x+y)^n = \sum_{i =0}^n \binom{n}{i}x^iy^{n-i}.$$It can be restated with the coefficient operator as:
$$\displaystyle [x^k](x+y)^n = \binom{n}{k}y^{n-k}.$$Now we can use the rules and the binomial theorem to solve the question:
Many counting problems can be convert to one of finding the coefficient of a certain degree in a series/polynomial.
Q. Find the numbers of ways that a teacher can distribute a certain number of cookies to a certain number of kids.
More generally,
How many ways are there to distribute $n$ identitical things to $k$ different people (or locations)?
Each distribution corresponds to a unique non-negative integer solution (i.e. $z_i \ge 0$ for each $i$) to the equation
$$ z_1 + z_2 + \cdots + z_k = n. $$For incidence, the solution $(1,1,5)$ of $z_1+z_2+z_3 = 7$ corresponds to the distribution that the first kid and second kid get 1 cookie each and the 3rd kids gets 5 cookies.
And the solution $(4,0,3)$ correponds to the distribution that the first kid gets 4 cookies, the 2nd kid gets none and the 3rd kid gets 3.
The fundamental observation relating solutions to $(*)$ and coefficients of power series is:
Theorem 1. The number of solutions of $(*)$ is $$[x^n](1+x+x^2+\cdots)^k = [x^n]\frac{1}{(1-x)^k}.$$
Exercise. Verify that for $n=5$ and $k=3$.
Certainly, this observation is unless for answering the original question unless we have an easier way to compute the coefficients of $\dfrac{1}{(1-x)^k}$ than expanding the series.
Luckily, we do
Theorem 2. $$[x^n]\frac{1}{(1-x)^k} = \binom{n+k-1}{n}= \binom{n+k-1}{k-1}.$$
One can prove this by a little Calculus or by "star and bar" as described in the text.
Therefore, the number of ways of distributing $n$ identical things to $k$ different people (or locations) is $\displaystyle \binom{n+k-1}{k-1}$.
Here is a cool way of viewing all this
It follows from the binomial theorem
$$ [x^n](1-x)^k = (-1)^n\binom{k}{n} $$where
$$ \binom{k}{n} = \frac{k(k-1)\cdots (k-n+1)}{n!} $$So by replacing $k$ by $-k$, we formally get
$$ \binom{-k}{n} = \frac{(-k)(-k-1)\cdots (-k-n+1)}{n!} = (-1)^n\frac{(n+k-1)\cdots (k+1)k}{n!} = (-1)^n\binom{n+k-1}{n} $$Thus,
\begin{align*} [x^n]\frac{1}{(1-x)^k} &= [x^n](1-x)^{-k} = (-1)^n\binom{-k}{n} \\ &= (-1)^n (-1)^n\binom{n+k-1}{n} = \binom{n+k-1}{n}. \end{align*}We will justify that in Notes 10.
Q 1. This time the teacher has 30 M & M's to give to $5$ kids, but she wants to make sure that each kid has at least 1 candy, how many ways can she do that?
A. Easy! To make sure each kid has at least a candy, she gives each of them one first. Now she has $30-5 = 25$ M & M's left for her to freely distribute. Hence, the answer is $\displaystyle \binom{25+5-1}{5-1}=\binom{29}{4}$.
Exercise. What if she wants to make sure each kids has at least two M & M's? How many ways she can distribute the candies?
From the algebraic POV, the answer is
$$ \begin{align*} [x^{30}](x^2 + x^3 + \cdots)^5 &= [x^{30}](x^2(1+x+x^2+\cdots))^5 \\ &= [x^{30}](x^{10})\frac{1}{(1-x)^5} = [x^{30-10}]\frac{1}{(1-x)^5}\\ &= [x^{20}]\frac{1}{(1-x)^5} = \binom{24}{4}. \end{align*} $$Q 2. Same number of M & M's but this time the teacher wants to make sure that no kids get more than $8$ candies (too many candies is a bad thing). How many ways can she do so?
A. Not so easy to count directly (one way of doing so it by PIE). However, we will let algebra to take care of things.
Since no kids get more than 8 candies, the answer should be the coefficient of $x^{30}$ in (see the fact for sums of powers
$$ \begin{align*} (1+x+x^2+\cdots+x^8)^5 &= \left(\frac{1-x^9}{1-x}\right)^5 \end{align*} $$First, according to the Binomial Theorem,
$$ (1-x^9)^5 = \binom{5}{0}x^0- \binom{5}{1}x^9 + \binom{5}{2}x^{18}-\binom{5}{3}x^{27} + \binom{5}{4}x^{36} - \binom{5}{5}x^{45} $$Second, according to Proposition 2.
$$ \frac{1}{(1-x)^5} = \cdots + \binom{7}{4}x^3 + \cdots + \binom{16}{4}x^{12} + \cdots + \binom{25}{4}x^{21} + \cdots + \binom{34}{4}x^{30}+\cdots $$So, the answer is $$ \begin{align*} \binom{5}{0}\binom{34}{4} - \binom{5}{1}\binom{25}{4} + \binom{5}{2}\binom{16}{4} - \binom{5}{3}\binom{7}{4}=976. \end{align*} $$
Q.3 How many ways to give out 30 M & M's to 5 kids so that that every kid has at least 3 M & M's but no one gets more than 8?
A. The question ask for how many solution to
$$ z_1 + z_2 + \cdots +z_5 = 30$$so that $3 \le z_i \le 8$ for each $i \in \{1,\cdots,5\}$
Note that we can solve this by combining the techniques illustrated in Q1 and Q2.
Since the number of M & M's each kid gets is between $3$ to $8$ and there are 5 kids and $30$ M & M's,
so the answer to the question is the coefficient of $x^{30}$ in $(x^3 + x^4 +x^5 + x^6+x^7+x^8)^5$
Just like Q2., using the Binomial Theorem, we get
$$ (1-x^6)^5 = \binom{5}{0}x^0- \binom{5}{1}x^6 + \binom{5}{2}x^{12}-\binom{5}{3}x^{18} + \binom{5}{4}x^{24} - \binom{5}{5}x^{30} $$And
$$ \frac{1}{(1-x)^5} = \cdots + \binom{7}{4}x^3 + \cdots + \binom{13}{4}x^9 + \cdots + \binom{19}{4}x^{15}+\cdots $$Thus,
$$ [x^{15}]\left(\frac{1-x^9}{1-x}\right)^5 = \binom{5}{0}\binom{19}{4} - \binom{5}{1}\binom{13}{4}+ \binom{5}{2}\binom{7}{4}$$A multiset is a set in which elements are allowed to be repeated. E.g. $\{a,b,b,c\}$ is a multiset of size $4$.
Formally, a multiset of elements from $A$ is a function $\mu \colon A \to \mathbb{N}$. For $x \in A$, the value $\mu(x)$ is the multiplicity of $x$.
The size of a multiset is the sum of all multiplicities, i.e. $\sum_{x \in A} \mu(x)$.
Example. The multiset $\mu \colon A:=\{a,b,\ldots, z\} \to \mathbb{N}$ defined by $\mu(a)=3, \mu(b)=1$ and $\mu(x)=0$ for all other $x \in A$ can be visualized as $\{a,a,a,b\}$.
The size is $\sum_{x \in A} \mu(x) = \mu(a) + \mu(b) + \mu(c) + \cdots + \mu(z)= 3+1 = 4$.
What is the set and the multiplicity function associate to the multiset $\{b,b,a,a\}$? What is the size? What about $\{a,b,b,b,c,c\}$?
To determine a multiset of elements from $A$, all we need is to determine the multiplicities of each $x \in A$.
Therefore the number of multiset of size $n$ whose elements are from a set of size $k$ is the same of the number of natural number solutions to equation:
$$ z_1 + z_2 + \cdots +z_k = n.$$And we have already known the answer is $\displaystyle \binom{n+k-1}{n}$.
Many seemingly different questions are actually the same when you look at them the right way. Here is an example.
When playing Yahtzee, you roll five regular 6-sided dice. How many different outcomes are possible from a single roll? The order of the dice does not matter.
The first thing to do is to write out a few possible outcomes!
For example, $\{1,3,3,4,5\}$. That means the outcome is one 1, two 3's, one 4 and one 5 (so five dice in total).
Note that $\{3,1,5,4,3\}$ is the same outcome and the order does not matter.
So what are we counting here?
Well, what determine an outcome? All we need to know is how many 1's, 2's... 6's are there in the outcome.
i.e. a multiset of size 5 (there are 5 dice) of elements coming from the set $\{1,2,3,4,5,6\}$ (each die is a regular 6-sided die).
And we have seen the number of such multisets (hence the number of possible outcomes) is
$$ \binom{5+(6-1)}{5} =\binom{10}{5}$$