#LyX 2.4 created this file. For more info see https://www.lyx.org/
\lyxformat 620
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\input defs
\usepackage{amsmath}
\end_preamble
\use_default_options true
\maintain_unincluded_children no
\language english
\language_package default
\inputencoding utf8
\fontencoding auto
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_roman_osf false
\font_sans_osf false
\font_typewriter_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement class
\float_alignment class
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_formatted_ref 0
\use_minted 0
\use_lineno 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tablestyle default
\tracking_changes false
\output_changes false
\change_bars false
\postpone_fragile_content false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\docbook_table_output 0
\docbook_mathml_prefix 1
\end_header
\begin_body
\begin_layout Standard
\begin_inset FormulaMacro
\newcommand{\stirla}[2]{\genfrac[]{0pt}{}{#1}{#2}}
{\begin{bmatrix}{\textstyle #1}\\
{\textstyle #2}
\end{bmatrix}}
\end_inset
\begin_inset FormulaMacro
\newcommand{\stirlb}[2]{\genfrac\{\}{0pt}{}{#1}{#2}}
{\begin{Bmatrix}{\textstyle #1}\\
{\textstyle #2}
\end{Bmatrix}}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc1[00]
\end_layout
\end_inset
How many combinations of
\begin_inset Formula $n$
\end_inset
things taken
\begin_inset Formula $n-1$
\end_inset
at a time are possible?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
\begin_inset Formula $\binom{n}{n-1}=\frac{n!}{1!(n-1)!}=n$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc2[00]
\end_layout
\end_inset
What is
\begin_inset Formula $\binom{0}{0}$
\end_inset
?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
\begin_inset Formula $\binom{0}{0}=\frac{1!}{1!1!}=1$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc3[00]
\end_layout
\end_inset
How many bridge hands (13 cards out of a 52-card deck) are possible?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
\begin_inset Formula $\binom{52}{13}=635013559600$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc4[10]
\end_layout
\end_inset
Give the answer to exercise 3 as a product of prime numbers.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
We have
\begin_inset Formula $\binom{52}{13}=\frac{52!}{13!39!}$
\end_inset
.
Using Equation 1.2.5.8:
\end_layout
\begin_layout Standard
\begin_inset Formula
\begin{align*}
52! & =2^{49}3^{23}5^{12}7^{8}11^{4}13^{4}17^{3}19^{2}23^{2}\cdot29\cdot31\cdot37\cdot41\cdot43\cdot47,\\
39! & =2^{35}3^{18}5^{8}7^{5}11^{3}13^{3}17^{2}19^{2}\cdot23\cdot29\cdot31\cdot37\\
13! & =2^{10}3^{5}5^{2}\cdot7\cdot11\cdot13\\
\hline \binom{52}{13} & =2^{4}5^{2}7^{2}\cdot17\cdot23\cdot41\cdot43\cdot47.
\end{align*}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
rexerc5[05]
\end_layout
\end_inset
Use Pascal's triangle to explain the fact that
\begin_inset Formula $11^{4}=14641$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
\begin_inset Formula $11^{4}=(10+1)^{4}=\binom{4}{0}10^{4}1^{0}+\binom{4}{1}10^{3}1^{1}+\binom{4}{2}10^{2}1^{2}+\binom{4}{3}10^{1}1^{3}+\binom{4}{4}10^{0}1^{4}=14641$
\end_inset
.
The pattern works for the number 11 in any given base until the number 10 or higher appears,
which in this case happens in the next row.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
rexerc6[10]
\end_layout
\end_inset
Pascal's triangle (Table 1) can be extended in all directions by use of the addition formula,
Eq.
(9).
Find the three rows that go on
\emph on
top
\emph default
of Table 1 (i.e.
for
\begin_inset Formula $r=-1$
\end_inset
,
\begin_inset Formula $-2$
\end_inset
,
and
\begin_inset Formula $-3$
\end_inset
).
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
The table is based on the properties that
\begin_inset Formula $\binom{r}{k}=\binom{r-1}{k}+\binom{r-1}{k-1}$
\end_inset
and that
\begin_inset Formula $\binom{r}{k}=0$
\end_inset
for
\begin_inset Formula $k<0$
\end_inset
.
This implies that
\begin_inset Formula $\binom{r}{0}=1$
\end_inset
for any
\begin_inset Formula $r\in\mathbb{Z}$
\end_inset
(really for any
\begin_inset Formula $r\in\mathbb{R}$
\end_inset
) and that
\begin_inset Formula $\binom{r-1}{k}=\binom{r}{k}-\binom{r-1}{k-1}$
\end_inset
(the one below in the table minus the one on the left).
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $r$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{0}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{1}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{2}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{3}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{4}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{5}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{6}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{7}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{8}$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $\binom{r}{9}$
\end_inset
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-3$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-3$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $6$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-10$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $15$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-21$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $28$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-36$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $45$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-55$
\end_inset
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-2$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-2$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $3$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-4$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $5$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-6$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $7$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-8$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $9$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-10$
\end_inset
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-1$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-1$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $1$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-1$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-1$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-1$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
1
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\begin_inset Formula $-1$
\end_inset
\end_layout
\end_inset
|
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc8[00]
\end_layout
\end_inset
What property of Pascal's triangle is reflected in the
\begin_inset Quotes eld
\end_inset
symmetry condition,
\begin_inset Quotes erd
\end_inset
Eq.
(6)?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
The symmetry of each row
\begin_inset Formula $r$
\end_inset
with center in
\begin_inset Formula $k=\frac{r}{2}$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc9[01]
\end_layout
\end_inset
What is the value of
\begin_inset Formula $\binom{n}{n}$
\end_inset
?
(Consider all integers
\begin_inset Formula $n$
\end_inset
.)
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
For
\begin_inset Formula $n\geq0$
\end_inset
,
\begin_inset Formula $\binom{n}{n}=\frac{n!}{n!1!}=1$
\end_inset
.
For
\begin_inset Formula $n<0$
\end_inset
,
by definition
\begin_inset Formula $\binom{n}{n}=0$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
rexerc10[M25]
\end_layout
\end_inset
If
\begin_inset Formula $p$
\end_inset
is prime,
show that:
\end_layout
\begin_layout Enumerate
\begin_inset Formula $\binom{n}{p}\equiv\left\lfloor \frac{n}{p}\right\rfloor \pmod p$
\end_inset
.
\end_layout
\begin_layout Enumerate
\begin_inset Formula $\binom{p}{k}\equiv0\pmod p$
\end_inset
,
for
\begin_inset Formula $1\leq k\leq p-1$
\end_inset
.
\end_layout
\begin_layout Enumerate
\begin_inset Formula $\binom{p-1}{k}\equiv(-1)^{k}\pmod p$
\end_inset
,
for
\begin_inset Formula $0\leq k\leq p-1$
\end_inset
.
\end_layout
\begin_layout Enumerate
\begin_inset Formula $\binom{p+1}{k}\equiv0\pmod p$
\end_inset
,
for
\begin_inset Formula $2\leq k\leq p-1$
\end_inset
.
\end_layout
\begin_layout Enumerate
(É.
Lucas,
1877.)
\begin_inset Formula
\[
\binom{n}{k}\equiv\binom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor}\binom{n\bmod p}{k\bmod p}\pmod p.
\]
\end_inset
\end_layout
\begin_layout Enumerate
If the representations of
\begin_inset Formula $n$
\end_inset
and
\begin_inset Formula $k$
\end_inset
in the
\begin_inset Formula $p$
\end_inset
-ary number system are
\begin_inset Formula
\begin{eqnarray*}
\begin{array}{rlc}
n & = & a_{r}p^{r}+\dots+a_{1}p+a_{0},\\
k & = & b_{r}p^{r}+\dots+b_{1}p+b_{0},
\end{array} & \text{then} & \binom{n}{k}\equiv\binom{a_{r}}{b_{r}}\cdots\binom{a_{1}}{b_{1}}\binom{a_{0}}{b_{0}}\pmod p.
\end{eqnarray*}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
We assume
\begin_inset Formula $n\in\mathbb{Z}$
\end_inset
and
\begin_inset Formula $k\in\mathbb{N}$
\end_inset
.
\end_layout
\begin_layout Enumerate
Using part 5,
\begin_inset Formula
\[
\binom{n}{p}\equiv\binom{\lfloor n/p\rfloor}{\lfloor p/p\rfloor}\binom{n\bmod p}{p\bmod p}=\binom{\lfloor n/p\rfloor}{1}\binom{n\bmod p}{0}=\left\lfloor \frac{n}{p}\right\rfloor \cdot1.
\]
\end_inset
\begin_inset Note Note
status open
\begin_layout Plain Layout
\begin_inset Note Comment
status open
\begin_layout Plain Layout
Since we know
\begin_inset Formula $\binom{n}{p}=\frac{n(n-1)\cdots(n-p+1)}{1\cdot2\cdot\cdots\cdot p}\in\mathbb{Z}$
\end_inset
(because of the addition formula),
and since
\begin_inset Formula $p$
\end_inset
appears once in the denominator,
there must be a
\begin_inset Formula $k\in\{0,\dots,p-1\}$
\end_inset
such that
\begin_inset Formula $p\mid n-k$
\end_inset
,
and it obviously must be unique.
It's then easy to see that
\begin_inset Formula $\lfloor\frac{n}{p}\rfloor=\frac{n-k}{p}$
\end_inset
,
and so
\begin_inset Formula
\[
\binom{n}{p}\equiv\left\lfloor \frac{n}{p}\right\rfloor \frac{n(n-1)\cdots(n-k+1)(n-k-1)\cdots(n-p+1)}{1\cdot2\cdots(p-1)}\pmod p.
\]
\end_inset
Let us call
\begin_inset Formula $b$
\end_inset
the numerator in the fraction of the above formula,
we just need to prove that
\begin_inset Formula $\frac{b}{(p-1)!}\equiv1\pmod p$
\end_inset
,
which by rule 1.2.4–C is equivalent to
\begin_inset Formula $b\equiv(p-1)!\bmod p!$
\end_inset
.
Since
\begin_inset Formula $b$
\end_inset
is a multiple of
\begin_inset Formula $(p-1)!$
\end_inset
(otherwise
\begin_inset Formula $\binom{n}{p}$
\end_inset
would be an integer),
\begin_inset Formula $b\equiv0\equiv(p-1)!\bmod(p-1)!$
\end_inset
,
and since
\begin_inset Formula $\{(n-j)\bmod p\}_{0\leq j0.
\end{array}\right.
\]
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc39[M10]
\end_layout
\end_inset
What is the sum
\begin_inset Formula $\sum_{k}\stirla nk$
\end_inset
of the numbers in each row of Stirling's first triangle?
What is the sum of these numbers with alternating signs?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
We can use Equation 44:
\end_layout
\begin_layout Standard
\begin_inset Formula
\begin{multline*}
\sum_{k}\stirla nk=(-1)^{-n}\sum_{k}(-1)^{n-k}\stirla nk(-1)^{k}=(-1)^{n}(-1)^{\underline{n}}=\\
=(-1)^{n}(-1)(-2)\cdots(-n)=n!,
\end{multline*}
\end_inset
\begin_inset Formula
\[
\sum_{k}\stirla nk(-1)^{k}=\sum_{k}\stirla nk(-1)^{-k}=(-1)^{-n}\sum_{k}(-1)^{n-k}\stirla nk1^{k}=(-1)^{n}1^{\underline{n}}=\delta_{n0}-\delta_{n1}.
\]
\end_inset
The first equation makes sense,
as it is the number of permutations of
\begin_inset Formula $n$
\end_inset
symbols irrespective of the number
\begin_inset Formula $k$
\end_inset
of cycles.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc42[HM10]
\end_layout
\end_inset
Express the binomial coefficient
\begin_inset Formula $\binom{r}{k}$
\end_inset
in terms of the beta function defined above.
(This gives us a way to extend the definition to all real values of
\begin_inset Formula $k$
\end_inset
.)
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
For integers
\begin_inset Formula $r\geq0$
\end_inset
and
\begin_inset Formula $k\neq0$
\end_inset
,
\begin_inset Formula
\[
\binom{r}{k}=\frac{r!}{k!(r-k)!}=\frac{\Gamma(r+1)}{\Gamma(k+1)\Gamma(r-k)}=\frac{\Gamma(r+1)}{k\Gamma(k)\Gamma(r-k+1)}=(kB(k,r-k+1))^{-1}.
\]
\end_inset
We can extend this function to the points where it is not defined by taking limits.
\end_layout
\begin_layout Standard
We are not required to evaluate the domain of this function,
but we have to see that it matches our definition for
\begin_inset Formula $r\in\mathbb{R}$
\end_inset
and
\begin_inset Formula $k\in\mathbb{Z}$
\end_inset
.
For
\begin_inset Formula $k\in\mathbb{N}$
\end_inset
,
we first see that
\begin_inset Formula
\begin{multline*}
\lim_{(x,y)\to(r,k)}\frac{\Gamma(x-y+1)}{\Gamma(x-k+1)}=\lim_{(x,y)\to(r,k)}\frac{\lim_{m}\frac{m^{x-y}m!}{(x-y+1)\cdots(x-y+m)}}{\lim_{m}\frac{m^{x-k}m!}{(x-k+1)\cdots(x-k+m)}}=\\
=\lim_{(x,y)\to(r,k)}\lim_{m}m^{k-y}\prod_{i=1}^{m}\frac{x+m-y}{x+m-k}=1,
\end{multline*}
\end_inset
where I don't remember enough of my calculus lessons to know why the last step is correct but it has to do with exchanging limits.
With this,
if we successively apply the fact that
\begin_inset Formula $\Gamma(x+1)=x\Gamma(x)$
\end_inset
,
\begin_inset Formula
\begin{multline*}
\lim_{(x,y)\to(r,k)}\frac{\Gamma(x+1)}{y\Gamma(y)\Gamma(x-y+1)}=\lim_{(x,y)\to(r,k)}\frac{x(x-1)\cdots(x-k+1)}{y\Gamma(y)\frac{\Gamma(x-y+1)}{\Gamma(x-k+1)}}=\\
=\frac{r(r-1)\cdots(r-k+1)}{k!}.
\end{multline*}
\end_inset
If
\begin_inset Formula $k\in\mathbb{Z}^{-}$
\end_inset
,
for
\begin_inset Formula $r\notin\mathbb{Z}^{-}$
\end_inset
,
\begin_inset Formula $\Gamma(r+1)$
\end_inset
is bounded in an open set around
\begin_inset Formula $(r,k)$
\end_inset
,
and since
\begin_inset Formula $\Gamma$
\end_inset
is continuous and has no zeros,
the denominator tends to infinity,
so the corresponding limit correctly evaluates to 0.
If
\begin_inset Formula $k,r\in\mathbb{Z}^{-}$
\end_inset
I can't find if the value is defined,
but if it is then its value is 0.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
exerc44[HM20]
\end_layout
\end_inset
Using the generalized binomial coefficient suggested in exercise 42,
show that
\begin_inset Formula
\[
\binom{r}{1/2}=2^{2r+1}\bigg/\binom{2r}{r}\pi.
\]
\end_inset
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
From the definition,
\begin_inset Formula
\[
\binom{r}{\frac{1}{2}}=\frac{1}{\frac{1}{2}B(\frac{1}{2},r+\frac{1}{2})}=\frac{2\Gamma(r+1)}{\Gamma(\frac{1}{2})\Gamma(r+\frac{1}{2})}.
\]
\end_inset
Now,
we know
\begin_inset Formula $\frac{\sqrt{\pi}}{2}=(\frac{1}{2})!=\frac{1}{2}\Gamma(\frac{1}{2})$
\end_inset
,
so
\begin_inset Formula $\Gamma(\frac{1}{2})=\sqrt{\pi}$
\end_inset
and
\begin_inset Formula
\[
\binom{r}{\frac{1}{2}}=\frac{2r!}{\sqrt{\pi}(r-\frac{1}{2})(r-\frac{3}{2})\cdots(\frac{1}{2})\sqrt{\pi}}=\frac{2r!2^{r}}{\pi(2r-1)(2r-3)\cdots1}.
\]
\end_inset
We see that
\begin_inset Formula $(2r)!=((2r)(2r-2)\cdots2)((2r-1)(2r-3)\cdots1)$
\end_inset
.
We already have the second factor,
and the first one is precisely
\begin_inset Formula $2^{r}r!$
\end_inset
,
so we multiply both numerator and denominator by this factor to get that
\begin_inset Formula
\[
\binom{r}{\frac{1}{2}}=\frac{2r!2^{r}2^{r}r!}{\pi(2r)!}=\frac{2^{2r+1}}{\binom{2r}{r}\pi}.
\]
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
rexerc46[M21]
\end_layout
\end_inset
Using Stirling's approximation,
Eq.
1.2.5–(7),
find an approximate value of
\begin_inset Formula $\binom{x+y}{y}$
\end_inset
,
assuming that both
\begin_inset Formula $x$
\end_inset
and
\begin_inset Formula $y$
\end_inset
are large.
In particular,
find the approximate size of
\begin_inset Formula $\binom{2n}{n}$
\end_inset
when
\begin_inset Formula $n$
\end_inset
is large.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
For large
\begin_inset Formula $x$
\end_inset
and
\begin_inset Formula $y$
\end_inset
,
\begin_inset Formula
\begin{multline*}
\binom{x+y}{y}=\frac{(x+y)!}{x!y!}\approx\frac{\sqrt{2\pi(x+y)}\left(\frac{x+y}{\text{e}}\right)^{x+y}}{\sqrt{2\pi x}\sqrt{2\pi y}\left(\frac{x}{\text{e}}\right)^{x}\left(\frac{y}{\text{e}}\right)^{y}}=\sqrt{\frac{x+y}{2\pi xy}}\left(\frac{(x+y)^{x+y}}{x^{x}y^{y}}\right)=\\
=\frac{(x+y)^{x+y+\nicefrac{1}{2}}}{\sqrt{2\pi}x^{x+\nicefrac{1}{2}}y^{y+\nicefrac{1}{2}}}=\sqrt{\frac{1}{2\pi}\left(\frac{1}{x}+\frac{1}{y}\right)}\left(1+\frac{y}{x}\right)^{x}\left(1+\frac{x}{y}\right)^{y}.
\end{multline*}
\end_inset
Then,
for large
\begin_inset Formula $n$
\end_inset
,
\begin_inset Formula
\[
\binom{2n}{n}=\frac{(2n)^{2n+\nicefrac{1}{2}}}{\sqrt{2\pi}n^{2n+1}}=\frac{2^{2n}\sqrt{2}n^{2n}\sqrt{n}}{\sqrt{2\pi}n^{2n}n}=\frac{4^{n}}{\sqrt{\pi n}}.
\]
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
rexerc48[M25]
\end_layout
\end_inset
Show that
\begin_inset Formula
\[
\sum_{k\geq0}\binom{n}{k}\frac{(-1)^{k}}{k+x}=\frac{n!}{x(x+1)\cdots(x+n)}=\frac{1}{x\binom{n+x}{n}},
\]
\end_inset
if the denominators are not zero.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
The second equality is obvious.
For the first one,
since the way the formula is written assumes
\begin_inset Formula $n\in\mathbb{N}$
\end_inset
,
we can prove this by induction.
For
\begin_inset Formula $n=0$
\end_inset
,
\begin_inset Formula
\[
\sum_{k\geq0}\binom{0}{k}\frac{(-1)^{k}}{k+x}=\frac{1}{x}=\frac{0!}{x}.
\]
\end_inset
For
\begin_inset Formula $n>0$
\end_inset
,
\begin_inset Formula
\begin{multline*}
\sum_{k\geq0}\binom{n}{k}\frac{(-1)^{k}}{k+x}=\sum_{k\geq0}\binom{n-1}{k}\frac{(-1)^{k}}{k+x}+\sum_{k\geq0}\binom{n-1}{k-1}\frac{(-1)^{k}}{k+x}=\\
=\sum_{k\geq0}\binom{n-1}{k}\frac{(-1)^{k}}{k+x}+\sum_{k\geq0}\binom{n-1}{k}\frac{(-1)^{k+1}}{k+1+x}=\frac{1}{x\binom{n-1+x}{n-1}}-\frac{1}{(x+1)\binom{n+x}{n-1}}=\\
=\frac{(n-1)!}{x(x+1)\cdots(x+n-1)}-\frac{(n-1)!}{(x+1)(x+2)\cdots(x+n)}=\frac{(n-1)!((\cancel{x+}n)\cancel{-x})}{x(x+1)\cdots(x+n)}.
\end{multline*}
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
rexerc57[M22]
\end_layout
\end_inset
Show that the coefficient
\begin_inset Formula $a_{m}$
\end_inset
in Stirling's attempt at generalizing the factorial function,
Eq.
1.2.5–(12),
is
\begin_inset Formula
\[
\frac{(-1)^{m}}{m!}\sum_{k\geq1}(-1)^{k}\binom{m-1}{k-1}\ln k.
\]
\end_inset
Also find
\begin_inset Formula $q$
\end_inset
-nomial generalizations of the fundamental identities (17) and (21).
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
The sum in Stirling's attempt is
\begin_inset Formula
\begin{eqnarray*}
S_{n} & = & \sum_{k\geq0}a_{k+1}\prod_{j=0}^{k}(n-j)=\sum_{m\geq1}a_{m}\prod_{j=0}^{m-1}(n-j)\\
& = & \sum_{m\geq1}\frac{(-1)^{m}}{m!}\left(\sum_{k\geq1}(-1)^{k}\binom{m-1}{k-1}\ln k\right)\prod_{j=0}^{m-1}(n-j)\\
& = & \sum_{k\geq1}\left(\sum_{m\geq1}(-1)^{m+k}\binom{n}{m}\binom{m-1}{k-1}\right)\ln k.
\end{eqnarray*}
\end_inset
There are several things happening in the last line.
First,
note that both sums are bounded,
for
\begin_inset Formula $m$
\end_inset
must be at most
\begin_inset Formula $n$
\end_inset
because otherwise the product would contain a factor
\begin_inset Formula $n-n=0$
\end_inset
,
and
\begin_inset Formula $k$
\end_inset
must be lower than
\begin_inset Formula $m$
\end_inset
,
and therefore lower than
\begin_inset Formula $n$
\end_inset
,
because otherwise the factor
\begin_inset Formula $\binom{m-1}{k-1}$
\end_inset
would be 0.
This allows us to swap the sums and extract a factor that only depends on
\begin_inset Formula $k$
\end_inset
.
Moreover,
\begin_inset Formula
\[
\frac{\prod_{j=0}^{m-1}(n-j)}{m!}=\frac{\prod_{j=1}^{m}(n-j+1)}{\prod_{j=1}^{m}j}=\binom{n}{m}.
\]
\end_inset
\end_layout
\begin_layout Standard
Let
\begin_inset Formula $A_{k}$
\end_inset
be the value of the inner sum for a given
\begin_inset Formula $k$
\end_inset
,
we know that
\begin_inset Formula $A_{k}=0$
\end_inset
for
\begin_inset Formula $k>n$
\end_inset
,
and if we prove that
\begin_inset Formula $A_{k}=1$
\end_inset
for
\begin_inset Formula $k\leq n$
\end_inset
,
we would have
\begin_inset Formula
\[
S_{n}=\sum_{k=1}^{n}\ln k=\ln\prod_{k=1}^{n}k=\ln n!
\]
\end_inset
\end_layout
\begin_layout Standard
Now,
we have
\begin_inset Formula
\begin{align*}
A_{k} & =\sum_{m\geq1}(-1)^{m+k}\binom{n}{m}\binom{m-1}{k-1}\\
& =\sum_{m}(-1)^{m+k}\binom{n}{m}\binom{m-1}{k-1}-(-1)^{k}\binom{-1}{k-1} & (*)\\
& =\sum_{m}(-1)^{n-m-k}\binom{n}{n-m}\binom{n-m-1}{k-1}+1 & (**)\\
& =-\sum_{m}(-1)^{n-m}\binom{n}{m}\binom{k-1-n+m}{k-1}+1 & \text{Rules B, G}\\
& =-\binom{k-1-n}{k-1-n}+1=1, & \text{Eq. (23)}
\end{align*}
\end_inset
where in
\begin_inset Formula $(*)$
\end_inset
we expand the domain of
\begin_inset Formula $m$
\end_inset
to all integers and subtract the case when
\begin_inset Formula $m=0$
\end_inset
to compensate for that (this is the only nonzero term that wasn't considered already) and in
\begin_inset Formula $(**)$
\end_inset
we change
\begin_inset Formula $m$
\end_inset
to
\begin_inset Formula $n-m$
\end_inset
.
\end_layout
\begin_layout Standard
For the second part of the exercise,
we start by writing the identities (17) and (21) in
\begin_inset Formula $q$
\end_inset
-nomial notation.
For (17),
this would be
\begin_inset Formula
\begin{eqnarray*}
\binom{r}{k,r-k}=(-1)^{k}\binom{k-r-1}{k,-r-1}, & \text{ or } & \binom{a+b}{a,b}=(-1)^{a}\binom{-b-1}{a,-(a+b)-1}.
\end{eqnarray*}
\end_inset
That is,
this allows us to change the sum on top to something resembling just one of the numbers that were on the bottom part.
To generalize this,
\begin_inset Formula
\begin{align*}
\binom{k_{1}+\dots+k_{m}}{k_{1},\dots,k_{m}} & =\binom{k_{1}+k_{2}}{k_{1}}\cdots\binom{k_{1}+\dots+k_{m}}{k_{1}+\dots+k_{m-1}}\\
& =(-1)^{k_{1}+\dots+k_{m-1}}\binom{k_{1}+k_{2}}{k_{1}}\cdots\binom{k_{1}+\dots+k_{m-1}}{k_{1}+\dots+k_{m-2}}\binom{-k_{m}-1}{k_{1}+\dots+k_{m-1}}\\
& =(-1)^{k_{1}+\dots+k_{m-1}}\binom{-k_{m}-1}{k_{1},\dots,k_{m-1},-(k_{1}+\dots+k_{m})-1}.
\end{align*}
\end_inset
We are abusing notation here,
since the book only defines multinomial coefficients for
\begin_inset Formula $k_{i}\geq0$
\end_inset
,
but we can define them for any
\begin_inset Formula $k_{i}\in\mathbb{Z}$
\end_inset
by using the property that relates them to binomial coefficients,
at the cost of symmetry with respect to the order of the
\begin_inset Formula $k_{i}$
\end_inset
.
\end_layout
\begin_layout Standard
For (21),
this would be
\begin_inset Formula
\[
\sum_{k}\binom{r}{k,r-k}\binom{s}{n-k,s-n+k}=\binom{r+s}{n,r+s-n}.
\]
\end_inset
That is,
in this case we would add up all the numbers on each component.
This clearly holds if we place
\begin_inset Formula $k,r-k$
\end_inset
and
\begin_inset Formula $n-k,s-n+k$
\end_inset
as the two last components of the multinomial coefficient.
There must be a better (less silly) generalization but I've already spent way too much time in this exercise.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
rexerc60[M23]
\end_layout
\end_inset
We have seen that
\begin_inset Formula $\binom{n}{k}$
\end_inset
is the number of combinations of
\begin_inset Formula $n$
\end_inset
things,
\begin_inset Formula $k$
\end_inset
at a time,
namely the number of ways to choose
\begin_inset Formula $k$
\end_inset
different things out of a set of
\begin_inset Formula $n$
\end_inset
.
The
\emph on
combinations with repetitions
\emph default
are similar to ordinary combinations,
except that we may choose each object any number of times.
Thus,
the list (1) would be extended to include also
\begin_inset Formula $aaa$
\end_inset
,
\begin_inset Formula $aab$
\end_inset
,
\begin_inset Formula $aac$
\end_inset
,
\begin_inset Formula $aad$
\end_inset
,
\begin_inset Formula $aae$
\end_inset
,
\begin_inset Formula $abb$
\end_inset
,
etc.,
if we were considering combinations with repetition.
How many
\begin_inset Formula $k$
\end_inset
-combinations of
\begin_inset Formula $n$
\end_inset
objects are there,
if repetition is allowed?
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
answer
\end_layout
\end_inset
We can draw a bijection between
\begin_inset Formula $k$
\end_inset
-combinations of
\begin_inset Formula $\{1,\dots,n\}$
\end_inset
with repetition and
\begin_inset Formula $k$
\end_inset
-combinations of
\begin_inset Formula $\{1,\dots,n+k-1\}$
\end_inset
without repetition by the following assignment:
\begin_inset Formula
\begin{eqnarray*}
1\leq a_{1}\leq a_{2}\leq\dots\leq a_{k}\leq n & \mapsto & 1\leq a_{1}