Skip to main content
Contents Embed Prev Up Next \(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Handout 8.2 Partitions and Newton’s Binomial Theorem
Partitions of Integers.
Definition 8.4 .
A
partition of the positive integer
\(n\) is a way of writing
\(n\) as a sum of nonincreasing positive integers.
Definition 8.5 .
A partition of a positive integer is said to be a
partition into odd parts if every term (also referred to as a
part ) in the sum is odd.
Definition 8.6 .
A partition of a positive integer is said to be a
partition into distinct parts if each integer appears in the sum at most once.
Activity 8.2.1 .
List the partitions of
\(9\text{.}\) Count the number of partitions into odd parts. Count the number of partitions into distinct parts.
Hint .
Be systematic! One way to do this is by grouping partitions by their largest part.
\begin{align*}
9\amp \amp 3\amp +3+3\\
8\amp +1 \amp 3\amp +3+2+1\\
7\amp +2 \amp 3\amp +3+1+1+1\\
7\amp +1+1 \amp 3\amp +2+2+2\\
6\amp +3 \amp 3\amp +2+2+1+1\\
6\amp +2+1 \amp 3\amp +2+1+1+1+1\\
6\amp +1+1+1 \amp 3\amp +1+1+1+1+1+1\\
5\amp +4 \amp 2\amp +2+2+2+1\\
5\amp +3+1 \amp 2\amp +2+2+1+1+1\\
5\amp +2+2 \amp 2\amp +2+1+1+1+1+1\\
5\amp +2+1+1 \amp 2\amp +1+1+1+1+1+1+1\\
5\amp +1+1+1+1 \amp 1\amp +1+1+1+1+1+1+1+1\\
4\amp +4+1 \amp \\
4\amp +3+2 \amp \\
4\amp +3+1+1 \amp \\
4\amp +2+2+1 \amp \\
4\amp +2+1+1+1 \amp \\
4\amp +1+1+1+1+1 \amp
\end{align*}
How would we write a generating function in which the coefficient on
\(x^n\) is the number of partitions of
\(n\text{?}\)
Activity 8.2.2 .
(a) Write a generating function in which the coefficient on
\(x^{n}\) is the number of partitions of
\(n\) into distinct parts.
Hint .
This is conveniently done as a product of simple generating functions.
(b) Write a generating function in which the coefficient on
\(x^{n}\) is the number of partitions of
\(n\) into odd parts.
Hint .
A convenient form is a product of rational functions, but you might want to start with a product of power series and rewrite it.
(c) Show that your generating functions above are actually equal to one another.
Hint .
\(\displaystyle (1+x^{k})\frac{1-x^{k}}{1-x^{k}}= \frac{\text{?}}{1-x^{k}}\)
Newton’s Binomial Theorem.
Definition 8.7 .
For all real numbers \(p\) and nonnegative integers \(k\text{,}\) the number \(P(p,k)\) is defined by
\(P(p,0)=1\) for all real numbers
\(p\) and
\(P(p,k) = p P(p-1,k-1)\) for all real numbers
\(p\) and integers
\(k\gt 0\text{.}\)
Definition 8.8 .
For all real numbers \(p\) and nonnegative integers \(k\text{,}\)
\begin{equation*}
\binom{p}{k}=\frac{P(p,k)}{k!}\text{.}
\end{equation*}
Activity 8.2.3 .
Compute
\(\displaystyle\binom{-9/2}{5}\text{.}\)
Theorem 8.9 . Newton’s Binomial Theorem.
For all real \(p\) with \(p\neq0\text{,}\)
\begin{equation*}
(1+x)^{p}=\sum_{n=0}^{\infty}\binom{p}{n}x^{n}\text{.}
\end{equation*}
Lemma 8.10 .
For each
\(k\geq 0\text{,}\) \(P(p,k+1)=P(p,k)(p-k)\text{.}\)
Activity 8.2.4 .
(a) Use mathematical induction to show that for all
\(k\geq 0\text{,}\) \(\displaystyle \binom{-1/2}{k}= (-1)^{k}\frac{\binom{2k}{k}}{2^{2k}}\text{.}\)
(b) Use Newton’s Binomial Theorem and the step above to write
\((1-4x)^{-1/2}\) as a formal power series in which the coefficient on
\(x^{n}\) is a binomial coefficient in which both numbers are
integers .
