# Assignments for Discrete Mathematics 離散數學作業

### ==Please explain each term in your solution precisely.==
### ==請精準解釋解題過程中的每一算式/項== (有多項時可善用 $1, 2, ... , n$ 的表示法：解釋第1項, 解釋第2項, ... , 解釋第$n$項) ==所附解答並未各項解釋，凡需要時，請自行完成之==。
---
## Chapter 1. Fundamental Principles of Couting (計數的基本原理)
## [作業一]
### 1. ($\S 1.1\ \sharp 3$)
$Buick\ automobiles\ come\ in\ four\ models,\ 12\ colors,\ three\ engine\ sizes,\ and\ two\ transmission\ types.$
$(a)How\ many\ distinct\ Buicks\ can\ be\ manufactured?$
$(b)\ If\ one\ of\ the\ available\ colors\ is\ blue,\ how\ many\ different\ blue\ Buicks\ can\ be\ manufactured?$
:::spoiler 中文
$Buick\ (別克)汽車有4個型號、12種顏色、3種引擎尺寸和2種變速器類型。$
$(a)\ 有多少種不同的Buick汽車可以製造$？
$(b)\ 如果指定顏色是藍色，那麼有多少種不同的Buick汽車可以製造$？
:::
:::spoiler solution
$(a)\ By\ the\ product\ of\ rule:\ \ 4\times12\times3\times2=288$
$(b)\ 4\times3\times2=24$
:::
### 2. ($\S 1.1\ \sharp 20$)
$Over\ the\ Internet,\ data\ are\ transmitted\ in\ structured\ blocks\ of\ bits\ called\ datagrams.$

$(a)\ In\ how\ many\ ways\ can\ the\ letters\ in\ DATAGRAM\ be\ arranged?$
$(b)\ For\ the\ arrangements\ of\ part\ (a),\ how\ many\ have\ all\ three\ A's\ together.$

:::spoiler 中文
$(a) 有多少種方式可以排列$ "$DATAGRAM$"？
$(b) 如果三個A必須在一起，有多少種排列方式$？
:::

:::spoiler solution
$(a)\ \dfrac{8!}{3!}=6720, since\ there\ are\ 3\ A's.$
$(b)\ 6!=720, regarding\ the\ 3\ A's\ as\ a\ unique\ symbol.$
:::
### 3. ($\S 1.2\ \sharp 32$)
[Original statement] If $n$ and $k$ are positive integers with
$n=3k$, then $n!/(3!)^k$ is an integer.
:::spoiler 中文
若 $n = 3k$，則 $\displaystyle\frac{n!}{(3!)^k}$ 必為整數，其中 $k$ 為正整數。 ($\displaystyle\frac{n!}{3^k}$ 亦為整數)
:::
:::spoiler proof
考慮 $x_1, x_1, x_1, x_2, x_2, x_2, ... , x_k, x_k, x_k$ 為 $k$ 組相異物件，每組重複三個，總個數為 $n$；<br> 這 $n$ 個(含重複)物件的排列個數為：$\alpha =\displaystyle\frac{n!}{(3!)(3!)...(3!)} = \frac{n!}{(3!)^k} = \frac{n!}{(3\times 2\times 1)^k}= \frac{n!}{3^k2^k}$ <br> 因其為排列的個數，故 $\alpha$ 必為整數！
$\displaystyle\frac{n!}{3^k} = 2^k\times\frac{n!}{3^k2^k} = 2^k\times\alpha$ 亦為整數 (因 $\alpha$ 為整數，以 $2^k$ 乘之依然為整數)；原題得証。
此題可沿伸：若 $n = 3k$，則 $\displaystyle\frac{n!}{3^k2^k}$、$\displaystyle\frac{n!}{3^k}$、$\displaystyle\frac{n!}{2^k}$ 皆為整數。
再沿伸：若 $n = \beta k$，則 $\displaystyle\frac{n!}{(\beta!)^k}$、$\displaystyle\frac{n!}{\beta^k}$、$\displaystyle\frac{n!}{(\beta-1)^k}$、$...、$ $\displaystyle\frac{n!}{2^k}$、$n!$ 皆為整數。
:::
### 4. ($\S 1.3\ p. 18$)
Among the $3^{10}$ strings of length $10$ with alphabet $\{0, 1, 2\}$, how many have even weight (which is the sum of the corresponding values of the 10 alphabets for a string).
:::spoiler 中文
給定字元集合 $\{0, 1, 2\}$，在長度為 10 所有 $3^{10}$ 個不同字串中，有多少個其權重為偶數 (註：權重即為字串中所有10個字元對應數字的和)？
:::
:::spoiler solution
$$
2^{10}+\dbinom{10}{2}2^8+\dbinom{10}{4}2^6+\dbinom{10}{6}2^4+\dbinom{10}{8}2^2+\dbinom{10}{10}2^0 \\=
\sum_{n=0}^{5}\dbinom{10}{2n}2^{10-2n}
$$
請解釋 $2^{10}, \dbinom{10}{2}2^8, ... , \dbinom{10}{10}2^0 如何而得。$
:::

### 5. ($\S 1.3\ p. 19$)
Count the number of five-card selections from a standard deck of 52 cards that contain at least one club.

:::spoiler 中文
從52張撲克牌堆中任選五張牌並且其中至少有一張是梅花的組合有幾種？
:::
:::spoiler solution
$$
\dbinom{52}{5}-\dbinom{39}{5}=2,023,203
$$
:::

### 6. ($\S 1.3\ p. 21$)
To prove $\dbinom{n}{r}=\dbinom{n}{n-r}$ using a combinatorial proof.
:::spoiler proof
Regarding any selection of size $r$ from a collection of $n$ distinct objects, the selection process leaves
behind $n − r$ objects. Consequently, $\dbinom{n}{r}=\dbinom{n}{n-r}$
affirms the existence of a correspondence between the selections of size $r$ (objects chosen) and the selections of size $n − r$ (objects left behind).
:::
### 7. ($\S 1.2\ \sharp 37$)
$Sixteen\ people\ are\ to\ be\ seated\ at\ two\ circular\ tables,\ one\ of\ which\ seats\ 10\ while\ the\ other\ seats\ six.$$How\ many\ different\ seating\ arrangements\ are\ possible?$

:::spoiler 中文
$有16個人須坐在兩張圓桌周圍，其中一個圓桌有10個座位，另一個有6個座位，有幾種可能的座位安排$？
:::

:::spoiler solution
$\dbinom{16}{10}\times\dfrac{10!}{10}\times\dfrac{6!}{6}$
:::

### 8. ($\S 1.3\ \sharp 12$)

$In\ how\ many\ ways\ can\ 12\ different\ books\ be\ distributed\ among\ four\ children\ so\ that$

$(a)\ each\ child\ gets\ three\ books?$

$(b)\ the\ two\ oldest\ children\ get\ four\ books\ each\ and\ the\ two\ youngest\ get\ two\ books\ each?$

:::spoiler 中文
$老師有12本不同的書要發給4個小孩，請問：$
$(a) 所有小孩均獲得3本書的方式有幾種$？
$(b) 兩個較年長的獲得4本書且另外兩個較年輕的獲得2本書的方式有幾種$？
:::

:::spoiler solution
$(a)\ C_3^{12}\times C_3^9\times C_3^6\times C_3^3$
$(b)\ C_4^{12}\times C_4^8\times C_2^4\times C_2^2$
:::

### 9. ($\S 1.3\ \ Theorem\ 1.1\ and\ \S 1.4\ ex. 1.36$)
(a) What is the Binomial theorem?
(b) Prove the correctness of the Binomial theorem.
($\text{c}$) How many terms are there for $(x+y)^n$?

:::spoiler solution
(a) $(x+y)^n=\displaystyle\sum\limits_{k = 0}^{n}\dbinom{n}{k}x^ky^{n-k}\quad (=\displaystyle\sum\limits_{k = 0}^{n}\dbinom{n}{n-k}x^ky^{n-k})$

(b) $$(x + y)^n = (x+y)(x+y) ... (x+y)$$ Regrding term $x^ky^{n−k}$, its coefficient is the number of different ways in which we can select $k\ x$’s (and consequently ($n-k\ y$’s) from the $n$ available factors. The total number of such selections of size $k$ from a collection of size $n$ is $C(n, k) = \dbinom{n}{k}$, and from this the theorem follows.

考慮 $(x + y)^n = (x+y)(x+y) ... (x+y)$ (共 $n$ 個 $(x+y)$ 相乘) 中的 $x^ky^{n−k}$，此項係數是由 $n$ 個 $(x+y)$ 中選出 $k$ 項中的 $x$ 與其它 $n-k$ 項中的 $y$ 相乘所加總而成，而自 $n$ 個 $(x+y)$ 中選出 $k$ 項 (自 $n$ 個物件選出 $k$ 個) 總共有 $\binom{n}{k}$ 選法，每種選法對係數貢獻1，加總後係數即為 $\binom{n}{k}$，對每一 $k$，$0\le k \le n$ 皆成立，於是 $(x+y)^n=\displaystyle\sum\limits_{k = 0}^{n}\dbinom{n}{k}x^ky^{n-k}$ 成立。

($\text{c}$) In the binomial expansion for $(x + y)^n$ , each term is of the form \begin{aligned}\dbinom{n}{k}x^ky^{n−k}\end{aligned}
where $0\le k\le n$. The total number of terms in the expansion of $(x+y)^n$ is the number of nonnegative integer solutions of $n_1 +n_2 = n$ ($n_1$ is the exponent for $x$ , $n_2$ the exponent for $y$). This number is \begin{aligned}C(2 + n − 1, n)
=n + 1.\end{aligned}Therefore, $(x + y)^n$ has $n+1$ terms.
由二項式定理可知：在 $(x + y)^n$ 的展開式中，每一項的型式為： $\dbinom{n}{k}x^ky^{n−k}$，其中 $0\le k\le n$；此時 $x$ 的冪次和 $y$ 的冪次相加恰為 $n(=k+(n-k))$。亦即：令 $x$ 的冪次為 $n_1$ 且 $y$ 的冪次為 $n_2$，則 $n_1+n_2 = n$；每一組非負整數解 $(n_1,n_2)$ 即對應一項 $x^{n_1}y^{n_2} (=x^ky^{n−k})$。而其非負整數解的個數恰為 $\binom{n+(2−1)}{n} = n + 1$；所以 $(x + y)^n$ 展開後共有 $n+1$ 項。
:::

### 10. ($\S 1.3\ p. 23$)
For each integer $n\ >\ 0$ ,
$(a)\ \dbinom{n}{0}+\dbinom{n}{1}+\dbinom{n}{2}+...+\dbinom{n}{n}=2^n$
$(b)\ \dbinom{n}{0}-\dbinom{n}{1}+\dbinom{n}{2}-...+(-1)^n\dbinom{n}{n}=0$

:::spoiler solution
Part (a) follows from the binomial theorem when we set $x = y = 1$. When $x = −1$ and $y = 1$, part (b) results.
:::

### 11. ($\S 1.3\ \sharp 9$)
How many bytes contain (a) exactly two $1$’s; (b) exactly four $1$’s; \(c)exactly six $1$’s; (d) at least six $1$’s?

:::spoiler 中文
一個byte(a)包含兩個$1$的方式有幾種(b)包含四個$1$的方式有幾種\(c)包含六個$1$的方式有幾種(d)至少6個$1$的方式有幾種
:::

:::spoiler solution
$(a)\ \dbinom{8}{2}$
$(b)\ \dbinom{8}{4}$
$(c)\ \dbinom{8}{6}$
$(d)\ \dbinom{8}{6}+\ \dbinom{8}{7}+\ \dbinom{8}{8}$
:::

### 12. ($\S 1.3\ \sharp 17$)
Express each of the following using the summation (or Sigma) notation. In parts (a), (d), and (e), n denotes a positive integer.

$(a)\ \dfrac{1}{2!}+\dfrac{1}{3!}+\dfrac{1}{4!}+...+\dfrac{1}{n!},n≥2$

$(b)\ 1 + 4 + 9 + 16 + 25 + 36 + 49$

$(c)\ 1^3 − 2^3 + 3^3 − 4^3 + 5^3 − 6^3 + 7^3$

$(d)\ \dfrac{1}{n}+\dfrac{2}{n+1}+\dfrac{3}{n+2}+...+\dfrac{n+1}{2n}$

$(e)\ n-\dfrac{n+1}{2!}+\dfrac{n+2}{4!}-\dfrac{n+3}{6!}+...+(-1)^n\dfrac{2n}{(2n)!}$

:::spoiler 中文
使用 $\Sigma$ 符號表達以下各項。 在(a)、(d)和(e)中，n表示正整數。
:::

:::spoiler solution
$(a)\ \sum\limits_{k = 2}^{n}{\dfrac{1}{k!}}$

$(b)\ \sum\limits_{i = 1}^{7}{i^2}$

$(c)\ \sum\limits_{j=1}^{7}{(-1)^{j-1}j^3} =\sum\limits_{j=1}^{7}{(-1)^{j+1}j^3}$

$(d)\ \sum\limits_{i=0}^{n}{\dfrac{i+1}{n+i}}$

$(d)\ \sum\limits_{i=0}^{n}{(-1)^i\dfrac{n+i}{(2i)!}}$

:::

### 13. ($\S 1.3\ \sharp 30$)
With $n$ a positive integer, evaluate the sum
$\dbinom{n}{0}+2\dbinom{n}{1}+2^2\dbinom{n}{2}+...+2^k\dbinom{n}{k}+...+2^n\dbinom{n}{n}$

:::spoiler 中文
計算$\dbinom{n}{0}+2\dbinom{n}{1}+2^2\dbinom{n}{2}+...+2^k\dbinom{n}{k}+...+2^n\dbinom{n}{n}$的總和
:::

:::spoiler solution
The sum is the binomial expansion of $(1+2)^n=3^n$
:::

---

## [作業二]

### 1. ($\S 1.4\ ex. 1.28$)
Seven kids go to McDonald, where $4$ sets of combo food are provided. How many orders are possible for these $7$ kids? ==The order is ++relevant++==. (Each kid has his/her own meal.)
:::spoiler 中文
七個小孩去麥當勞，麥當勞有提供四種不同的套餐，這七個小孩有幾種點餐的可能？餐的順序對小孩而言是重要的 (The order is relevant.)；每個小孩都有自己的餐點。
:::

:::spoiler solution
$4^7$
:::

### 2. ($\S 1.4\ ex. 1.28$)
Seven kids go to McDonald, where $4$ sets of combo food are provided. How many orders are possible for the resterant? ==The order is ++irrelevant++==. (Each kid has his/her own meal.)
:::spoiler 中文
七個小孩去麥當勞，麥當勞有提供四種不同的套餐，請問麥當勞廚房會收到幾種點餐的可能？餐的順序對小孩而言是不重要的 (The order is irrelevant.)；麥當勞廚房可能收到多少種點餐的菜單？
:::

:::spoiler solution
$\dbinom{7+4-1}{7}=\dbinom{10}{7}$
:::

### 3. ($\S 1.4\ ex. 33$)
$x_1 + x_2 + x_3 + x_4 = 7\ ,\text{where } x_i ≥ 0\text{ for all }\ 1\ ≤\ i\ ≤\ 4$.
Find the number of nonnegative integer solutions to the equation.
:::spoiler 中文
$x_1 + x_2 + x_3 + x_4 = 7\ , x_i ≥ 0,\ 1 ≤ i ≤ 4$.
請求算此方程式非負整數解的個數？
:::
:::spoiler solution
$\dbinom{7+4-1}{7}=\dbinom{10}{7}$
:::

### 4. ($\S 1.4\ ex. 1.33$)
How may ways are there to distribute $7$ $identical$ pennies to $4$ $distinct$ boxes.

:::spoiler 中文
有幾種方式可以將$7$個**相同**的硬幣放入$4$個**不同**的盒子?
:::

:::spoiler solution
$\dbinom{7+4-1}{7}=\dbinom{10}{7}$
:::

### 5. ($\S 1.4\ \sharp 1$)

$In\ how\ many\ ways\ can\ 10\ (identical)\ dimes\ be\ distributed\ among\ five\ children\ if$

$(a)\ there\ are\ no\ restrictions?$

$(b)\ each\ child\ gets\ at\ least\ one\ dime？$

$(c)\ the\ oldest\ child\ gets\ at\ least\ two\ dimes？$

:::spoiler 中文
$在沒有限制的情況下，10個相同的硬幣可以分給5個孩子$
$(a) 有多少種方式$？
$(b) 每個孩子至少拿到1個硬幣有多少種方式$？
$(c) 最大的孩子至少拿到2個硬幣有多少種方式$？
:::

:::spoiler solution
$(a)\ \dbinom{10+5-1}{10}=\dbinom{14}{10}$
$(b)\ \dbinom{5+5-1}{5}=\dbinom{9}{5}$
$(c)\ \dbinom{8+5-1}{8}=\dbinom{12}{8}$
:::

### 6. ($\S 1.4\ \sharp 14$)
In the expansion of $\left(3v+2w+x+y+z\right)^8$
(a) find the coefficient of $v^2w^4xz$;
(b) how many terms in the expansion?

:::spoiler 中文
多項式 $\left(3v+2w+x+y+z\right)^8$ 展開後
(a) $v^2w^4xz$ 項的係數是多少？
(b) 總共有多少項？
:::

:::spoiler solution

(a)
$\dbinom{8}{2, 4, 1, 0, 1}3^22^4 =\dbinom{8}{2}\dbinom{6}{4}\dbinom{2}{0}\dbinom{2}{1}\dbinom{1}{1}3^22^4=\ \dfrac{8!}{2!6!}\dfrac{6!}{4!2!}\dfrac{2!}{1!1!}3^22^4 = \dfrac{8!}{2!4!}3^22^4$
(b) 該多項式展開後的每一項形式皆為 $v^aw^bx^cy^dz^e$ 且 $a+b+c+d+e=8, a,b,c,d,e\ge0$；所求即為此方程式的非負整數解的個數：$\dbinom{8+5-1}{8}=\dbinom{12}{8}$。
:::

### 7. ($\S 1.4\ ex. 39$)
Consider the following program segment, where $i$, $j$ , and $k$ are integer variables.

for i := 1 to 20 do
    for j := 1 to i do
        for k := 1 to j do
            print (i * j + k)

How many times is the print statement executed in this program segment?

:::spoiler 中文
考慮以下程式，其中$i$, $j$ , $k$是整數變數。請問 print 這行指令執行了幾次？
:::

:::spoiler solution
$\ \dbinom{3+20-1}{3} = \dbinom{22}{3} = 1540$
:::

### 8. ($\S 1.4\ \sharp 17$)
How many ways are there to place $12$ marbles of the same size in five distinct jars if (a) the marbles are all black? (b) each marble is a different color?

:::spoiler 中文
12顆大小相同的彈珠放入5個不同的罐子，如果(a)所有彈珠皆為黑色有幾種方式？(b)所有彈珠皆為不同顏色有幾種方式
:::

:::spoiler solution
$(a)\ \dbinom{5+12-1}{12} = \dbinom{16}{12}$
$(b)\ 5^{12}$
:::

### 9. ($\S 1.4\ \sharp 19$)
How many times is the print statement executed for the following program segment? (Here, $i$, $j$ , $k$, and $m$ are integer variables.)

for i := 1 to 20 do
    for j := 1 to i do
        for k := 1 to j do
            for m := 1 to k do
                print (i * j)+(k * m)

:::spoiler 中文
print被執行了幾次，其中$i$, $j$ , $k$, $m$是整數變數
:::

:::spoiler solution
$\ \dbinom{20+4-1}{4} = \dbinom{23}{4}$
:::

### 10. ($\S 1.4\ \sharp 23$)
(a) Given positive integers $m$, $n$ with $m ≥ n$, show that the number of ways to distribute $m$ identical objects into $n$ distinct containers with no container left empty is
\begin{aligned}
C(m − 1, m − n) = C(m − 1, n − 1).
\end{aligned}
(b) Show that the number of distributions in part (a) where
each container holds at least $r$ objects ($m ≥ nr$) is
\begin{aligned}C(m − 1 + (1 − r)n, n − 1).\end{aligned}
:::spoiler 中文
(a)給定正整數 $m$, $n$（其中 $m ≥ n$），證明將 $n$ 個相同物件分配到 $m$ 個不同容器且沒有容器為空的方法數為
\begin{aligned}C(m − 1, m − n) = C(m − 1, n − 1)\end{aligned}
(b)證明(a)中每個容器至少有r個物件($m ≥ nr$)為
\begin{aligned}C(m − 1 + (1 − r)n, n − 1).\end{aligned}
:::

:::spoiler solution
$(a)\ \dbinom{(m-n)+n-1}{m-n} = \dbinom{m-1}{m-n}= \dbinom{m-1}{(m-1)-(m-n)}= \dbinom{m-1}{n-1}$

$(b)\ \dbinom{(m-rn)+n-1}{m-rn} = \dbinom{m-1+(1-r)n}{m-rn}= \dbinom{m-1+(1-r)n}{n-1}$
:::

## [作業三]
:::info
### PMI (Principle of Mathematical Induction):
$$[S(n_0)\wedge[\forall\ k\ge n_0[S(k)\implies S(k+1)]] ]\implies \forall\ n\ge n_0\ S(n)
$$
### 數學歸納法原理：
若 [ $S(n_0)$ 成立 且 [對所有 $k\ge n_o$ 而言，當 $S(k)$ 成立時必可推出 $S(k+1)$ 成立]] 則可得 $S(n)$ 必定成立，對所有 $k\ge n_0$ 而言。

:::
### Prove the formulas by PMI (Principle of Mathematical Induction)
### 以數學歸納法証明下列式子：

### 1. ($\S 4.1\ ex. 4.9$)

\begin{aligned}
H_1 &= 1 \\
H_2 &= 1+\dfrac{1}{2} \\
H_3 &= 1+\dfrac{1}{2}+\dfrac{1}{3} \\
.\\.\\. \\
H_n &= 1+\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{n}\ ,for\ each \ n\in\mathbb{Z}^+ \\
\sum_{j=1}^{n}H_j&=(n+1)H_n-n
\end{aligned}

:::spoiler solution
基礎：$當\ n=1\ 時，$
\begin{aligned}
\sum_{j=1}^{1}H_j&=H_1=(1+1)H_1-1
\end{aligned}
假設：if $n=k$ that：
\begin{aligned}
\sum_{j=1}^{k}H_j&=(k+1)H_k-k\ \ \ is\ true
\end{aligned}
推論：
\begin{aligned}
\sum_{j=1}^{k+1}H_j=\sum_{j=1}^{k}H_j+H_{k+1}&=(k+1)H_k-k+H_{k+1}\\
&=(k+1)(H_{k+1} − \dfrac{1}{k + 1}) − k + H_{k+1}\\
&=(k+2)H_{k+1}-1-k\\
&=(k+2)H_{k+1}-(k+1)
\end{aligned}
基於數學歸納法原理，原式得証。
:::

### 2.
$(a)\ \sum\limits_{j = 1}^{n}(2j-1)^2=1^2+3^2+...+(2n-1)^2=\dfrac{n(2n+1)(2n-1)}{3}$
$(b)\ \sum\limits_{j = 1}^{n}j^3=1^3+2^3+...+n^3=\dfrac{n^2(n+1)^2}{4}=\left(\dfrac{n(n+1)}{2}\right)^2=\left(\sum\limits_{j=1}^{n}j\right)^2$

:::spoiler solution

(a)
基礎：$n=1$時，$\sum\limits_{j = 1}^{1}(2j-1)^2=1^2=\dfrac{1(2+1)(2-1)}{3}$ 成立。
假設：$n=k \ge1$ 時該式成立，即 $\sum\limits_{j = 1}^{k}(2j-1)^2=\dfrac{k(2k+1)(2k-1)}{3}$
推論：當 $n=k+1$ 時，
\begin{aligned}
\sum_{j = 1}^{k+1}(2j-1)^2&=[1^2+3^2+...+(2k-1)^2]+[2(k+1)-1]^2\\
&=\dfrac{k(2k+1)(2k-1)}{3}+[2(k+1)-1]^2\\
&=\dfrac{k(2k+1)(2k-1)}{3}+(2k+1)^2\\
&=\dfrac{k(2k+1)(2k-1)+3(2k+1)^2}{3}\\
&=\dfrac{(2k+1)[k(2k-1)+3(2k+1)]}{3}\\
&=\dfrac{(2k+1)(2k^2-k+6k+3)}{3}\\
&=\dfrac{(2k+1)(2k^2+5k+3)}{3}\\
&=\dfrac{(2k+1)(k+1)(2k+3)}{3}\\
&=\dfrac{(k+1)[2(k+1)+1][2(k+1)-1]}{3}\\
該式亦成立。
\end{aligned}
基於數學歸納法原理，原式得証。

(b)
基礎：$n=1$ 時，$\sum\limits_{j = 1}^{1}j^3=1^3=\dfrac{1^2(1+1)^2}{4}$ 成立。
假設 $n=k \ge1$ 時成立，即 $\sum\limits_{j = 1}^{k}j^3=\dfrac{k^2(k+1)^2}{4}=\left(\sum\limits_{j=1}^{k}j\right)^2$
推論：當 $n=k+1$ 時，
\begin{aligned}
\sum_{j = 1}^{k+1}j^3&=(1^3+2^3+...+k^3)+(k+1)^3\\
&=\dfrac{k^2(k+1)^2}{4}+(k+1)^3\\
&=\dfrac{k^2(k+1)^2+4(k+1)^3}{4}\\
&=\dfrac{(k+1)^2(k^2+4k+4)}{4}\\
&=\dfrac{(k+1)^2(k+2)^2}{4}\\
&=\dfrac{(k+1)^2[(k+1)+1]^2}{4}\\
&=\left(\dfrac{(k+1)[(k+1)+1]}{2}\right)^2\\
&=\left(\sum_{j=1}^{k+1}j\right)^2
\end{aligned}https://hackmd.io/
基於數學歸納法原理，原式得証。
:::

### 3.

(a) $\sum\limits_{j = 1}^{n}2^{j-1} (= 2^0+2^1+2^2+... +2^{n-1}) = 2^n-1$
:::spoiler solution
基礎：當 $n=1$ 時，<br>$\qquad\quad\sum\limits_{j = 1}^{n}2^{j-1} =\sum\limits_{j = 1}^{1}2^{j-1} = 2^{1-1}=2^0= 1 = 2^1-1= 2^n-1$，原式成立。
假設：當 $n=k$ 時，該式成立：<br>
$\qquad\quad\sum\limits_{j = 1}^{n}2^{j-1}=\sum\limits_{j = 1}^{k}2^{j-1} = 2^0+2^1+2^2+... +2^{k-1} = 2^k-1$。
推論：當 $n=k+1$ 時，<br>$\qquad\quad\sum\limits_{j = 1}^{n}2^{j-1} = \sum\limits_{j = 1}^{k+1}2^{j-1} = 2^{1-1}+2^{2-1}+2^{3-1}+... +2^{k-1}+2^{(k+1)-1}$
$\qquad\qquad= (2^0+2+2^2+... +2^{k-1})+2^{k} = 2^k-1+2^k$ $\qquad\qquad= 2\times 2^k-1 = 2^{k+1}-1=2^n-1$。<br>$\qquad\quad$可知該式亦成立。
基於數學歸納法原理可得原式成立。
:::
(b) $\sum\limits_{j = 1}^{n}j\times2^{j-1} (= 1\times2^0+2\times2^1+3\times2^2+... +n\times2^{n-1}) = (n-1)\times2^n+1$
:::spoiler solution
基礎：當 $n=1$ 時，<br>$\qquad\quad\sum\limits_{j = 1}^{1}j\times2^{j-1} = 1\times2^{1-1}=1\times2^0= 1 = (1-1)\times2^1+1$，原式成立。
假設：當 $n=k$ 時，該式成立：<br>$\qquad\quad\sum\limits_{j = 1}^{k}j\times2^{j-1} = 1\times2^0+2\times2^1+3\times2^2+... +k\times2^{k-1} = (k-1)\times2^k+1$。
推論：當 $n=k+1$ 時，<br>$\qquad\quad\sum\limits_{j = 1}^{k+1}j\times2^{j-1} = 1\times2^0+2\times2^1+3\times2^2+... +k\times2^{k-1}+(k+1)\times2^{k}$
$\qquad\qquad= (k-1)\times2^k+1+(k+1)\times2^{k} = 2^k(k-1+k+1)+1$ $\qquad\qquad= 2k\times 2^k+1 =k\times2^{k+1}+1 (=((k+1)-1)\times2^{k+1}+1 )$。<br>$\qquad\quad$可知該式亦成立。
基於數學歸納法原理，原式得証。
:::

### 4.
$(a)S(n):2^n<n!，證明所有大於\ 3\ 的整數\ n，S(n)均成立。$

$(b)S(n):n^2<2^n，證明所有大於\ 4\ 的整數\ n，S(n)均成立。$

$(c)S(n):n^3<2^n，找出最小的正整數\ n_0，然後證明所有大於\ n_0\ 的整數\ n，S(n)均成立。$

:::spoiler solution
$(a)$
$2^n<n!，n>3，即\ n\ge4。$
基礎：當 $n=4$ 時，$2^4=16<4!$，成立。
假設：$n=k\ge4$ 時成立，即 $2k<k!$。
當 $n=k+1$ 時，$2^{k+1}=2\times2^k<2\times k!<(k+1)\times k!=(k+1)!$
故由數學歸納法得證 $S(n)$ 成立。

$(b)$
$n^2<2^n，n\ge5。$
基礎：當 $n=5$ 時，$5^2<2^5$，成立。
假設 $n=k\ge5$ 時成立，即 $k^2<2^k$。
推論：當 $n=k+1$ 時，$(k+1)^2=k^2+2k+1<2^k+2k+1<2^k+2^k=2^{k+1}$
即 $(k+1)^2<2^{k+1}$ ，需補上 $(2k+1)<2^k$ 的證明，因已假設$k^2<2^k$，故證明 $(2k+1)<k^2$ 即可，當 $n\ge5$ 時，$(2k+1)<k^2$ 明顯成立，
故數學歸納法原理得證 $S(n)$ 成立。

$(c)$
$n^3<2^n$
基礎：當 $n=10$ 時，$10^3<2^10$，故 $n_0=10$ 為讓 $S(n)$ 成立最小的 $n$ 值。
假設：$n=k\ge10$ 時成立，即 $k^3<2^k$。
推論：當 $n=k+1$ 時，$(k+1)^3=k^3+3k^2+3k+1<2^k+3k^2+3k+1<2^k+2^k=2^{k+1}$
同樣需補上 $3k^2+3k+1<2^k$ 的證明，因已假設$k^3<2^k$，故證明 $3k^2+3k+1<k^3$ 即可，當 $n\ge10$ 時，$3k^2+3k+1<k^3$ 明顯成立，
故數學歸納法原理得證 $S(n)$ 成立。
:::

### 5.
$S(n):(n^3-n)\ 為\ 3\ 的倍數，證明所有大於\ 1\ 的整數\ n，S(n)均成立。如：\ n=4，n^3-n=4^3-4=60\ 為 3 的倍數。$
:::spoiler solution
基礎：當 $n=1$ 時，$n^3-n=1-1=0$ 為 3 的倍數，$S(1)$ 成立。
假設：$n=k$ 時成立，即 $S(k): k^3-k=3x，\ x$ 整數。
推論：當 $n=k+1$ 時，$S(k+1)$：
\begin{aligned}
(k+1)^3-(k+1) &= (k+1)[(k+1)^2-1]\\
&=(k+1)[(k+1)^2-1]\\
&=(k+1)(k^2+2k+1-1) = (k+1)(k^2+2k)\\
&=k^3+2k^2+k^2+2k\\
&=(k^3-k)+(3k^2+3k) \qquad // 關鍵步驟\\
&=3x+3(k^2+k)\\
&=3(x+k^2+k)\\
\end{aligned}
$\qquad\quad即\ S(k+1)\ 亦為\ 3\ 的倍數。$

由數學歸納法原理可得證 $S(n)$ 成立。
:::
### 6. Properties of $F_n$ and $L_n$

(a) $\quad\sum\limits_{i=0}^{n}F_i^2=F_n\times F_{n+1}\ ,\ n\ge1$ where $F_n=\begin{cases}0,& \text{if }n=0;\\1,& \text{if }n=1;\\F_{n-1}+F_{n-2}& \text{otherwise}.\end{cases}$
:::spoiler solution
基礎：$n=1$ 時，
\begin{aligned}
\sum\limits_{i=0}^{1}F_i^2=0^2+1^2=1\times 1=F_1\times F_2\ 成立。
\end{aligned}
假設：$n=k$ 時，該式成立。
\begin{aligned}
\sum\limits_{i=0}^{k}F_i^2=F_k\times F_{k+1}
\end{aligned}
推論：$n=k+1$ 時，
\begin{aligned}
\sum\limits_{i=0}^{k+1}F_i^2&=\sum_{i=0}^{k}F_i^2+ F^2_{k+1}=F_k\times F_{k+1}+ F^2_{k+1}\\
&=(F_{k}+F_{k+1})\times F_{k+1}\\
&=F_{k+2}\times F_{k+1}\\
&=F_{k+1}\times F_{k+2}
\end{aligned}
基於數學歸納法原理，原式得証。
:::
(b) $\quad L_n=F_{n-1}+F_{n+1},\ n\ge1$ where $L_n=\begin{cases}2,& \text{if }n=0;\\1,& \text{if }n=1;\\L_{n-1}+L_{n-2}& \text{otherwise}.\end{cases}$
:::spoiler solution
基礎：$n=1$ 和 $n=2$ 時 (注意遞迴式中有 $F_{n-1}\ 和\ F_{n+1}$ 兩項，故亦取基礎兩項)，
\begin{aligned}L_1=1=0+1=F_0+F_2=F_{1-1}+F_{1+1}, \\
L_2=3=1+2=F_1+F_3=F_{2-1}+F_{2+1},\\
\end{aligned}
$\qquad\quad$原式成立。
假設：$n=1, 2, ..., k-1, k$ 時，該式成立：$L_n=F_{n-1}+F_{n+1}$。（注意：此處假設成立的式子多於一則是可以的！基於的是「强數學歸納法」(strong mathematical induction）。

推論：$n=k+1$ 時，
\begin{aligned}
L_{k+1} &=L_k+L_{k-1}=\\
&=(F_{k-1}+F_{k+1})+(F_{k-2}+F_{k})\\
&=(F_{k-1}+F_{k-2})+(F_{k+1}+F_{k})\\
&=F_{k}+F_{k+2}
\end{aligned}
基於數學歸納法原理，原式得証。
:::
\(c)
For a fixed $m\in\mathbb{Z}^+\ ,\ \sum\limits_{k=0}^{m-1}a_{m,k}=m!$, where

$a_{m,k}=(m-k)a_{m-1,k-1}+(k+1)a_{m-1,k}, 0\le k \le m-1, a_{0,0}=1, a_{m,k}=0, k\ge m, k\lt 0$

:::spoiler solution

基礎：當 $m=1$ 時，<br>$\qquad\quad\sum\limits_{k=0}^{m-1}a_{m,k} =\sum\limits_{k=0}^{1-1}a_{1,k} = a_{1,0} =1 = 1!$，原式成立。
假設：當 $m=n$ 時，該式成立：<br>
$\qquad\quad\sum\limits_{k=0}^{n-1}a_{n,k}=n!$。
推論：當 $m=n+1$ 時，<br>$\qquad\quad\sum\limits_{k=0}^{(n+1)-1}a_{n,k}\ =\sum\limits_{k=0}^{n}[(n+1-k)a_{n,k-1}+(k+1)a_{n,k}]=$
$\qquad\qquad\qquad\qquad=[(n+1)a_{n,-1}+a_{n,0}]+[na_{n,0}+2a_{n,1}]+...+[a_{n,n-1}+(n+1)a_{n,n}]$
$\qquad\qquad\qquad\qquad=[a_{n,0}+na_{n,0}]+[2a_{n,1}+(n-1)a_{n,1}]+...+[na_{n,n-1}+a_{n,n-1}]$
$\qquad\qquad\qquad\qquad=(n+1)\sum\limits_{k=0}^{n-1}a_{n,k}=(n+1)\times n!=(n+1)!$

基於數學歸納法原理可得原式成立。
:::

### 7. More properties of $F_n$ and $L_n$

證明以下式子。
(a) $\quad\sum\limits_{i=0}^{n}F_i=F_{n+2}-1, n \ge1$
(b) $\quad\sum\limits_{i=1}^{n}\dfrac{F_{i-1}}{2^i}=1-\dfrac{F_{n+2}}{2^n}, n \ge1$
\(c) $\quad\sum\limits_{i=1}^{n}L_i^2=L_nL_{n+1}-2, n \ge1$

:::spoiler solution
(a)
基礎：當 $n=1$ 時，<br>$\qquad\quad\sum\limits_{i=0}^{n}F_i=\sum\limits_{i=0}^{1}F_i=F_0+F_1=F_1=F_3-1=1=F_3-1=F_{1+2}-1$，原式成立。
假設：當 $n=k$ 時，該式成立：
$\qquad\quad\sum\limits_{i=0}^{k}F_i=F_{k+2}-1$。
推論：當 $n=k+1$ 時，<br>$\qquad\quad\sum\limits_{i=0}^{k+1}F_i=\sum\limits_{i=0}^{k}F_i+F_{k+1}$
$\qquad\qquad\quad\ =F_{k+2}+F_{k+1}+1$
$\qquad\qquad\quad\ =F_{k+3}+1$
$\qquad\quad該式亦成立。$
基於數學歸納法原理可得原式成立。

(b)
基礎：當 $n=1$ 時，<br>$\qquad\quad\sum\limits_{i=1}^{n}\dfrac{F_{i-1}}{2^i}=\sum\limits_{i=1}^{1}\dfrac{F_{i-1}}{2^i}=\dfrac{F_{1-1}}{2^1}=1-\dfrac{F_{1+2}}{2^1}=0$，原式成立。
假設：當 $n=k$ 時，該式成立：
$\qquad\quad\sum\limits_{i=1}^{k}\dfrac{F_{i-1}}{2^i}=1-\dfrac{F_{k+2}}{2^k}$。
推論：當 $n=k+1$ 時，<br>$\qquad\quad\sum\limits_{i=1}^{k+1}\dfrac{F_{i-1}}{2^i}=\sum\limits_{i=1}^{k}\dfrac{F_{i-1}}{2^i}+\dfrac{F_{(k+1)-1}}{2^{k+1}}$

$\qquad\qquad\qquad\quad=1-\dfrac{F_{k+2}}{2^k}+\dfrac{F_{k}}{2^{k+1}}$

$\qquad\qquad\qquad\quad=1-\dfrac{2F_{k+2}-F_{k}}{2^{k+1}}$

$\qquad\qquad\qquad\quad=1-\dfrac{F_{k+3}}{2^{k+1}}$
$\qquad該式亦成立。$

基於數學歸納法原理可得原式成立。

\(c)
基礎：當 $n=1$ 時，<br>$\qquad\quad\sum\limits_{i=1}^{n}L_i^2=\sum\limits_{i=1}^{1}L_i^2=L_1^2=L_1L_{1+1}-2=1$，原式成立。
假設：當 $n=k$ 時，該式成立：
$\qquad\quad\sum\limits_{i=1}^{k}L_i^2=L_kL_{k+1}-2$。
推論：當 $n=k+1$ 時，<br>$\qquad\quad\sum\limits_{i=1}^{k+1}L_i^2=\sum\limits_{i=1}^{k}L_i^2+L_{k+1}^2$

$\qquad\qquad\quad\quad =L_kL_{k+1}-2+L_{k+1}^2$

$\qquad\qquad\quad\quad =L_kL_{k+1}+L_{k+1}L_{k+1}-2$

$\qquad\qquad\quad\quad =L_{k+1}(L_k+L_{k+1})-2$

$\qquad\qquad\quad\quad =L_{k+1}L_{k+2}-2$
$\qquad\quad該式亦成立。$

基於數學歸納法原理可得原式成立。
:::
----

### 8. ($\S 4.2\ \sharp 1$)

Give a recursive definition for each of the following integer sequences $c_1, c_2, c_3,...,$
where for all $n\in\mathbb{Z}^+$ we have

\begin{aligned}
&(a)\ c_n= 7n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (b)\ c_n= 7^n\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (c)\ c_n= 3n+7 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (d)\ c_n= 7\\
&(e)\ c_n= n^2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (f) \ c_n= 2-(-1)^n
\end{aligned}

:::spoiler 中文
用遞迴方式定義以上數列
:::

:::spoiler solution
以下皆有兩組遞迴式 ($(f)$ 有三組)，擇其一作答即可。
$(a)\quad c_1= 7;$ and $c_{n+1}=c_n+7$, for $n\ge1$. 或
$\quad\quad\ c_n=\begin{cases}7, &\text{if }n=1;\\c_{n-1}+7\ ,&\text{otherwise}.\end{cases}$

$(b)\quad c_1= 7;$ and $c_{n+1}=7c_n$, for $n\ge1$. 或
$\quad\quad\ c_n=\begin{cases} 7, &\text{if }n=1;\\7c_{n-1},&\text{otherwise}.\end{cases}$

$(c)\quad c_1= 10;$ and $c_{n+1}=c_n+3$, for $n\ge1$. 或
$\quad\quad\ c_n=\begin{cases}10, &\text{if }n=1;\\c_{n-1}+3,&\text{otherwise}.\end{cases}$

$(d)\quad c_1= 7;$ and $c_{n+1}=c_n$, for $n\ge1$. 或
$\quad\quad\ c_n=\begin{cases}7, &\text{if }n=1;\\c_{n-1},&\text{otherwise}.\end{cases}$

$(e)\quad c_1= 1;$ and $c_{n+1}=c_n+2n+1$, for $n\ge1$. 或
$\quad\quad\ c_n=\begin{cases}1, &\text{if }n=1;\\c_{n-1}+2(n-1)+1\,&\text{otherwise}. \end{cases}$

$(f)\quad c_1= 3\ ;c_2=1;$ and $c_{n+2}=c_n$, for $n\ge1$. 或
$\quad\quad\ c_n=\begin{cases}3, &\text{if }n=1;\\ 1, &\text{if }n=2;\\c_{n-2}=c_n,&\text{otherwise}.\end{cases}$ 或
$\quad\quad\ c_n=\begin{cases}3, &\text{if }n\ \text{is odd};\\ 1, &\text{otherwise}.\end{cases}$
:::

### 9.
You are climbing a stair case with $n$ steps.Each time you can either climb $1$, $2$ or $3$ steps. Write a recursive function to compute the number of distinct ways you can climb to the top.

:::spoiler 中文
你正在爬一座有 n 階的樓梯。每次你可以爬 1 階、2 階或 3 階。請撰寫一個遞迴函式來計算你可以用多少種不同的方式爬到樓梯的頂端。
:::

:::spoiler solution
Let $a_n$ be the distinct ways to climb to the top of the $n$-step stair.
令 $a_n$ 表示爬上 $n$ 階樓梯頂端的可能步伐總數，則
$a_n=\begin{cases}1,& \text{if }n=1;\\2,& \text{if }n=2;\\4,& \text{if }n=3;\\a_{n-1}+a_{n-2}+a_{n-3},&\text{if } n\ge\text{4}.\end{cases}$
:::

### 10.
#### Express the following formulae recursively:
(a) $H_n=1+\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{n},\ \text{for each }n\in\mathbb{Z}^+$

(b) $b_n = 2n, \text{for each }n\in\mathbb{Z}^+$

:::spoiler 中文
請將上述公式以遞迴方式表示。
:::
:::spoiler solution
(a)
$H_n=\begin{cases}1,& \text{if }n=1;\\H_{n-1}+\dfrac{1}{n},& \text{otherwise}.\end{cases}$

(b)
$b_n=\begin{cases}2,& \text{if }n=1;\\b_{n-1}+2,& \text{otherwise}.\end{cases}$
:::

### 11.

Let $d_n$ denote the number of $derangements$ of $n$ distinct objects. Express $d_n$ recursively.
:::spoiler 中文
令 $d_n$ 表示任意 $n$ 個相異物件集體錯亂的個數。求 $d_n$ 的遞迴式。
:::

:::spoiler solution
$d_n=\begin{cases}0,& \text{if }n=1;\\1,& \text{if }n=2;\\(n-1)(d_{n-2}+d_{n-1}),& \text{otherwise}.\end{cases}$

:::

### 12.

How many way are there, expressed by a recursive formula, for coloring $n$ numbered sectors of a circle using $3$ colors? .

:::spoiler 中文
請將「使用 $3$ 個顔色塗圓內 $n$ 個弦狀區域，相鄰弦不能同色的所有塗法」以遞迴式表示出來。
:::
:::spoiler solution
令 $a_n$ 表示「使用 $3$ 個顔色塗圓內 $n$ 個弦狀區域，相鄰弦不能同色的所有塗法」，則
$\qquad a_n=\begin{cases}3,& \text{if }n=1;\\6& \text{if }n=2;\\6,& \text{if }n=3;\\a_{n-1}+2a_{n-2},& \text{otherwise}.\end{cases}$
:::
### 13.
How many positive divisors are there for $29,338,848,000$?
:::spoiler 中文
29,338,848,000 的正因數有多少個？
:::
:::spoiler solution
$29,338,848,000 = 2^83^55^37^311$

(8 + 1)(5 + 1)(3 + 1)(3 + 1)(1 + 1) = (9)(6)(4)(4)(2) = 1728
:::
----
## [作業四] Relations and Functions

### 1 ($\S 5.1\ \sharp\ 1$)

If $A = \{1, 2, 3, 4\}$, $B = \{2, 5\}$, and $C = \{3, 4, 7\}$, determine $A \times B$, $B \times A$, $A\cup (B\times C)$, $(A \cup B) \times C$, and $(A \times C) \cup (B \times C) .$

:::spoiler solution
$A\times B=\{(1,2),(2,2),(3,2),(4,2),(1,5),(2,5),(3,5),(4,5)\}$
$B\times A=\{(2,1),(2,2),(2,3),(2,4),(5,1),(5,2),(5,3),(5,4)\}$
$A\cup (B\times C)=\{1,2,3,4,(2,3),(2,4),(2,7),(5,3),(5,4),(5,7)\}$
$(A\cup B)\times C=(A\times C)\cup (B\times C)=\{(1,3),(2,3),(3,3),(4,3),(5,3),(1,4),(2,4),(3,4),(4,4),(5,4),(1,7),(2,7),(3,7),(4,7),(5,7)\}$
:::

### 2 ($\S 5.1\ \sharp\ 7$)

(a) If $A = \{1, 2, 3, 4, 5\}$ and $B = \{w, x, y, z\}$, how many elements are there in $\mathcal{P}(A \times B)$?
(b) Generalize the result in part (a).

:::spoiler solution
(a) Since $\vert A \vert$ = $5$ and $\vert B \vert$ = $4$ ,we have $\vert A\times B \vert$ = $\vert A \vert \times \vert B \vert$ = $5\times 4$ = $20$.

Consequently, $A \times B$ has $2^{20}$ subsets, so $\vert \mathcal{P} (A\times B) \vert$ = $2^{20}$.

(b) If $\vert A \vert = m$ and $\vert B \vert = n$, for $m, n \in N$, then $\vert A\times B \vert = mn$.

Consequently, $\vert \mathcal{P} (A\times B) \vert$ = $2^{mn}$.
:::

### 3 ($\S 5.1\ \sharp\ 11$)　
For $A, B, C \subseteq \mathcal{U}$, prove that: $A \times (B - C) = (A \times B) - (A \times C)$
註：$\mathcal{U}$ 表示 universal set (所有元素構成的集合)。
:::spoiler solution
$~~~~~~ (x,y) \in A \times (B - C)$ $\qquad$ (由卡氏積 $\times$ 的定義得知) <br> $\Leftrightarrow x \in A$ and $y \in B - C$ $\qquad$ (由差集 $-$ 的定義可得：)<br> $\Leftrightarrow x \in A$ and $(y \in B \text{ and } y \notin C)$ $\quad$ (將 $x$ 的條件與 $y$ 的條件結合：)<br> $\Leftrightarrow (x \in A\text{ and } y \in B) \text{ and } (x \in A\ and\ y \notin C)$ $\quad$ (回到卡氏積 $\times$ 的定義：)
$\Leftrightarrow (x,y) \in A\times B\text{ and } (x,y) \notin A\times C$ $\quad$ (回到差集 $-$ 的定義：)
$\Leftrightarrow (x,y) \in (A\times B) - (A\times C)$...
:::

### 4 ($\S 5.2\ \sharp\ 3$)

Let $A = \{1, 2, 3, 4\}$ and $B = \{x, y, z\}$.

$(a)$ List five functions from $A$ to $B$.
$(b)$ How many functions $f: A \to B$ are there?
$(c)$ How many functions $f: A \to B$ are one-to-one?
$(d)$ How many functions $g: B \to A$ are there?
$(e)$ How many functions $g: B \to A$ are one-to-one?
$(f)$ How many functions $f: A \to B$ satisfy $f(1) = x$?
$(g)$ How many functions $f: A \to B$ satisfy $f(1) = f(2) = x$?
$(h)$ How many functions $f: A \to B$ satisfy $f(1) = x$ and $f(2) = y$?

:::spoiler solution
$(a)\ \lbrace (1,x), (2,x), (3,x), (4,x) \rbrace$ , $\lbrace (1,y), (2,y), (3,y), (4,y) \rbrace$ , $\lbrace (1,z), (2,z), (3,z), (4,z) \rbrace$ , $\lbrace (1,x), (2,y), (3,x), (4,y) \rbrace$ , $\lbrace (1,x), (2,y), (3,z), (4,x) \rbrace$

$(b)\ 3^4\ \ (c)\ 0\ \ (d)\ 4^3\ \ (e)\ 24\ \ (f)\ 3^3\ \ (g)\ 3^2\ \ (h)\ 3^2$
:::

### 5 ($\S 5.2\ \sharp\ 5$)
Let $A, B, C ⊆ R^2$ (i.e., $R\times R$) where $A = \{(x, y)|y = 2x + 1\}$, $B = \{(x, y)|y = 3x\}$, and $C = \{(x, y)|x − y = 7\}$. Determine each of the following:

$(a)\ A ∩ B\ (b)\ B ∩ C$

$(c)\ \overline{\bar{A} \cup \bar{C}}\ (d)\ \bar{B} ∪ \bar{C}$

:::spoiler solution
$(a)\ A \cap B = \lbrace (x,y)|y = 2x + 1$ and $y = 3x \rbrace$

$2x + 1 = 3x \Rightarrow x = 1$.

So $A \cap B = \lbrace (1,3) \rbrace$.

$(b)\ B \cap C = \lbrace (x,y)|y = 3x$ and $y = x - 7 \rbrace$

$3x = x - 7 \Rightarrow 2x = -7$, so $x = \dfrac{-7}{2}$.

Consequently, $B \cap C = \lbrace (\dfrac{-7}{2}\ ,\ 3(\dfrac{-7}{2})) \rbrace = \lbrace (\dfrac{-7}{2}\ ,\ \dfrac{-21}{2}) \rbrace$

$(c)\ \overline{\overline A \cup \overline C} = \overline{\overline A} \cap \overline{\overline C}$ (De Morgan's laws ，又稱：笛摩定律、對偶律) <br> $= A \cap C = \lbrace (x,y)|y = 2x + 1$ and $y = x - 7 \rbrace$
Now, $2x + 1 = x - 7 \Rightarrow x = -8$, and so $A \cap C = \lbrace (-8, -15) \rbrace$.

$(d)$ We know that $\overline B \cup \overline C = \overline{B \cap C}$, and since $B \cap C = \lbrace (\dfrac{-7}{2}\ ,\ \dfrac{-21}{2}) \rbrace$, we have $\overline B \cup \overline C = R^2 - \lbrace (\dfrac{-7}{2}\ ,\ \dfrac{-21}{2}) \rbrace$ <br> $\qquad\quad= \lbrace (x,y)|x \neq \dfrac{-7}{2}\text{ or } y \neq \dfrac{-21}{2} \rbrace$.

:::

### 6 ($\S 5.2\ \sharp\ 15$)

For each of the following functions, determine whether it is one-to-one and determine its range (值域).
$(a) f : Z \to Z,\ f (x) = 2x + 1$
$(b) f : Q \to Q,\ f (x) = 2x + 1$
$(c) f : Z \to Z,\ f (x) = x^3 − x$
$(d) f : R \to R,\ f (x) = e^x$
$(e) f : [\frac{−π}{2}, \frac{π}{2}] \to R,\ f (x) = \sin{x}$
$(f) f : [0, π] \to R,\ f (x) = \sin{x}$
註：$Z$、$Q$、$R$ 分別為所有整數、有理數、實數的集合。
:::spoiler solution
$(a)$ One-to-one.The range is the set of all odd integers.
$(b)$ One-to-one. $Range\ =\ Q$
$(c)$ Since $f(1)=f(0),f$ is not one-to-one.The range of $f=\{0,\pm6,\pm24,\pm60,...\}=\{n^3-n|n\in Z\}.$
$(d)$ One-to-one. $Range=(0,+\infty)=R^+$
$(e)$ One-to-one. $Range=[-1,1]$
$(f)$ Since $f(\cfrac{\pi}{4})=f(\cfrac{3\pi}{4})$, $f$ is not one-to-one. The range of $f=[0,1]$.
:::

### 7 ($\S 5.2\ \sharp\ 17$)
Let $A = \{1, 2, 3, 4, 5\}$, $B = \{w, x, y, z\}$, $A_1 = \{2, 3, 5\}⊆ A$, and $g: A_1 \to B$. In how many ways can $g$ be extended to a function $f : A \to B$? (註：有多少種擴張方式，方可使 $g$ 成為 $f$ 。)

:::spoiler solution
The extension must include $f(1)$ and $f(4)$. Since $|B|=4$ there are four choices for each of $1$ and $4$, so there are $4^2=16$ ways to extend the given function $g$.
:::

### 8 ($\S 5.2\ \sharp\ 18$)

Give an example of a function $f : A \to B$ and $A_1$, $A_2 ⊆ A$ for which $f (A_1 ∩ A_2)\ne f (A_1) ∩ f (A_2)$.

:::spoiler solution
Let $A=\{1,2\},B=\{3,4\}$ and $f=\{(1,3),(2,3)\}.$ For $A_1=\{1\},A_2=\{2\},f(A_1\cap A_2)=f(\varnothing)=\varnothing$, while $f(A_1)\cap f(A_2)=\{3\}\cap \{3\}=\{3\}.$

:::

### 9 ($\S 5.3\ \sharp\ 4$)

Let $A = \{1, 2, 3, 4\}$ and $B = \{1, 2, 3, 4, 5, 6\}$.
$(a)$ How many functions are there from $A$ to $B$? How many of these are one-to-one? How many are onto?
$(b)$ How many functions are there from $B$ to $A$? How many of these are onto? How many are one-to-one?

:::spoiler solution
$(b)$ $4^6$ ; $onto(6, 4)=\binom{4}{4}4^6-\binom{4}{3}3^6+\binom{4}{2}2^6-\binom{4}{1}1^6=\sum_{k=0}^{4}(-1)^k\binom{4}{4-k}(4-k)^6$ ; $0$。
$(a)$ $6^4$ ; $6\times 5\times 4\times 3=\dfrac{6!}{2!}=P(6, 2)$ ; $0$。

$(b)$ $4^6$ ; $onto(6, 4)=\binom{4}{4}4^6-\binom{4}{3}3^6+\binom{4}{2}2^6-\binom{4}{1}1^6=\sum_{k=0}^{4}(-1)^k\binom{4}{4-k}(4-k)^6$ ; $0$。
:::

### 10 ($\S 5.3\ \sharp\ 8$)
A chemist who has **five** assistants is engaged in a research project that calls for **nine** compounds that must be synthesized.
In how many ways can the chemist assign these syntheses to the **five** assistants so that each is working on **at least one synthesis**?
:::spoiler 中文
一位化學家有五位助理，正在進行一項研究計畫，該計畫需要合成九種化合物。這位化學家要如何將這九項合成工作分配給五位助理，使得每位助理至少負責一項工作？共有多少種分配方式？
:::
:::spoiler solution
Let $A$ be the set of compounds and $B$ the set of assistants. Then the number of assignments with no idle assistants is the number of onto functions from set $A$ to set $B$. There are $onto(9, 5)=\binom{5}{5}5^9-\binom{5}{4}4^9+\binom{5}{3}3^9-\binom{5}{2}2^9+\binom{5}{1}1^9=\sum_{k=0}^{5}(-1)^k\binom{5}{5-k}(5-k)^9$ such functions.
九項合成工作以 onto 形式分配給五位助理。
:::

## [作業五] Onto Functions and Stirling Number of the 2nd Kind

### 1 ($\S 5.3\ \sharp\ 10$)

Suppose we have seven different colored balls and four containers numbered I, II, III, and IV.
$(a)$ In how many ways can we distribute the balls so that no container is left empty?
$(b)$ In this collection of seven colored balls, one of them is blue. In how many ways can we distribute the balls so that no container is empty and the blue ball is in container II?
$(c)$ If we remove the numbers from the containers so that we can no longer distinguish them, in how many ways can we distribute the seven colored balls among the four identical containers, with some container(s) possibly empty?
:::spoiler 中文
假設我們有七顆不同顏色的球和四個容器，編號為 I、II、III 和 IV。
（a）有多少種方式可以分配這些球，使得每個容器都至少有一顆球？
（b）在這七顆球中，其中一顆是藍色的。若藍色球必須放在容器 II 中，並且仍要求每個容器都不為空，有多少種分配方式？
（c）若將容器的編號移除，無法區分容器，並允許有些容器為空，則有多少種方式可以分配這七顆不同顏色的球？
:::
:::spoiler solution
$(a)$ $onto(7, 4)=\sum_{k=0}^{4}(-1)^k\binom{4}{4-k}(4-k)^7=4!S(7,4)$

$(b)$ $3!S(6,3)$ (Here container II contains only the blue ball) + $4!S(6,4)$ (Here container II contains more than just the blue ball).
註：藍色球已放入盒子II，則該盒符合題意的可能情況是：(1)只放該藍色球--其它6個色球放入其它3個盒子，不得留空盒、或 (2) 除藍色球外還有其它球--其它6個色球放入4個盒子，不得留空盒。 (1) 的可能放法是：$onto(6, 3)=3!S(6,3)$；而 (2) 則是：$onto(6, 4)=4!S(6,4)$；兩者不會同時成立，以加法原則相加之！

$(c)$ $S(7,4) + S(7,3) + S(7,2) + S(7,1)$.
註："remove the numbers from the containers" 表示盒子己無法區別，即容器是相同的；宜用 Stirling number of the 2nd kind 來想。
:::
### 2 ($\S 5.3\ Ex.\ 5.25$)
At the CH Company, Joan, the supervisor, has a secretary, Teresa, and three other administrative assistants. If seven accounts must be processed, in how many ways can Joan assign the accounts so that each assistant works on at least one account and Teresa’s work $includes$ the most expensive account?
:::spoiler 中文
在 CH 公司，主管 Joan 有一位秘書 Teresa 和另外三位行政助理。如果有七個帳戶需要處理，Joan 可以用多少種不同的方式分配這些帳戶，使得每位助理至少處理一個帳戶，且 Teresa 所負責的帳戶中**包含**最昂貴的那一個帳戶？ $請留意：包含應解讀成\Rightarrow$ <br>$(1)\ Teresa\ 只處理最昂貴的那個帳戶$；或 <br>$(2)\ Teresa\ 除了處理最昂貴的帳戶，並且也處理其它帳戶。$<br>"$包含$"涵蓋(包含)上述兩種情況。$
:::
:::spoiler solution 請依下列講義內容與上課講解吸收消化！
:::

### 3
Let $m, n$ be positive integers with $1 < n ≤ m$. Prove $$S(m+1, n) = S(m, n−1) + nS(m, n).$$

:::spoiler Proofs
下面提供兩種証明方式，任一可也。
#### Proof 1
#### Proof 2
:::

---
### 4 ($\S 5.3\ \sharp\ 11$)
Determine the next two rows $(m =9, 10)$ of Table 5.1 for the Stirling numbers $S(m, n)$, where $1\le n\le m$.

:::spoiler Solution
:::

### 5 ($\S 5.3\ \sharp\ 13$)

$(a)$ How many two-factor unordered factorizations, where each factor is greater than $1$, are there for $156,009$?
:::spoiler 中文
(a) 將 $156,009$ 分解成兩個大於 $1$ 的因數相乘，順序不重要，有多少種分解法？
:::
<br> $(b)$ In how many ways can $156,009$ be factored into two or more factors, each greater than $1$, with no regard to the order of the factors?
:::spoiler 中文
(b) 將 $156,009$ 分解成兩個或以上大於 $1$ 的因數相乘，順序不重要，有多少種分解法？
:::

<br> $(c)$ Let $p_1, p_2, p_3,\cdots,p_n$ be $n$ distinct primes. In how many ways can one factor the product $\prod^n_{i=1}\ p_i$ into two or more factors, each greater than $1$, where the order of the factors is not relevant?
:::spoiler 中文
設 $p_1, p_2, p_3,\cdots,p_n$ 為 $𝑛$ 個互不相同的質數。現在要將它們的乘積 $\prod^n_{i=1}\ p_i$ 分解成兩個或更多個因數相乘，每個因數都必須大於 1，且因數的順序不重要。問題是：有多少種不同的分解方式？
:::
:::spoiler solution [以上三小題請用 Stiling number of the 2nd kind 來聯想]

<br> $(a)$ Since $156,009 = 3\times7\times17\times19\times23$, it follows that there are $S(5,2) = 15$ two-factor unordered factorizations of $156,009$, where each factor is greater than 1. (註：想成將 $156,009$ 的 5 個質因數 ($3, 7, 17, 19, 24$) onto 到 $2$ 個相同容器中(順序不重要)！)

$(b)$ 將 $156,009$ 的 5 個質因數 ($3, 7, 17, 19, 24$) onto 到 $2, 3, 4\ 或\ 5$ 個相同容器中！
$\displaystyle\sum_{i=2}^{5}S(5,i) = S(5,2) + S(5,3) + S(5,4) + S(5,5) = 15 + 25 + 10 + 1 = 51$.

$(c)$ 將 $\prod^n_{i=1}\ p_i$ 的 $n$ 個質因數 ($p_1, p_2, p_3,\cdots,p_n$) onto 到 $2, 3, \cdots 或\ n$ 個相同容器中！擇一發生，適用加法原則，其方法數共有：$\displaystyle\sum_{i=2}^{n}S(n,i)$.
:::

### 6. ($\S 5.3\ \sharp\ 6$)
a) Verify that $5^7=\sum_{i=1}^{5}\binom{5}{i}(i!)S(7,i)$.
b) Provide a combinatorial argument to prove that for all $m, n ∈ Z^+$, $m^n=\sum_{i=1}^m\binom{m}{i}(i!)S(n, i)$.
:::spoiler solution
$(a)~5^7=\sum_{i=1}^{5}\binom{5}{i}(i!)S(7,i)$
$~\qquad=\binom{5}{1}(1!)S(7,1)+\binom{5}{2}(2!)S(7,2) +\binom{5}{3}(3!)S(7,3)+\binom{5}{4}(4!)S(7,4)+\binom{5}{5}(5!)S(7,5)$
$~\qquad= (5)(1)(1) + (10)(2)(63) + (10)(6)(301) + (5)(24)(350) + (1)(120)(14)$$~\qquad= 78,125 = 5^7$

$(b)~m^n~可視為所有~f:A\rightarrow B~函數的可能個數；其中~|A|=m、|B|=n。$
$~\quad由於~(i!)S(n, i)=onto(n,i),~正為~onto~函數~f:A\rightarrow B_i~~的所有可能個數，$
$~\quad其中~B_i\subseteq B~且~|B_i|=i。而滿足~B_i\subseteq B~且~|B_i|=i~的集合個數共有\binom{m}{i}~個，$
$~\quad所以~onto~函數~f:A\rightarrow B_i~共計有\binom{m}{i}onto(n,i)~個。$
$~\quad於是所有~f:A\rightarrow B~函數的可能個數恰為A~onto~到各個~B_i~函數個數的總和:$
$$m^n=\sum_{i=1}^m\binom{m}{i}onto(n,i)=\sum_{i=1}^m\binom{m}{i}(i!)S(n, i).$$ $~\quad原式得証。$
:::
### 7 ($\S 5.4\ \sharp\ 5$)

Let $|A| = 5$.
$(a)$ What is $|A \times A|$?
$(b)$ How many functions $f : A \times A \to A$ are there?
$(c)$ How many closed binary operations are there on $A$?
$(d)$ How many of these closed binary operations are commutative?

:::spoiler solution
用 $n\times n$ 矩陣來表示 function，每個 entry 的值可以是 $A$ 的任一成員；比較容易聯想！
$(a)~ 25~ (=5\times5)$
$(b)~ 5^{25}$
$(c)~ 5^{25}$
$(d)$ Owing to the commutative property, the diagonal $f(i,i)$ for $1\le i \le 5$ may be any element of $A$, and $f(i,j)=f(j,i)$ for $1\lt i\lt j \le 5$, each of which can also be any element of $A$. The former has $5^5$ possibilities, and the latter have $5^{4+3+2+1}=5^{10}$ optiones. Together, there are $5^{5}\times 5^{10}=5^{15}$ closed binary operations.
:::

### 8 ($\S 5.4\ \sharp\ 6$)

Let $A = \{x, a, b, c, d\}$.
$(a)$ How many closed binary operations $f$ on $A$ satisfy $f (a, b) = c$?
$(b)$ How many of the functions $f$ in part $(a)$ have $x$ as an identity?
$(c)$ How many of the functions $f$ in part $(a)$ have an identity?
$(d)$ How many of the functions $f$ in part $(c)$ are commutative?

:::spoiler solution

用 $n\times n$ 矩陣來表示 function，每個 entry 的值可以是 $A$ 的任一成員來解題！
$(a)\ 5^{24}$
$5\times 5$ 中的 $f (a, b) = c$，其它 entries 可以是 $A$ 的任一成員，個數有 5^{5\times 5-1}=5^{24}$

$(b)\ 5^{15}$
$x$ 是 identity，所以 $f(\alpha,x)=\alpha=f(x,\alpha),\ \alpha\in A$；除了 $f (a, b) = c$ 之外，其它 $15(=25-9-1)$ 個 entries 可以是 $A$ 的任一成員，個數有 $5^{15}$

$(c)\ 3\times5^{15}$, Because neither $a$ nor $b$ can be an identity.
由於 $f(a,b)=c$，所以 a 且 b 不可以是 identity！(若是的話，$f(\alpha, a)=a=f(a, \alpha)$、$f(\alpha, b)=b=f(b, \alpha)$，但 $f(a,b)=c$)。於是 identity 可以是 $x, c, d$ 三者之一；個數有 $3\times 5^{15}$

$(d)\ 3\times5^9$
先回到 (b)：$x$ 是 identity 時有 $5^{15}$ 個 funtions。要求其必須對稱，又因 $f(a,b)=c$，可知 $f(b, a)=c$，此時上三角的 entries 共有 $4+3+2+1-1=9$ 個，每個皆可是 $A$ 的任一成員，identity 可以是 $x, c, d$ 三者之一，總個數有 $3\times5^{9}$。
:::

### 9 ($\S 5.4\ \sharp\ 8$)

Let $A = \{2, 4, 8, 16, 32\}$, and consider the closed binary operation $f : A \times A\to A$ where $f (a, b) =gcd(a, b)$. Does $f$ have an identity element?

:::spoiler solution

Each element in A is of the form $2^i$ for some $1 \leq i \leq 5$, and $gcd(2^i,2^5) = 2^i = gcd(2^5, 2^i)$, so $2^5 = 32$ is the identity element for $f$.

| | 2 | 4 | 8 | 16 | 32 |
|:--: | :--: | :--: |:--: | :--: | :--: |
| 2 |2 | 2 | 2 |2 | 2 |
| 4 |2 | 4 | 4 |4 | 4 |
| 8 |2| 4 |8 | 8 |8 |
| 16 |2|4 |8 | 16 | 16|
| 32 |2|4 |8 | 16 |32|

:::

### 10 ($\S 5.4\ \sharp\ 11$)

For $\varnothing \ne A ⊆ Z^+$, let $f, g: A \times A \to A$ be the closed binary operations defined by $f (a, b) = min\{a, b\}$ and $g(a, b) =
max\{a, b\}$. Does $f$ have an identity element? Does $g$?

::: spoiler solution
By the Well-Ordering Principle $A$ has a least element and this same element is the identity for $g$. If $A$ is finite then $A$ will have a largest element and this same element will be the identity for $f$. If $A$ is infinite then $f$ cannot have an identity.
根據良序原理，集合 𝐴 存在最小元素，該元素同時也是運算
𝑔 的單位元。若 𝐴 是有限集合，則它也存在最大元素，該元素將成為運算 𝑓 的單位元。然而，若 𝐴 是無限集合，則運算 𝑓 將不可能存在單位元。
以下用 $A=\{a, b, c, d\},\ a\lt b\lt c \lt d$ 為例來看 $f$ 和 $g$：

|$f$| a | b | c | d |
|:--: | :--: | :--: |:--: | :--: |
| a |a | a | a |a|
| b |a| b | b |b |
| c |a| b |c | c |
| d | a |b | c | d|

$d$ 為 $f$ 的 identity！($d=max\{x|x\in A\}$)

|$g$| a | b | c | d |
|:--: | :--: | :--: |:--: | :--: |
| a |a |b | c |d|
| b |b| b | c |d |
| c |c| c |c | d |
| d | d |d |d | d|

$a$ 為 $g$ 的 identity！($a=min\{x|x\in A\}$)
:::

---

## [作業六]
:::info
### The Pigeonhole Principle
If $m$ pigeons occupy $n$ pigeonholes and $m\lt n$, then at least one pigeonhole has two or more pigeons roosting in it.

### 鴿籠原理
當 $m$ 隻鴿子飛回 $n$ 個籠子，而 $m\lt n$ ，則至少有一個鴿籠有兩隻或以上的鴿子。
:::
### 1. ($\S 5.5\ ex\ 5.39$)
An office employs $13$ file clerks, so at least two of them must have birthdays during the same month.

:::spoiler 中文
一間公司僱用 $13$ 名檔案文員，其中至少有兩人的生日為同一月
:::

:::spoiler solution
可想成有 $13$ 隻鴿子($13$ 名檔案文員)飛進 $12$ 個鴿籠($12$ 月份)，由鴿籠原理，至少會有 $1$ 個鴿籠關至少 $2$ 隻鴿子，即至少有兩人的生日在同一月份。
:::

### 2. ($\S 5.5\ ex\ 5.40$)
Larry returns from the laundromat with $12$ pairs of socks (each pair a different color) in a laundry bag. Drawing the socks from the bag randomly, how many he has to draw at most of them to get a matched pair?

:::spoiler 中文
Larry從自助洗衣店回來，手裡拿著一個洗衣袋，裡面裝著 $12$ 雙襪子（每雙顏色都不同）。 從袋子裡隨機抽出襪子，最多抽出多少隻才能得到一雙配對的襪子?
:::

:::spoiler solution
12 雙顏色不同的襪子，共有 24 隻，Larry 的隨機取法，有可能取出 12 隻皆不是同一雙，在取第 13 隻時必定會與前 12 隻湊出一雙。因而Larry 最多任取13 隻襪子，即必可湊出成對的襪子。
將 12 雙不同顏色的襪子想成鴿籠，那麼只要 13 隻鴿子(即此題的襪子)回鴿籠，即可由鴿籠原理得知：至少有一鴿籠有兩隻以上的鴿子(一雙成對的襪子)。
:::

### 3. ($\S 5.5\ ex\ 5.44$)
Any subset of size $6$ from the set $S = \{1, 2, 3, . . . , 9\}$ must contain two elements whose sum is $10$.
:::spoiler 中文
$S = \{1, 2, 3, . . . , 9\}$ 中任何個數為 6 的部份集合，必定含有兩個元素其和為 10。
:::
:::spoiler solution
Here the pigeons constitute a six-element subset of $\{1, 2, 3, . . . , 9\}$, and the pigeonholes are the subsets $\{1, 9\}, \{2, 8\}, \{3, 7\}, \{4, 6\}, \{5\}$. When the six pigeons go to their respective pigeonholes, they must fill at least one of the two-element subsets whose members sum to 10.

將 $\{1, 9\}, \{2, 8\}, \{3, 7\}, \{4, 6\}, \{5\}$ 設定為鴿籠，共 5 個，$S$ 部份集合的 6 個元素想成有編號 1~6 的 6 隻鴿子，其會回到含有所屬編號的籠子；則由鴿籠原理得知：至少有一鴿籠有兩隻以上的鴿子--該鴿籠內的兩個元素相加恰為 10 。註：$\{5\}$ 至多只有一隻鴿子飛入。
:::

### 4. ($\S 5.5\ ex\ 5.45$)
Triangle $ACE$ is equilateral with $AC = 1$. If five points are selected from the interior of the triangle, there are at least two whose distance apart is less than $\dfrac{1}{2}$.
:::spoiler 中文
正三角形 $ACE$ 其邊長 $AC=1$，自 $ACE$ 內部取出的 5 個點，必存在兩個點，其距離必小於 $\dfrac{1}{2}$。
:::
:::spoiler solution
For the triangle in Fig.$5$.$8$, the four smaller triangles are congruent equilateral triangles and $AB = \dfrac{1}{2}$. We break up the interior of triangle $ACE$ into the following four regions,which are mutually disjoint in pairs:
$R1:$ the interior of triangle $BCD$ together with the points on the segment $BD$, excluding $B$ and $D$.
$R2:$ the interior of triangle $ABF$.
$R3:$ the interior of triangle $BDF$ together with the points on the segments $BF$ and $DF$, excluding $B$, $D$, and $F$.
$R4:$ the interior of triangle $FDE$.
Now we apply the pigeonhole principle. Five points in the interior of triangle $ACE$ must be such that at least two of them are in one of the four regions $R_i$ , $1 ≤ i ≤ 4$, where any two points are separated by a distance less than $\dfrac{1}{2}$.

將邊長為 1 的正三角形，如圖5.8般切分出 4 個邊長為 $\frac{1}{2}$ 的小正三角形--將其設為鴿籠，將自原三角形內部取出的 5 個點想成為鴿子；則由鴿籠原理得知：至少有一鴿籠(小正三角形)有兩隻以上的鴿子(兩個以上的點)--而那兩個在同一小三角形內的點，其距離必小於 $\frac{1}{2}$。
:::
### ５. ($\S 5.5\ ex\ 5.41$)
Wilma is given a tape that contains $500,000$ “words” of four or fewer lowercase letters. (Consecutive words on the tape are separated by a blank character.) Can it be that the 500,000 words are all distinct?
:::spoiler 中文

Wilma持有的紙帶上有 $500,000$ 個字詞--皆由 ４ 或少於 ４ 個小寫字元所構成(字詞間以空格隔開)。這 $500,000$ 個字詞皆相異嗎？
:::
:::spoiler solution
From the rules of sum and product, the total number of different possible words, using four or fewer letters, is
$\qquad 26^4 + 26^3 + 26^2 + 26 = 475,254$.
With these 475,254 words as the pigeonholes, and the 500,000 words on the tape as the pigeons, it follows that at least one word is repeated on the tape.
由於每個字詞 (word) 為 ４ 或少於 ４ 個小寫字元，而英文小寫字元共計有 26 個，由乘法與加法原則可知字詞總數為：
$\qquad 26^4 + 26^3 + 26^2 + 26 = 475,254$。
將之視為籠子總數，而 $500,000$ 個字詞視為鴿子，則由鴿籠原理得知：至少有一鴿籠(字詞)有兩隻以上的鴿子(該字詞重複出現了)。因而此 $500,000$ 個字詞不會同異！
:::
### 6 ($\S 5.5\ ex\ 5.49$)
Let $S ⊂ Z^+$, where $|S| = 37$. $|S|$ contains two elements that have the same remainder upon division by $36$.
於正整數中任取 37 個做為集合 $S$，則 $S$ 必包含兩個元素，其在除以 36 時會同餘。
Here the pigeons are the 37 positive integers in $S$.
We know from the division algorithm (of Theorem 4.5) that when any positive integer $n$ is divided by 36, there exists a unique quotient q and unique remainder $r$, where
$\qquad n = 36q + r,\ 0 ≤ r < 36$.
The 36 possible values of $r$ constitute the pigeonholes, and the result is now established by the pigeonhole principle.

## [作業七] Solving/Counting Problems by Generating Functions
### 1. Ex. 9.1
Mildred buys 12 oranges for her children, Grace, Mary, and Frank. In how many ways can she distribute the oranges so that Grace gets at least four, and Mary and Frank get at least two, but Frank gets no more than five?
:::spoiler solution

The generating polynomials of
Grace: $x^4+x^5+x^6+x^7+x^8$;
Mary : $x^2+x^3+x^4+x^5+x^6$;
Frank: $x^2+x^3+x^4+x^5$.
The generating polynomials of the requirement is:
$$f(x)=(x^4+x^5+x^6+x^7+x^8)(x^2+x^3+x^4+x^5+x^6)(x^2+x^3+x^4+x^5)$$
The answer is the coefficient of term $x^{12}$ in $f(x)$.
:::
### 2. Combinations with repetition of 3 distinct objects

Consider objects $a, a, a, b, b, c$ where $a, b, c$ are distinct. Answer the following questions using generating function:
(a) List all possible selections for these objects (e.g., selecting 0, 1, 2, ..., or 6 objects, respectively).
(b) In how many ways can we select 4 out of these objects?
:::spoiler solution
:::
(a) The ways for selecting
(1) $a$ can be represented as $1+ax+a^2x^2+a^3x^3$;
(2) $b$ can be represented as $1+bx+b^2x^2$;
(3) $b$ can be represented as $1+cx$.
The generating function of selecting them is
\begin{aligned}
G(x) &= (1+ax+a^2x^2+a^3x^3)(1+bx+b^2x^2)
(1+cx) \\
&=(1+(a+b)x+(a^2+ab+b^2)x^2+(a^3+a^2b+ab^2)x^3+(a^2b^2+a^3b)x^4+a^3b^2x^5)(1+cx) \\
&=1+(a+b+c)x+(a^2+ab+b^2+ac+bc)x^2+(a^3+a^2b+ab^2+a^2c+abc+b^2c)x^3+ \\& ~~~~~~ (a^2b^2+a^3b+a^3c+a^2bc+ab^2c)x^4+(a^3b^2+a^2b^2c+a^3bc)x^5+a^3b^2cx^6
\end{aligned}
That is, the possible ways for selecting $r\ (=0, 1, \cdots,6)$ objects are listed as follows.

| $r$ | selections | # of ways |
| :-----: | -------- |:--:|
| 0 | $\emptyset$| 1 |
| 1 | $a, b, c$| 3 |
| 2 | $aa, ab, bb, ac, bc$ | 5 |
| 3 | $aaa, aab, abb, aac, abc, bbc$ | 6 |
| 4 | $aabb, aaab, aaac, aabc, abbc$ | 5 |
| 5 | $aaabb, aabbc, aaabc$ | 3 |
| 6 | $aaabbc$ | 1 |

(b) The answer is 5, which is exactly the coefficient of $x^4$ in $G(x)$ by setting $a=b=c=1$.
:::
### 3 ($\S 9.2\ ex\ 9.4$) Combinations without repetition
In how many ways can we select, without repetitions, $r$ objects from $n$ distinct objects?
:::spoiler solution
Let the $n$ distinct objects be named as $a_1, a_2, \cdots, a_n$.
The generating polynomial of selecting $a_i$ without repetitions can be represed as $1+x$ (either select it or not, without repetitions) for $1\le i\le n$. The corresponding genrating function is
$f(x)=(1+x)^n=\displaystyle\sum_{k=0}^n\binom{n}{k}x^k$.
The answer is the coefficient of $x^r$ in $f(x)$, which is $\dbinom{n}{r}$.
:::

### 4. ($\S 9.2\ ex\ 9.11$) Combinations with repetition
In how many ways can we select, with repetitions allowed, $r$ objects from $n$ distinct objects?
:::spoiler solution
:::
Let the $n$ distinct objects be named as $a_1, a_2, \cdots, a_n$.
The generating polynomial of selecting $a_i$ *with repetitions* can be represed as $1+x+x^2+x^3+\cdots$ (either select it one/two/three/... times or not) for $1\le i\le n$. The corresponding genrating function is
$f(x)=(1+x+x^2+x^3+\cdots)^n=\displaystyle\sum_{k=0}^nx^k$
$\qquad\ =(\dfrac{1}{1-x})^n = (1-x)^{-n}=\displaystyle\sum_{k=0}^{\infty}\binom{k+n-1}{k}x^k$.

The answer is the coefficient of $x^r$ in $f(x)$, which is $\dbinom{r+n-1}{r}$ (just like we learnt from combinations with repetitions).

### 5. ($\S 9.2\ ex\ 9.12$) Compositions
(a) Counting the $compositions$ of a positive integer $5$ using generating functions.
:::spoiler solution
5 可由 1, 2, 3, 4, 5 個成員(相加)組成而得，而每個成員可以是 1, 2, 3, 4, 5。每個成員可能的個數 (1, 或 2, 或 3, ..., 5；只能為其中之一)，可用生成多項式為：
$\qquad \qquad \qquad x+x^2+x^3+x^4+x^5$
表示(不得有 $1$ 那一項！)。
(1) 由 1 個成員相加為 5 : 其生成函數 $x+x^2+x^3+x^4+x^5$ 中的 $x^5$，只有 1 種組成。
(2) 由 2 個成員相加為 5 : 檢視生成函數 $(x+x^2+x^3+x^4+x^5)^2$ 展開後 $x^5$ 的係數，可知有 $xx^4$、$x^2x^3$、$x^3x^2$、$x^4x$ 4 種。
(3) 由 3 個成員相加出 5 : 檢視生成函數 $(x+x^2+x^3+x^4+x^5)^3$ 展開後 $x^5$ 的係數，可知有 $xxx^3$、$xx^2x^2$、$xx^3x$、$x^2xx^2$、$x^2x^2x$、$x^3xx$ 6 種。
(4) 由 4 個成員相加成 5 : 檢視生成函數 $(x+x^2+x^3+x^4+x^5)^4$ 展開後 $x^5$ 的係數，可知有 $xxxx^2$、$xxx^2x$、$xx^2xx$、$x^2xxx$ 4 種。
(5) 由 5 個成員相加成 5 : 檢視生成函數 $(x+x^2+x^3+x^4+x^5)^5$ 展開後 $x^5$ 的係數，可知僅有 $xxxxx$， 1 種。
利用 rule of sum 得知 $5$ 的組成總共有 16 種。
:::

(b) General compositions:
Counting the $compositions$ of a positive integer $n$ using generating functions.
:::spoiler solution
Based on the discussion from (a), the required answer is at the $x^n$ coefficient of generating function:
\begin{aligned}g(x) &= \displaystyle\sum_{k=1}^{\infty}(x+x^2+x^3+\cdots)^k \\
&=\displaystyle\sum_{k=1}^{\infty}(\frac{x}{1-x})^k \qquad \text{replace }\frac{x}{1-x} \text{by } y\\
&=\displaystyle\sum_{k=1}^{\infty}y^k = y\sum_{k=0}^{\infty}y^k = y(\frac{1}{1-y}) =(\frac{x}{1-x})[\frac{1}{1-(\frac{x}{1-x})}]=(\frac{x}{1-x})[\frac{1}{\frac{1-x-x}{1-x}}]\\
&=\frac{x}{1-2x} = x[1+(2x)+(2x)^2+(2x)^3+\cdots] \\
&=2^0x+2^1x^2+2^2x^3+2^3x^4+\cdots+2^{n-1}x^n+\cdots
\end{aligned}

Thus the number of compositions of a positive integer $n$ is the coefficient of $x^n$ in $g(x)$, which is $2^{n-1}$.
:::
### 6 ($\S 9.2\ ex\ 9.13$) Palindromes
#### (a) Counting the $palindromes$ of a positive integer $6$ and $7$ using generating functions.
:::spoiler solution
Based on the above figure, for 7 (6), there are $1 + (1 + 2 + 4) = 1 + (1 + 2^1 + 2^2) = 1 + (2^3−1) = 2^3$
palindromes.
$6\ (7)$ 逐次減 $0、2、4、6$，所減的值分配至左右兩端，左(右)端將所分得的數字取其任一組成，可得所屬迴文 (組成與迴文有 1 對 1 對應關係。本題中所減的 $0, 2, 4, 6$ 分配至左右兩端，左(右)端可得 $0(=\frac{0}{2}), 1(=\frac{2}{2}), 2(=\frac{4}{2}), 3(=\frac{6}{2})$ ，而其組成個數分別為 $1, 1, 2, 4$，因而迴文個數亦分別為 $1, 1, 2, 4$。
:::
#### (b) Counting the $palindromes$ of a positive integer $n$ using generating functions.
:::spoiler solution
既是迴文，必然左端與右端對稱。先考慮 $n$ 為偶數且 $n=2k$, $k\gt 0$，則 $n$ 可分別減 $0、2、4、6、\cdots、2k$，所減的值均分給左右兩端，任一端可分得 $1、1、2、3、\cdots、k$，而其組成恰為 $1、2^0、2^1、2^2、\cdots、2^{k-1}$；每一組成對應至一個迴文，於是總共迴文數為：
$\qquad\qquad1+2^0+2^1+2^2+\cdots+2^{k-1}=1+(2^k-1)=2^k=2^{\frac{n}{2}}.$
當 $n$ 為奇數且 $n=2k+1$, $k\gt 0$，則 $n$ 亦可分別減 $0、2、4、6、\cdots、2k$，所減的值均分給左右兩端，任一端可分得 $1、1、2、3、\cdots、k$，而其組成恰為 $1、2^0、2^1、2^2、\cdots、2^{k-1}$；每一組成對應至一個迴文，於是總共迴文數為：
$\qquad\qquad1+2^0+2^1+2^2+\cdots+2^{k-1}=1+(2^k-1)=2^k=2^{\lfloor\frac{n}{2}\rfloor}.$
總結：正整數 $n$ 的迴文個數為 $2^{\lfloor\frac{n}{2}\rfloor}$.
:::
### 7 ($\S 9.2\ ex\ 9.14$)
In how many ways can a police captain distribute 24 rifle shells to four police officers so that each officer gets at least three shells, but not more than eight?
:::spoiler solution
用 combinations with repetition 來解的話，可列式為：
$\qquad\qquad c_1+c_2+c_3+c_4=24,\ 3 \le c_i \le 8\text{ for }1\le i\le 4.$
上式限制式多，不易求解。可考慮生成函數！
每位警員可得槍套個數的生成函數為：
$\qquad\qquad\qquad x^3+x^4+\cdots+x^8$
四位警員可得槍套個數的生成函數為
$\qquad\qquad f(x)=(x^3+x^4+\cdots+x^8)^4$
所求即為 $f(x)$ 中 $x^{24}$ 的係數：
\begin{aligned}
(x^3+x^4+\cdots+x^8)^4 = x^4x^3(1+x+\cdots+x^5) = x^{12}(\frac{1-x^6}{1-x})^4
\end{aligned}
由上可知所求即為 $(\frac{1-x^6}{1-x})^4$ 中 $x^{12}$ 的係數：
\begin{aligned}
(\frac{1-x^6}{1-x})^4 &= (1-x^6)^4(1-x)^{-4} \\
&= [\binom{4}{0}+\binom{4}{1}(-x^6)+\binom{4}{2}(-x^6)^2+\binom{4}{3}(-x^6)^3+\binom{4}{4}(-x^6)^4][\binom{-4}{0}+\binom{-4}{1}(-x)+\binom{-4}{2}(-x)^{2}+\binom{-4}{3}(-x)^{3}+\cdots] \\
&= [\binom{4}{0}-\binom{4}{1}x^6+\binom{4}{2}x^{12}-\binom{4}{3}x^{18}+\binom{4}{4}x^{24}][\binom{-4}{0}-\binom{-4}{1}x+\binom{-4}{2}x^{2}-\binom{-4}{3}x^{3}+\cdots] \\
\end{aligned}
其 $x^{12}$ 的係數為：
\begin{aligned}
&\qquad 1\binom{-4}{12}(-1)^{12}-\binom{4}{1}\binom{-4}{6}(-1)^{6}+\binom{4}{2}\binom{-4}{0}1 \\
&= \binom{15}{2}-\binom{4}{1}\binom{9}{6}+\binom{4}{2} = 125. \\
\end{aligned}
:::
### 8 ($\S 9.2\ ex\ 9.15$)
for all $n\in \mathbb{Z}^+$, $\dbinom{2n}{n}=\displaystyle\sum_{i=0}^{n}\dbinom{n}{i}^2$.
:::spoiler solution
既利用生成函數，宜將 $\binom{2n}{n}$ 想成 $x^n$ 前的係數 (其形式$\binom{2n}{n}$ 很像兩項式係數)：$\binom{2n}{n}x^n$！此時生成函數即為
$\qquad\qquad\sum_{k=0}^{2n}\binom{2n}{k}x^k=(1+x)^{2n}=[(1+x)^n]^2$。

我們關心的是 $x^n$ 的係數，亦即 $\binom{2n}{n}$；它在等號的左邊，我們試著看等號右邊 $x^n$ 的係數；
$\qquad[(1+x)^n]^2=(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n)(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots+\binom{n}{n}x^n)$
上式乘開後，$x^n$ 的係數為:
$\qquad\qquad\binom{n}{0}\binom{n}{n}+\binom{n}{1}\binom{n}{n-1}+\binom{n}{2}\binom{n}{n-2}+\cdots+\binom{n}{n}\binom{n}{0}$
$\qquad\quad=\binom{n}{0}\binom{n}{0}+\binom{n}{1}\binom{n}{1}+\binom{n}{2}\binom{n}{2}+\cdots+\binom{n}{n}\binom{n}{n}$
$\qquad\quad=\sum_{i=0}^n\binom{n}{i}\binom{n}{i}$
$\qquad\quad=\sum_{i=0}^n\binom{n}{i}^2$

基於等號兩邊的 $x^n$ 係數必定相等，所以：$\binom{2n}{n}=\sum_{i=0}^{n}\binom{n}{i}^2$。
:::

---

### 9 ($\S 9.3$) Partitions
#### (a) Counting the number of partitions for 10.
:::spoiler solution
10 的分割可以是若干個
(1) 1's: $1+x+x^2+x^3+\cdots+x^{10}$
(2) 2's: $1+x^2+x^4+x^6+x^8+x^{10}$
(3) 3's: $1+x^3+x^6+x^9$
(4) 4's: $1+x^4+x^8$
$\quad\ \cdots$
(10) 10: $1+x^{10}$
其間沒有順序的考量 (without regard to order)，其生成函數為：
$g(x)=(1+x+x^2+x^3+\cdots+x^{10})(1+x^2+x^4+x^6+x^8)(1+x^3+x^6+x^9)\cdots(1+x^{10})$
所求即為 $g(x)$ 展開後 $x^{10}$ 的係數。為精簡上式，可用其 infinite series 表示：
\begin{aligned}
f(x)&=(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^6+\cdots)(1+x^3+x^6+x^9+\cdots)\cdots(1+x^{10}+x^{20}+x^{30}+\cdots) \\
&=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}\cdots\frac{1}{1-x^{10}} \\
&=\prod_{i=1}^{10}\frac{1}{1-x^i}
\end{aligned}
:::

#### (b) Counting the number of partitions for positive integer $n$.
:::spoiler solution
Following (a), we know that the generating function for $n$'s partitions, denoted as, $P(x)$ is
$$\prod_{i=1}^{\infty}\frac{1}{1-x^i}.$$
That is, $P(x)$ generates $p(0),\ p(1),\ p(2),\ \cdots$ where $p(i)$ is the coefficient of $x^i$ in $P(x)$ (or the number of partitions of integer $i$) for $i\in \{0, 1, 2, \cdots\}$.
:::


:::danger
### Compositions
Compose a positive integer $n$ by positive summands (*with* regard to *order*)
### Partitions
Partition a positive integer $n$ by positive summands (*without* regard to *order*)
:::warning
"每個"**組成**的成員可以是 1, 2, 3, ... 順序是有關的；每個組成成員的生成函數可表示為 $1+x+x^2+x^3+\cdots$； 且每個皆可選 1, 2, 3, ... 相加湊出 $n$。
**分割**則沒有"每個"成員的概念！然可想成分割成員可以是若干個 1's, 2's, 3's, ... 順序是無關的；分割成員的生成函數分別可表示為 $(1+x+x^2+x^3+\cdots)$ 若干個1、$(1+x^2+x^4+x^6+\cdots)$ 若干個2、$(1+x^3+x^6+x^9+\cdots)$ 若干個3、...；所有選出的成員相加湊出 $n$。
:::

### 10 ($\S 9.3\ \sharp\ 6$)
What is the generating function for the number of partitions of $n ∈ \mathbb{N}$ into summands that (a) cannot occur more than five times; and (b) cannot exceed $12$ and cannot occur more than five times?

:::spoiler solution
:::
(a)
$\qquad f(x)=(1+x+x^2+...+x^5)(1+x^2+x^4+...+x^{10})\cdots$
$\qquad=\displaystyle\prod\limits_{i = 1}^{\infty}{(1+x^i+x^{2i}+...+x^{5i})}=\prod\limits_{i = 1}^{\infty}{[(1-x^{6i})/(1-x^i)]}$
(b)
$\qquad \displaystyle\prod\limits_{i = 1}^{12}{(1+x^i+x^{2i}+...+x^{5i})}=\prod\limits_{i = 1}^{12}{[(1-x^{6i})/(1-x^i)]}$

---

### 11 ($\S 9.1\ \sharp\ 2$)
Determine the generating function for the number of ways to distribute $35$ pennies (from an unlimited supply) among five children if (a) there are no restrictions; (b) each child gets at least $1¢$; \(c) each child gets at least $2¢$; (d) the oldest child gets at least $10¢$; and (e) the two youngest children must each get at least $10¢$.

:::spoiler 中文
將35個硬幣分給五個小孩，解:
(a)生成函數
(b)每個小孩至少拿一個硬幣的生成函數
(c)每個小孩至少拿二個硬幣的生成函數
(d)最大的小孩至少拿十個硬幣的生成函數
(e)兩個最小的小孩至少拿十個硬幣的生成函數
:::

:::spoiler solution
$(a) (1+x+x^2+...+x^{35})^5~~ or~~ (1+x+x^2+...)^5$

$(b) (x+x^2+...+x^{35})^5~~ or~~ x^5(1+x+x^2+...)^5$

$(c) (x^2+x^3+...x^{35})^5~~ or~~ x^{10}(1+x+x^2+...)^5$

$(d) (1+x+x^2+...x^{35})^4(x^{10}+x^{11}+...+x^{35}) ~~ or~~ (1+x+x^2+...)^4(x^{10}+x^{11}+x^{12}...)$

$(e) (x^{10}+x^{11}+...+x^{25})^2(1+x+x^2+...+x^{15})^3 ~~ or~~ (x^{10}+x^{11}+...)^2(1+x+x^2+...)^3$
:::

### 12 ($\S 9.1\ \sharp\ 5$)
Find the generating function for the number of integer solutions to the equation $c_1 + c_2 + c_3 + c_4 =20$ where $−3 ≤ c_1, −3 ≤ c_2, −5 ≤ c_3 ≤ 5,$ and $0 ≤ c_4$.

:::spoiler solution
:::
$\qquad c_1+c_2+c_3+c_4=20,-3 \le c_1,c_2,-5 \le c_3 \le 5,0 \le c_4$
設法將各變數 $c_i$ 的解範圍訂在 $x_i \ge 0$！令 $x_1=c_1+3,\ x_2=c_2+3,\ x_3=c_3+5, \ x_4=c_4$，此時
$\qquad (3+c_1)+(3+c_2)+(5+c_3)+c_4=31$；
亦即：
$\qquad x_1+x_2+x_3+x_4=31,\ x_1,x_2,x_4\ge 0,\ 10\ge x_3 \ge 0$
Consequently, the answer is the coefficient of $\ x^{31}$ in the generating function
$\qquad (1+x+x^2+...)^3(1+x+x^2+...+x^{10})$
:::

### 13 ($\S 9.2\ \sharp\ 10$)
In how many ways can two dozen identical robots be assigned to four assembly lines with (a) at least three robots assigned to each line? (b) at least three, but no more than nine, robots assigned to each line?

:::spoiler solution
(a) Each assembly line could obtain 3 or more robots, represented by $(x^3+x^4+...)$. The generating function for the 4 assembly lines becomes:
$\qquad\qquad(x^3+x^4+...)^4 = x^{12}(1+x+x^2+...)^4 = x^{12}(1-x)^{-4}$.
The answer is the coefficient of $\ x^{24}$ in $x^{12}(1-x)^{-4}$, or equivalently, that of $\ x^{12}$ in $(1-x)^{-4}$, which is
$\begin{pmatrix} -4 \\ 12 \end{pmatrix}(-1)^{12} = (-1)^{12}\begin{pmatrix} 12+4-1 \\ 12 \end{pmatrix}(-1)^{12} = \begin{pmatrix} 15 \\ 12 \end{pmatrix}$.
Hint：$(1-x)^{-n} (= \dfrac{1}{(1-x)^n}) = (1+(-x))^{-n}= \displaystyle\sum_{k=0}^\infty(-1)^k\binom{k+n-1}{k}(-x)^k =
\sum_{k=0}^{\infty}\binom{k+n-1}{k}x^k$.
注意：$(1-x)^{-4}$ 中 $\ x^{12}$ 的係數恰為$x_1+x_2+x_3+x_4=12$ 的非負整整解個數 (兩者有 1 對 1 的對應關係)，亦即 $\binom{12+4-1}{12}=\binom{15}{12}$！
(b) Each assembly line could obtain 3 or more, but no more than 9 robots, represented by $(x^3+x^4+...+x^9)$. The generating function for the 4 assembly lines becomes: $(x^2+x^4+...+x^9)^4 = x^{12}(1+x+x^2+...+x^6)^4$. The answer is the coefficient of $\ x^{24}$ in $x^{12}(1+x+x^2+...+x^6)^{4}$, or equivalently, that of $\ x^{12}$ in $(1+x+x^2+...+x^6)^{4}$. (考試時作答至此即可)
Since $\qquad(1+x+x^2+...+x^6)^{4}=(\dfrac{1-x^7}{1-x})^4= (1-x^7)^4(1-x)^{-4}= (1+(-x^7))^4(1+(-x)^{-4}$
$\qquad = [1-\binom{4}{1}(-x^7)+\binom{4}{2}(-x^7)^{2}+\binom{4}{3}(-x^7)^{3}+(-x^7)^{4}][\binom{-4}{0}+\binom{-4}{1}(-x)+\cdots+\binom{-4}{5}(-x)^5+\cdots+\binom{-4}{12}(-x)^{12}+\cdots]$
$\qquad = [1-4x^7+\binom{4}{2}x^{14}-\binom{4}{3}x^{21}+x^{28}][1-\binom{-4}{1}x+\cdots-\binom{-4}{5}x^5+\cdots+\binom{-4}{12}x^{12}+\cdots],$
the coefficient of $x^{12}$ is
$\qquad 1\dbinom{-4}{12}+(-4)\dbinom{-4}{5} = \dbinom{12-4+1}{12}+(-4)\dbinom{5+4-1}{5} =\dbinom{15}{12}-4\dbinom{8}{5}$.
:::

### 14 ($\S 9.2\ \sharp\ 16$)
How can Mary split up 12 hamburgers and 16 hot dogs among her sons Richard, Peter, Christopher, and James in such a way that James gets at least one hamburger and three hot dogs, and each of his brothers gets at least two hamburgers but at most
five hot dogs?

:::spoiler solution
For the hamburgers we need the coefficient of $x^{12}$ in
$\qquad (x+x^2 +...)( x^2 + x^3 +...)^3 = x(\dfrac{1}{1 - x})x^6(\dfrac{1}{1 - x})^3=x^7 (\dfrac{1}{1 - x})^4$.
It is the coefficient of $x^5$ in $(1-x)^{- 4}$, i.e.,
$\qquad \dbinom{-4}{5}(-1) ^ 5 = (-1)^5\dbinom{5+4-1}{5}(-1)^5=\dbinom{8}5{}.$
For the hot dogs we need the coefficient of $x ^ {16}$ in
$\qquad ( x ^ 3 + x ^ 4 +...)(1+x+x^2 +...+x^ 5 )^ 3 = x ^ 3 (\dfrac{1}{1 - x})(\dfrac{1 - x ^ 6}{1 - x}) ^ 3$.
It is the coefficient of $x ^ {13}$ in
$\qquad (1 - x ^ 6) ^ 3(1 - x) ^ {- 4} =[1- \dbinom{3}{1}x ^ 6 +\dbinom{3}{2}x ^{ 12} - x ^ {18} ][ \dbinom{- 4}{0}+\dbinom{- 4}{1}( - x)+...]$, i.e.,
$\qquad \dbinom{-4}{13}(- 1) ^ {13} - \dbinom{3}{1}\dbinom{- 4}{7}(- 1) ^ 7 + \dbinom{3}{2} \dbinom{- 4}{1}(- 1) = \dbinom{16}{13} - \dbinom{3}{1} \dbinom{10}{7} + \dbinom{3}{2}\dbinom{4}{1}$.
By the rule of product the total number of distributions for the prescribed conditions is
$\qquad \dbinom{8}{5}[\dbinom{16}{13}-\dbinom{3}{1} \dbinom{10}{7}+ \dbinom{3}{2}\dbinom{4}{1}]$
:::

### 15 ($\S 9.2\ \sharp\ 20$)
a) How many palindromes of $11$ start with $1$? with $2$? with $3$? with $4$?
b) How many palindromes of $12$ start with $1$? with $2$? with $3$? with $4$?

:::spoiler solution
${\bf (a)}$ If a palindrome of $11$ starts with $1$, then that palindrome ends in $1$. Upon removing '$1+$' from the start and '$+1$' from the end of the palindrome, we find a palindrome of $9$. And there are $2^{\lfloor{9/2}\rfloor}=2^4=16$ palindrome of $9$.
Similar arguments tells us that there are $2^{\lfloor{7/2}\rfloor}=8$ palindromes of $11$ that start with $2, 2^{\lfloor{5/2}\rfloor}=4$ palindromes of $11$ that start with $3$, and $2^{\lfloor{3/2}\rfloor}=2$ palindromes of $11$ that start with $4$.
${\bf (b)}$
For the palindromes of $12$, we find that $2^{\lfloor{10/2}\rfloor}=32$ start with $1, 2^{\lfloor{8/2}\rfloor}=16$ start with $2, 2^{\lfloor{6/2}\rfloor}=8$ start with $3$, and $2^{\lfloor{4/2}\rfloor}=4$ start with $4$.
:::

### 16 ($\S 9.2\ \sharp\ 23$)
Let $n ∈ \mathbb{Z}^+$ , $n$ even. How many palindromes of $n$ have an even number of summands? How many have an odd number of summands?

:::spoiler solution
Let $n=2k$ .The palindromes of n with an even number of summands have a plus sign at the center and their number is the number of compositions of $k$ - namely, $2^{k-1} = 2^{(n/2)-1}$ .Since there are $2^{n/2}$ palindromes in total, the number with an odd number of summands is $2^{n/2} - 2^{(n/2)-1} = 2^{n/2}(1- \dfrac{1}{2}) = 2^{n/2}(\dfrac{1}{2}) = 2^{(n/2)-1}$
:::

### 17 ($\S 9.2\ ex.\ 9.21$)
Find the generating function for the number of ways an advertising agent can purchase $n (\in \mathbb Z^+)$ minutes of air time if time slots for commercials come in blocks of 30, 60, or 120 seconds.
:::spoiler solution
Let 30 seconds represent one time unit. Then the answer is the number of integer solutions to the equation $a + 2b + 4c = 2n$ with $a, b, c\ge 0$. The associated generating function is
\begin{aligned}
f(x)&=(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^8+\cdots)(1+x^4+x^8+x^{12}+\cdots) \\
&=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^4}.
\end{aligned}
The coefficient of $x^{2n}$ is the number of partitions of $2n$ into 1’s, 2’s, and 4’s, the answer to the problem.
:::

### 18 ($\S 9.2\ extended\ reading$)

Please compare the non-negative integer solutions to equations using generating function:
(a) $a+b+c=3$;
(b) $a+2b+3c=3$;
\(c) $a+b+2c=3$;

### 19 ($\S 9.3\ \sharp\ 4$)
Find the generating function for the number of integer solutions of
(a) $2w + 3x + 5y + 7z = n, 0 ≤ w, x, y, z$
(b) $2w + 3x + 5y + 7z = n, 0 ≤ w, 4 ≤ x, y, 5 ≤ z$

:::spoiler solution
${\bf (a)}$
Consider the equation as the partitions of $n$ by summands of 2's, 3's, 5's and 7's. The generating polynomials are $(1+x^2+x^4+\cdots),\ (1+x^3+x^6+\cdots),\ (1+x^5+x^{10}+\cdots),\ (1+x^7+x^{14}+\cdots)$, or $\frac{1}{1-x^2},\ \frac{1}{1-x^3},\ \frac{1}{1-x^5},\ \frac{1}{1-x^7}$ respectively. The generating function becomes
$\qquad\qquad (\dfrac{1}{1-x^2})(\dfrac{1}{1-x^3})(\dfrac{1}{1-x^5})(\dfrac{1}{1-x^7})$
${\bf (b)}$
Consider the equation as the partitions of $n$ by summands of 2's, 3's, 5's and 7's with required constraints. The generating polynomials are
$(1+x^2+x^4+\cdots),\ (x^{12}+x^{15}+\cdots),\ (x^{20}+x^{25}+\cdots),\ (x^{35}+x^{40}+\cdots)$, or $\frac{1}{1-x^2},\ x^{12}(1+x^3+x^6+\cdots)=\frac{x^{12}}{1-x^3},\ x^{20}(1+x^5+x^{10}+\cdots)=\frac{x^{20}}{1-x^5},\ x^{35}(1+x^7+x^{14}+\cdots)=\frac{x^{35}}{1-x^7}$ respectively. The generating function is
$\qquad\qquad (\dfrac{1}{1-x^2})(\dfrac{x^{12}}{1-x^3})(\dfrac{x^{20}}{1-x^5})(\dfrac{x^{35}}{1-x^7})$.

:::

### 20 ($\S 9.2\ extended\ reading$)
Let $m, n\in \mathbb Z^+$, and define $p(m, n)$ to be the number of partitions of $m$ into exactly $n$ positive integers. Prove:
$\qquad\qquad p(m, n) = p(m-1, n-1) + p(m-n, n)$.
:::spoiler Proof
$p(m, n)$ can be represented as the number of positive integer solutions in

\begin{aligned}
m = s_1 + s_2 +\cdots+ s_n\quad\text{for }s_n\ge s_{n-1}\ge \cdots \ge s_2\ge s_1\ge 1.
\end{aligned}
There are two exclusive cases:
>(1) 1 is one of the summands:
$\qquad\qquad m = (m-1)+1 = s_1+s_2+\cdots+s_{n-1}+1,$
which corresponds to $p(m-1, n-1)$.

>(2) 1 is NOT one of the summands
\begin{aligned}
\qquad\qquad m &= s_1 + s_2 + \cdots + s_n (s1\ge 2) \\&= (t_1+1)+(t_2+1)+ \cdots +(t_n+1) \\
&= t_1+t_2+ \cdots +t_n+n \\
m-n &= t_1+t_2+ \cdots +t_n
\end{aligned}
which corresponds to $p(n, m-n)$.

Since Cases (1) and (2) are exhaustive and disjoint, we conclude
$\qquad\qquad p(m, n) = p(m-1, n-1) + p(m-n, n)$.
:::

---

---

## $Ordinary\ Generating\ Function$
:::info
Let $\{a_k\}_0^\infty = \{1_0, a_1, ... \}$ be a series. Function
\begin{aligned}
f(x) = a_0+a_1x+a_2x^2+a_3x^3+\ ...\ =\displaystyle\sum_{k=0}^{\infty}a_kx^k
\end{aligned}
is the $ordinary\ generating\ function$ of $\{a_k\}_0^\infty$.
:::
:::warning
#### $Ex.\ 1$ The generating function of $\{1\}_0^\infty$ is
\begin{aligned}
f(x) = 1+x+x^2+x^3+\ \cdots\ =\displaystyle\sum_{k=0}^{\infty}x^k=\dfrac{1}{1-x}
\end{aligned}
註：可視其為公比為 $x$ 的等比級數。
:::
This particular series $\{1\}_0^\infty$, i.e., $1, 1, 1, ...$ is really just a $geometric\ series$ with common ratio $x$. Let $S= 1 + x + x^2 + x^3 + \cdots$. Then we have
\begin{align*}
S & = 1 + x + x^2 + x^3 + \cdots\\
\underline{- x\ S} & \underline{\,\, = ~~~~~~ x + x^2 + x^3 + x^4 + \cdots}\\
(1-x)S &= 1 \\
S &= \dfrac{1}{1-x}. \\
\end{align*}
:::warning
#### $Ex.\ 2$ The generating function of $\{1\}_0^\infty$ is
\begin{aligned}
f(x) = 1+rx+r^2x^2+x^3+\ \cdots\ =\displaystyle\sum_{k=0}^{\infty}r^kx^k=\dfrac{1}{1-rx}
\end{aligned}
註：可視其為公比為 $rx$ 的等比級數。
:::
ex. For generating function
\begin{matrix}
\dfrac{x^2}{3+2x}&=\dfrac{x^2}{3+2x}=\dfrac{x^2}{3}(\dfrac{1}{1+\frac{2}{3}x})=\dfrac{x^2}{3}(\dfrac{1}{1-(-\frac{2}{3}x)}) \\
&=\dfrac{x^2}{3}(1+(-\dfrac{2}{3})x+(-\dfrac{2}{3})^2x^2+(-\dfrac{2}{3})^3x^3+\ ...) \\
&=\dfrac{1}{3}(x^2-\dfrac{2}{3}x^3+(-\dfrac{2}{3})^2x^2+-\dfrac{2}{3})^3x^3+\ ...\ ),
\end{matrix}
which generates series $0, 0, \dfrac{1}{3},\ \dfrac{1}{3}(-\dfrac{2}{3}),\ \dfrac{1}{3}(-\dfrac{2}{3})^2,\dfrac{1}{3}(-\dfrac{2}{3})^3,\ ...$
:::warning
#### $Ex.\ 3$ The generating function of $\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, ... , \binom{n}{n}$, for $n\gt 0$ is
\begin{aligned}
f(x) = \binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\ \cdots\ +\binom{n}{n}x^n\ =\displaystyle\sum_{k=0}^{\infty}\binom{n}{k}x^k=(1+x)^n
\end{aligned}
Note that the resultant $(1+x)^n$ is based on the Binomial theorem.
:::

:::warning
#### $Ex.\ 4$ Cosnider $a\in \mathbb{Z}$, $k\in \{0, 1, 2, ...\}$ and $\dbinom{a}{k}=\dfrac{a(a-1)(a-2)\cdots(a-k+1)}{k!}$ where $\dbinom{a}{0}=1$.
The generating function of $\binom{a}{0}, \binom{a}{1}, \binom{a}{2},\ \cdots\quad$ is
\begin{aligned}
f(x) = \binom{a}{0}+\binom{a}{1}x+\binom{a}{2}x^2+\ \cdots\ \ =\displaystyle\sum_{k=0}^{\infty}\binom{a}{k}x^k=(1+x)^a
\end{aligned}
:::
For $a\in \mathbb{Z}$, the $Maclaurin\ series$ expansion for $(1+x)^a$ is given by
\begin{align*}
(1+x)^a & = 1 + ax + \frac{a(a-1)x^2}{2!} + \frac{a(a-1)(a-2)}{3!}x^3 + \cdots\\
&= 1+ \sum_{k=1}^\infty\dfrac{a(a-1)(a-2)\cdots(a-k+1)}{k!}x^k\\
&= \sum_{k=0}^\infty\binom{a}{k}x^k. \\
\end{align*}

:::danger
It is a generalized form of Binomial theorm. We call it *generalized Binomial theorm*, i.e.,
$$(1+x)^a = \sum_{k=0}^\infty\binom{a}{k}x^k\ \text{for }a\in \mathbb{Z}\ (\mathbb{R})\text{ and }k\in \{0, 1, 2, ...\}.$$
:::
When $a\ (=n)\gt 0$, the above formula is exactly the Binomial theorem:
\begin{align*}
(1+x)^n & = \sum_{k=0}^\infty\binom{n}{k}x^k. \end{align*}
On the otherhand, suppose that $a=-n$ where $n\in \mathbb{N}$ (or equivalently, $a$ is negtive). We have
\begin{align*}
\dbinom{-n}{k} & = \dfrac{(-n)(-n-1)(-n-2)\cdots(-n-k+1)}{k!}\\
&= \dfrac{(-n)(-(n+1))(-(n+2))\cdots(-(n+k-1))}{k!} \\
&= \dfrac{(-1)^k(n)(n+1)(n+2)\cdots(n+k-1)}{k!}\\
&= \dfrac{(-1)^k\underline{(n-1)!}(n)(n+1)(n+2)\cdots(n+k-1)}{\underline{(n-1)!}k!}\\
&= \dfrac{(-1)^k(n+k-1)!}{{(n-1)!}k!} = \dfrac{(-1)^k(n+k-1)!}{((n+k-1)-k!)k!}\\
&= (-1)^k\binom{n+k-1}{k}.\\
\end{align*}
That is,
$$(1+x)^{-n} =\sum_{k=0}^\infty(-1)^k\binom{n+k-1}{k}x^k.$$

Note that
\begin{align*}
\dfrac{1}{(1-x)^n} & = (1+(-x))^{-n}
\\
&= \sum_{k=0}^\infty(-1)^k\binom{n+k-1}{k}(-x)^k \\
&= \sum_{k=0}^\infty\binom{n+k-1}{k}x^k. \\
\end{align*}
### 9.1 ($\S 9.2\ ex\ 9.11$) Combinations with repetition
In how many ways can we select, with repetitions allowed, $r$ objects from $n$ distinct objects?
:::spoiler solution
For each of the $n$ distinct objects, the geometric series$1+x+x^2+x^3+\cdots$ represents the possible choices for that object (namely none, one, two, ...). Considering all of the $n$ distinct objects, the generating function is
\begin{aligned}
f(x) = (1+x+x^2+x^3+ \cdots)^n =(\dfrac{1}{1-x})^n = \sum_{k=0}^\infty\binom{n+k-1}{k}x^k.
\end{aligned}
The required answer is the coefficient of $x^r$ in $f(x):\ \dbinom{n+k-1}{k}x^k$.
:::
### 9.2 ($\S 9.2\ ex\ 9.12$) Compositions
(a) Counting the $compositions$ of a positive integer $4$ using generating functions.
:::spoiler solution
4 可由 1, 2, 3, 4, ... 個成員(相加)組成而得，而每個成員可以是 1, 2, 3, 4, 5, ...。每個成員可能的數字 (1, 或 2, 或 3, ...；只能為其中之一)，可用生成函數：
$\qquad \qquad \qquad x+x^2+x^3+\cdots$
表示(不得有 $1$ 那一項！為何？)。
(1) 由 1 個成員相加為 4 : 選生成函數 $x+x^2+x^3+\cdots$ 中的 $x^4$，只有 1 種。
(2) 由 2 個成員相加為 4 : 選生成函數 $(x+x^2+x^3+\cdots)^2$ 中的 $xx^3$、$x^2x^2$、$x^3x$，有 3 種。
(3) 由 3 個成員相加出 4 : 選生成函數 $(x+x^2+x^3+\cdots)^3$ 中的 $xxx^2$、$xx^2x$、$x^2xx$，有 3 種。
(3) 由 3 個成員相加成 4 : 選生成函數 $(x+x^2+x^3+\cdots)^4$ 中的 $xxxx$，僅有 1 種。
利用 rule of sum 得知 $4$ 的組成總共有 $1+3+3+1=8$ 種。

:::
(b) General compositions:
Counting the $compositions$ of a positive integer $n$ using generating functions.
:::spoiler solution
The required answer is at the $x^n$ coefficient of generating function:
\begin{aligned}g(x) &= \displaystyle\sum_{k=1}^{\infty}(x+x^2+x^3+\cdots)^k \\
&=\displaystyle\sum_{k=1}^{\infty}(\frac{x}{1-x})^k \qquad \text{replace }\frac{x}{1-x} \text{by } y\\
&=\displaystyle\sum_{k=1}^{\infty}y^k = y\sum_{k=0}^{\infty}y^k = y(\frac{1}{1-y}) =(\frac{x}{1-x})[\frac{1}{1-(\frac{x}{1-x})}]=(\frac{x}{1-x})[\frac{1}{\frac{1-x-x}{1-x}}]\\
&=\frac{x}{1-2x} = x[1+(2x)+(2x)^2+(2x)^3+\cdots] \\
&=2^0x+2^1x^2+2^2x^3+2^3x^4+\cdots+2^{n-1}x^n+\cdots
\end{aligned}

Thus the number of compositions of a positive integer $n$ is the coefficient of $x^n$ in $g(x)$, which is $2^{n-1}$.
:::
### 9.3 ($\S 9.2\ ex\ 9.13$) Palindromes
(a) Counting the $palindromes$ of a positive integer $6$ and $7$ using generating functions.
:::spoiler
Based on the above figure, for 7 (6), there are $1 + (1 + 2 + 4) = 1 + (1 + 2^1 + 2^2) = 1 + (2^3−1) = 2^3$
palindromes.
$6\ (7)$ 逐次減 $0、2、4、6$，所減的值分配至左右兩端，左(右)端將所分得的數字取其任一組成，可得所屬迴文 (組成與迴文有 1 對 1 對應關係。本題中所減的 $0, 2, 4, 6$ 分配至左右兩端，左(右)端可得 $0(=\frac{0}{2}), 1(=\frac{2}{2}), 2(=\frac{4}{2}), 3(=\frac{6}{2})$ ，而其組成個數分別為 $1, 1, 2, 4$，因而迴文個數亦分別為 $1, 1, 2, 4$。
:::
(b) Counting the $palindromes$ of a positive integer $n$ using generating functions.
:::spoiler
既是迴文，必然左端與右端對稱。先考慮 $n$ 為偶數且 $n=2k$, $k\gt 0$，則 $n$ 可分別減 $0、2、4、6、\cdots、2k$，所減的值均分給左右兩端，任一端可分得 $1、1、2、3、\cdots、k$，而其組成恰為 $1、2^0、2^1、2^2、\cdots、2^{k-1}$；每一組成對應至一個迴文，於是總共迴文數為：
$\qquad\qquad1+2^0+2^1+2^2+\cdots+2^{k-1}=1+(2^k-1)=2^k=2^{\frac{n}{2}}.$
當 $n$ 為奇數且 $n=2k+1$, $k\gt 0$，則 $n$ 亦可分別減 $0、2、4、6、\cdots、2k$，所減的值均分給左右兩端，任一端可分得 $1、1、2、3、\cdots、k$，而其組成恰為 $1、2^0、2^1、2^2、\cdots、2^{k-1}$；每一組成對應至一個迴文，於是總共迴文數為：
$\qquad\qquad1+2^0+2^1+2^2+\cdots+2^{k-1}=1+(2^k-1)=2^k=2^{\lfloor\frac{n}{2}\rfloor}.$
總結：正整數 $n$ 的迴文個數為 $2^{\lfloor\frac{n}{2}\rfloor}$.
:::
### 9.4 ($\S 9.2\ ex\ 9.14$)
In how many ways can a police captain distribute 24 rifle shells to four police officers so that each officer gets at least three shells, but not more than eight?
:::spoiler
用 combinations with repetition 來解的話，可列式為：
$\qquad\qquad c_1+c_2+c_3+_4=24,\ 3 \le c_i \le 8\text{ for }1\le i\le 4.$
上式限制式多，不易求解。可考慮生成函數！
每位警員可得槍套個數的生成函數為：
$\qquad\qquad\qquad x^3+x^4+\cdots+x^8$
四位警員可得槍套個數的生成函數為
$\qquad\qquad f(x)=(x^3+x^4+\cdots+x^8)^4$
所求即為 $f(x)$ 中 $x^{24}$ 的係數：
\begin{aligned}
(x^3+x^4+\cdots+x^8)^4 = x^4x^3(1+x+\cdots+x^5) = x^{12}(\frac{1-x^6}{1-x})^4
\end{aligned}
由上可知所求即為 $(\frac{1-x^6}{1-x})^4$ 中 $x^{12}$ 的係數：
\begin{aligned}
(\frac{1-x^6}{1-x})^4 &= (1-x^6)^4(1-x)^{-4} \\
&= [\binom{4}{0}+\binom{4}{1}(-x^6)+\binom{4}{2}(-x^6)^2+\binom{4}{3}(-x^6)^3+\binom{4}{4}(-x^6)^4][\binom{-4}{0}+\binom{-4}{1}(-x)+\binom{-4}{2}(-x)^{2}+\binom{-4}{3}(-x)^{3}+\cdots] \\
&= [\binom{4}{0}-\binom{4}{1}x^6+\binom{4}{2}x^{12}-\binom{4}{3}x^{18}+\binom{4}{4}x^{24}][\binom{-4}{0}-\binom{-4}{1}x+\binom{-4}{2}x^{2}-\binom{-4}{3}x^{3}+\cdots] \\
\end{aligned}
其 $x^{12}$ 的係數為：
\begin{aligned}
&\qquad 1\binom{-4}{12}(-1)^{12}-\binom{4}{1}\binom{-4}{6}(-1)^{6}+\binom{4}{2}\binom{-4}{0}1 \\
&= \binom{15}{2}-\binom{4}{1}\binom{9}{6}+\binom{4}{2} = 125. \\
\end{aligned}
:::
### 9.5 ($\S 9.2\ ex\ 9.15$)
for all $n\in$

---

## 5.1 Cartesian Products and Relations 248

### Six closely related problems

### Definition 5.1 Cartesian product
For sets $A, B$ the Cartesian product, or cross product, of $A$ and $B$ is denoted by $A×B$ and equals $\{(a,\ b)|\ a\in A,\ b\in B\}$.

### Ordered Pairs
the elements of $A × B$ are ordered pairs
For $(a, b), (c, d)$ in $A×B$, we have $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$.
$A × B ≠ B × A$
$|A×B| = |A|×|B|$ (rule of product)
Cartesian product $A×B$ can be represented pictorially with the aid of a tree diagram

### Definition 5.2 Binary relation
For sets $A, B$, any subset of $A × B$ is called a $(binary)\ relation$ from $A$ to $B$. Any subset of $A × A$ is called a (binary) relation on $A$.

### Representations of a Relation
Set of ordered pairs
Directed bipartite graph
Relation $0/1$ (Boolean) matrix

:::danger
### Number of relations
For finite sets $A, B$ with $|A| = m$ and $|B| = n$, there are $2^{mn}$ relations from $A$ to $B$, including the empty relation as well as the relation $A × B$ itself.
:::
### Example Various relations
Subset: $R$ is the subset relation where $(C, D) ∈ R$ if and only if $C, D ⊆ B$ and $C ⊆ D$
Composition
Reverse
Complement
Intersection
Union
:::info

### Theorem 5.1
For any sets $A,B,C⊆ \mathcal{U}$:
$(a)\ A\times(B \cap C)=(A\times B) \cap (A\times C)$
$(b)\ A\times(B \cup C)=(A\times B) \cup (A\times C)$
$(c)\ (A \cap B)\times C=(A\times C) \cap (B\times C)$
$(d)\ (A \cup B)\times C=(A\times C) \cup (B\times C)$

:::
## 5.2 Functions: Plain and One-to-One 252

### Definition 5.3 Function / Mapping
For nonempty sets $A, B$, a *function*, or *mapping*, $f$ from $A$ to $B$, denoted $f : A → B$, is a relation from $A$ to $B$ in which every element of $A$ appears exactly once as the first component of an ordered pair in the relation.

#### Terminology
preimage
image
associating with: $f$ is a method for associating with each $a ∈ A$ the unique element $f (a) = b ∈ B$

### Definition 5.4 Domain, codomain, range
For the function $f : A→B$, $A$ is called the $domain$ of $f$ and $B$ the $codomain$ of $f$ . The subset of $B$ consisting of those elements that appear as second components in the ordered pairs of $f$ is called the $range$ of $f$ and is also denoted by $f(A)$ because it is the set of images (of the elements of $A$) under $f$.

### Example
Ceiling function
Floor function
Access function

:::danger
### Number of functions
For $|A| = m, |B| = n$, there are $n^m (|B|^{|A|})$ functions from $A$ to $B$.
:::
### Definition 5.5 1-1 (injective) function
A function $f : A→B$ is called **one-to-one**, or **injective**, if each element of $B$ appears at most once as the image of an element of $A$.

###
If $A, B$ are finite sets, for a one-to-one function $f : A→B \Rightarrow |A| ≤ |B| (m ≤ n)$
$f : A→B$ is one-to-one if and only if $∀a_1, a_2 ∈ A, f(a_1) = f(a_2) \Rightarrow a_1 = a_2$

:::danger
### Number of 1-1 functions
$n(n-1)(n-2)...(n-m+1) = n!/(n-m)! = P(n, m) = P(|B|, |A|)$
:::
### Definition 5.6 Image of a subset under $f$
If $f : A→B$ and $A_1$ belongs to $A$, then $f(A_1) = \{ b \in B\ |\ b = f(a),\text{ for some }a\text{ in }A_1\}$, and $f(A_1)$ is called the $image$ of $A_1$ under $f$.
:::info
### Theorem 5.2
Let $f:A\to B,$ with $A_1,A_2\subseteq A$.Then
$(a)f(A_1 \cup A_2)=f(A_1)\cup f(A_2)$
$(b)f(A_1 \cap A_2)\subseteq f(A_1)\cap f(A_2)$
$(c)f(A_1 \cap A_2)=f(A_1)\cap f(A_2)$ when $f$ is one-to-one.
:::
### Definition 5.7
$Restriction$ of $f$ to $A_1: f : A→B$ and $A_1 ⊆ A$, then $f|A1 : A1→B$

### Definition 5.8
Extension of $f$ to $A$: Let $A_1 ⊆ A$ and $f : A_1→B$. If $g: A→B$ and $g(a) = f(a)$ for all $a ∈ A_1$, then we call $g$ an $extension$ of $f$ to $A$

## 5.3 Onto Functions: Stirling Numbers of the Second Kind 260

### Definition 5.9 Onto (surjective) function
A function $f : A→B$ is called onto, or surjective, if $f (A) = B$ — that is, if for all $b$ in $B$, there is at least one a in $A$ with $f(a) = b$.

### Numbers of Onto Functions: The number of onto functions from $A$ to $B$ is equal to that of ways of distributing $m$ different objects to $n$ distinct containers with no container left empty
$|A| = m, |B| = n; m ≥ n$
$n = 2 ==> 2^m−2$
$n = 3 ==> C(3, 3)3^m−C(3, 2)2^m +C(3, 1)1^m$
...
for a general $n$ ==> $onto(A, B) = onto(m, n) = C(n, n)n^m−C(n, n-1)(n-1)^m + C(n, n-2)(n-2)^m− ... +(-1)(n-2)C(n, 2)2^m+ (-1)(n-1)C(n, 1)1^m$
$\sum_{k=0}^{n}(-1)^k\binom{n}{n-k}(n-k)^m$

### Example 5.24
### Example 5.25
### Example 5.26
If $A = \{a, b, c, d\}$ and $B = \{1, 2, 3\}$, then there are onto$(A, B) = 36$ onto functions from $A$ to $B$ or, equivalently, $36$ ways to distribute $4$ distinct objects into $3$ is tinguishable containers, with no container empty (and no regard for the location of objects in a given container).
Now if we no longer distinguish the containers, these $6 = 3!$ distributions become identical, so there are $36/(3!) =6$ ways to distribute the distinct objects $a, b, c, d$ among $3$ identical containers, leaving no container empty.

### Distributing $m$ distinct objects into $n$ numbered containers with no container left empty ==> onto$(A, B)$

### Distributing $m$ distinct objects into $n$ identical containers with no container left empty ==> Stirling number of the second kind $S(m, n)$

### Stirling number of the second kind: $S(m, n)$

### For $|A|=m ≥ n=|B|$, there are $n!×S(m, n)$ onto functions from $A$ to $B$.
:::info

### Theorem 5.3
Let $m, n$ be positive integers with $1 < n ≤ m$.
Then $S(m+1, n) = S(m, n−1) + nS(m, n).$

:::


## 5.4 Special Functions 267

### Definition 5.10 Binary operation, Closed
For any nonempty sets $A$ and $B$, any function $f: A×A→B$ is called a binary operation on $A$. If $B$ belongs to $A$, then the binary operation is said to be closed (on $A$). (When $B$ belongs to $A$ we may also say that $A$ is closed under $f$.)

### Definition 5.11 Unary (monary) operation

### Definition 5.12 Commutative and Associative operations
Let $f: A×A→B$; that is, $f$ is a binary operation on $A$.
$(a)\ f$ is said to be commutative if $f(a, b) = f(b, a)$ for all $(a, b)$ in $A×A$.
$(b)$ When $B$ belongs to $A$ (that is, when $f$ is closed), $f$ is said to be associative if for all $a, b, c$ in $A$, $f(f(a, b), c) =f(a, f(b, c))$.

### Example 5.33 Number of commutative closed binary operations $g$ on $A$

### Definition 5.13 Identity operation
Let $f: A×A→B$ be a binary operation on $A$. An element $x$ in $A$ is called an identity (or identity element) for $f$ if $f(a,x) = f(x, a) = a$ for all $a$ in $A$.
:::info

### Theorem 5.4
Let $f: A×A→B$ be a binary operation. If $f$ has an identity element $e$, $e$ is unique.

:::
### Definition 5.14 Projection

## 5.5 The Pigeonhole Principle 273

### The Pigeonhole Principle
If $m$ pigeons occupy $n$ pigeonholes and $m > n$, then at least one pigeonhole has two or more pigeons roosting in it.

## 5.6 Function Composition and Inverse Functions 278

### Additive inverse

### Multiplicative inverse

### Definition 5.15 One-to-one correspondence (bijective)
If $f: A×A→B$, then $f$ is said to be bijective, or to be a one-to-one correspondence, if $f$ is both one-to-one (injective) and onto (surjective).

### Definition 5.16 Identity function
The function $1_A: A→A$, defined by $1_A(a) = a$ for all $a$ in $A$, is called the identity function for $A$.

### Definition 5.17 Equal functions
If $f, g: A→B$, we say that $f$ and $g$ are equal and write $f = g$, if $f(a) = g(a)$ for all $a$ in $A$.

### Definition 5.18 Composite function
If $f: A→B$ and $g: B→C$, we define the composite function, which is denoted $g◦f : A→C$, by $(g◦f)(a) = g(f(a))$, for each $a$ in $A$.

### Theorem 5.5
Let $f: A→B$ and $g: B→C$.
$(a)$ If $f$ and $g$ are one-to-one, then $g◦f$ is one-to-one.
$(b)$ If $f$ and $g$ are onto, then $g◦f$ is onto.

### Theorem 5.6 Composition of functions is associative
If $f: A→B, g: B→C$ and $h: C→D$, then $(h◦g)◦f = h◦(g◦f )$.

### Definition 5.19
If $f: A→A$ we define $f^1 = f$, and for $n$ in $Z^+$ , $f^(n+1) =f◦(f^n)$.

### Definition 5.20 Converse relation
For sets $A, B$, if $R$ is a relation from $A$ to $B$, then the converse of $R$, denoted $R^c$ , is the relation from $B$ to $A$ defined by $R^c = \{(b, a)|(a, b) in R\}$.

### Definition 5.21 Invertible function
If $f: A→B$, then $f$ is said to be invertible if there is a function $g: B →A$ such that $g◦f = 1_A$ and $f◦g = 1_B$.

### Theorem 5.7 Uniqueness of invertible function
If a function $f: A→B$ is invertible and a function $g: B →A$ satisfies $g◦f = 1_A$ and $f◦g = 1_B$, then this function $g$ is unique.

:::info
### Theorem 5.8
A function $f: A→B$ is invertible if and only if it is one-to-one and onto.

:::

### Theorem 5.9
If $f: A→B, g: B→C$ are invertible functions, then $g◦f: A→C$ is invertible and $(g◦f)^{−1}= f^{−1}◦g^{−1}$.

### Definition 5.22 preimage
If $f: A→B$ and $B_1$ belongs to $B$, then $f^{−1}(B_1) = \{x \text{ in } A | f(x) \text{ in } B_1\}$. The set $f^{−1}(B_1)$ is called the preimage of $B_1$ under $f$ .

### Theorem 5.10
If $f: A→B$ and $B_1, B_2$ in $B$, then
$(a) f^{−1}(B_1∩B_2) = f^{−1}(B_1)∩f^{−1}(B_2)$;
$(b) f^{−1}(B_1∪B_2) = f^{−1}(B_1)∪f^{−1}(B_2)$; and
$(c) f^{−1}(\bar{B_1}) =\overline{ f^{−1} B_1}$

:::info
### Theorem 5.11
Let $f: A→B$ for finite sets $A$ and $B$, where $|A| = |B|$. Then the following statements are equivalent:
$(a)\ f$ is one-to-one;
$(b)\ f$ is onto; and
$(c)\ f$ is invertible.

:::

## 5.7 Computational Complexity 289

### Definition 5.23
Let $f, g: Z^+→R$. We say that $g$ dominates $f$ (or $f$ is dominated by $g$) if there exist constants $m$ in $R^+$ and $k$ in $Z^+$ such that $|f(n)| ≤ m|g(n)|$ for all $n$ in $Z^+$, where $n ≥ k$.

### Order, big-Oh
“$f$ in $O(g)$,” $O(g)$ represents the set of all functions with domain $Z^+$ and codomain $R$ that are dominated by $g$.

## 5.8 Analysis of Algorithms 294

### Order of magnitude
In general, the notation $f$ in $O(g)$ denotes that we do not know the function $f$ explicitly but do know an upper bound on its order of magnitude.

## 5.9 Summary and Historical Review 302

### Distinct or not {Objects, Containers}, Empty (Containers) or not