## 離散數學 Q&A [sjshyu@DiscreteMath ]
#### p.10 EXAMPLE 1.15
If $n$ and $k$ are positive integers with
$n=2^k$, then $n!/2^k$ is an integer.

若 $n = 3k$，則 $\displaystyle\frac{n!}{3^k}$ 必為整數，其中 $k$ 為正整數。
証明：考慮 $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!$ 皆為整數。

### More on circular permutation
https://www.stat.nuk.edu.tw/prost/content_new/c2-4.htm

#### p.101 Ex.2.25
[先考慮數字較小的例子如下]
**設 $Q$ 為從 0到4 這5個數字任選4個相異數字的集合。
證明 $Q$ 中必存在兩個不同的子集合 $H$ 與 $S$ ，使得
$\sum_{x\in H}x\ =\ \sum_{x\in S}x$ ；其中 $\sum_{x\in \varnothing }x = 0$。**
$Proof:$ [利用鴿籠原理]
首先觀察：$H$ 與 $S$ 為 $Q$ 的不同子集合，因而 $H\neq Q$ 且 $S\neq Q$ (子集合$H$和$S$皆有可能等於 $Q$，但若如此$H=S$不合題意)；亦即 $H\subset Q$ 且 $S\subset Q$；或解讀為 $|H|\leq3$ 且 $|S|\leq3$ (注意：$|Q| = 4$)。
再來觀察 $Q$ 真子集合 ($H$或$S$) 元素總和的最大和最小值：
當$Q$選到的4個相異數字為 {1, 2, 3, 4} 時，$H$或$S$元素總和最大者為 9 (=2+3+4；亦即 $H\ ($或$S$)={2, 3, 4})。
當$Q$選到的4個相異數字為 {0, 1, 2, 3} 時，$H$或$S$元素總和最小者為 0 ($H\ ($或$S)=\varnothing$)。
於是得知：$H$或$S$的可能元素總和所構成的集合為 {0, 1, 2, ... , 9}；各和數字可視其為一個鴿籠，共10個。
而 $H$或$S$ ($Q$的真子集合)的可能個數為 $2^4-1$ = 15 (不含$Q$)；各真子集合可視為鴿子，共15隻(比鴿籠數目多)。
由鴿籠原理可知：$Q$ 中必存在兩個不同的子集合 $H$ 與 $S$ ，兩者有相同的元素總和。

[回到課本的範例]
**$U = \{0, 1, 2, ... , 22\}$，而 $Q\subset U$ 且 $|Q|=7$。証明 $Q$ 中必存在兩個不同的子集合 $H$ 與 $S$ ，兩者有相同的元素總和。**
$Proof:$ $Q$ 的真子集合個數為 $2^7-1=127$；視其為鴿子總數。
由於$H\neq S$ ($S$為$Q$中不同的子集合)，$H\neq Q$ 且 $S\neq Q$，亦即 $|H|\le 6$ 且 $|S|\le 6$。於是當 $H$ 或 $S$ 為 {17, 18, 19, 20, 21, 22} 時，其元素總和為最大；當 $H$ 或 $S$ 為 $\varnothing$，其元素總和為最小；也就是 $0 \le \sum_{x\in H}x\ ($ 或 $\sum_{x\in S}x) \le 117$；視其為鴿籠總數。
由鴿籠原理可知：$Q$ 中必存在兩個不同的子集合 $H$ 與 $S$ ，兩者有相同的元素總和。

(注意：此題若以$|H|$ = 7 來解 $H$ = {16, 17, 18, 19, 20, 21, 22} 時有最大元素總和，則會出錯(鴿籠總數為134>127 鴿子總數 )！想清楚：$|H|$ = 7 是不對的；$H\subset Q$，$|H|\le 6$。)

## Compositions
### (a) By combinations with repetition & Binomial thm.
#### EXAMPLE 1.37 Number of compositions of 7
| # of summands | x | restriction | # of ways |
| :--: | :--: |:--: |:--: |
| 1 | $x_1 = 7$ or $w_1 = 6$ | $x_1 \ge 1$ or$w_1 \ge 0$ | $\dbinom{6+1-1}{6}=\dbinom{6}{6}=1$ |
| 2 | $x_1+x_2 = 7$ or $w_1+w_2 = 5$|$x_1, x_2 \ge 1$ or $w_1,w_2 \ge 0$ | $\dbinom{5+2-1}{5}=\dbinom{6}{5}$ |
| 3 | $x_1+x_2+x_3 = 7$ or $w_1+w_2+w_3 = 4$|$x_1, x_2, x_3 \ge 1$ or $w_1,w_2,w_3 \ge 0$ | $\dbinom{4+3-1}{4}=\dbinom{6}{4}$ |
| ... | | |
| 7 | $x_1+x_2+...+x_7 = 7$ or $w_1+w_2+w_3...+w_7 = 0$|$x_1, x_2, ..., x_7 \ge 1$ or $w_1,w_2,...,w_7 \ge 0$ | $\dbinom{0+7-1}{0}=\dbinom{6}{0}$ |

### (b) By powersets of $\{1, 2, ... , n-1\}$

### \(c\) By PMI
#### EXAMPLE 4.12 $S(n):\ n$ has $2^{n-1}$ compositions.

### (d) By generating functions
#### EXAMPLE 9.12 Number of compositions of 4
| # of summands | generating function | coefficient of $x^4$ | summand (constitution) |
| :--: | :--: |:--: |:--: |
| 1 | $x+x^2+x^3+x^4+... = \dfrac{x}{1-x}$ | 1 | 4 $(x^4)$ |
| 2 | $(x+x^2+x^3+x^4+...)^2 = (\dfrac{x}{1-x})^2$ |$3$ | $1+3, 2+2, 3+1\ (x^1x^3, x^2x^2, x^3x^1)$ |
| 3 | $(x+x^2+x^3+x^4+...)^3 = (\dfrac{x}{1-x})^3$ | $3$ | $1+1+2, 1+2+1, 2+1+1\ (x^1x^1x^2, x^1x^2x^1, x^2x^1x^1)$ |
| 4 | $(x+x^2+x^3+x^4+...)^4 = (\dfrac{x}{1-x})^4$ |$1$ | $1\ (x^1x^1x^1x^1)$ |

The answer lies at the coefficient of $x^4$ in
$$\displaystyle\sum_{i=1}^{4}(\dfrac{x}{1-x})^4=1+3+3+1=8.$$
In general, the number of compositions of $n$ is the coefficient of $x^n$ in the generating function:
$$f(x)=\displaystyle\sum_{i=1}^{\infty}(\dfrac{x}{1-x})^i.$$
Let $y=\frac{x}{1-x}$, we obtain
$$f(x)=\displaystyle\sum_{i=1}^{\infty}(\dfrac{x}{1-x})^i=\displaystyle\sum_{i=1}^{\infty}y^i=y\displaystyle\sum_{i=0}^{\infty}y^i=y(\frac{1}{1-y})\\ =(\frac{x}{1-x})[\frac{1}{1-(\frac{1}{1-x})}]=(\frac{x}{1-x})[\frac{1}{\frac{1-x-1}{1-x}}]\\=\frac{x}{1-2x}=x[1+(2x)+(2x)^2+(2x^3)+...]\\=2^0x+2^1x^2+2^2x^3+2^3x^4+... =\displaystyle\sum_{i=1}^{\infty}2^{i-1}x^i.$$
The coefficient of $x^n$ is $2^{n-1}$, which is exactly the number of combinations of $n$.

### Compositions vs. Partitions
#### GF of Compositions focuses on number of summands
Regarding compositions, 1+2, 2+1 are different. Each summand maybe any of 1, 2, 3, ... , and any two summands are independent.
1-summand (maybe one of 1, 2, 3, ...): $x+x^2+x^3+x^4+... = \dfrac{x}{1-x}$
2-summand (maybe two of 1, 2, 3, ...): $(x+x^2+x^3+x^4+...)^2 = (\dfrac{x}{1-x})^2$
$k$-summand (maybe $k$ of 1, 2, 3, ...): $(x+x^2+x^3+x^4+...)^k = (\dfrac{x}{1-x})^k$

#### Partitions focus on the numbers of 1's, 2's, ... in each summand

Since 1+2 and 2+1 are irrelevant in partitions, the idea that "any two summands are independent" in compositions is invalid. We should address the numbers of 1's, 2's, ... instead. For instance, 3, 1+2 (and 2+1), and 1+1+1 involve one 3, one 1 as well as one 2 and three 1's. For a number $n$, the number of 1’s we can use is 0 or 1 or 2 or ... . The power series $1+x+x^2+x^3+...$ keeps account of this for us. Likewise, $1+x^2+x^4+ x^6+...$ keeps track of the number of 2’s in the partition of $n$ (when we take $k$ 2's as $k$ of the summands, these 2's contributes $2\times k$ to the partition of $n$), while $1+x^3+x^6+x^9+...$
accounts for the number of 3’s. The generating function of the number of partitions of $n$, denoted as $p(n)$, becomes
$$f(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+ x^6+...)(1+x^3+x^6+x^9+...)\\= \dfrac{1}{1-x}\dfrac{1}{1-x^2}\dfrac{1}{1-x^3}...=\prod_{i=1}^{\infty}(\frac{1}{1-x^i}),$$

which generates sequence $p(0),\ p(1),\ p(2),\ ...$.

---
#### 9.4/9. If a 20-digit ternary (0, 1, 2) sequence is randomly generated, what is the probability that:
(a) It has an even number of 1’s?
(b) It has an even number of 1’s and an even number of 2’s?
\(c\) It has an odd number of 0’s?
(d) The total number of 0’s and 1’s is odd?
(e) The total number of 0’s and 1’s is even?

(Sol.)
Using exponential generating functions:
(a)
even number of 1’s: $1+\frac{x^2}{2!}+\frac{x^4}{4!}+\ ... = \frac{e^x+e^{-x}}{2}$
no restriction of 0’s (2's): $1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\ ... = {e^x}$
Thus, the generating function for such a sequence is:
$$g_a(x) = (\frac{e^x+e^{-x}}{2})(e^x)^2 = \frac{1}{2}(e^{3x}+e^x) =\frac{1}{2}(\displaystyle\sum_{i=0}^{\infty}\frac{(3x)^i}{i!}+\displaystyle\sum_{i=0}^{\infty}\frac{(x)^i}{i!}).$$
The number of sequences lies at the coefficient of $\frac{x^{20}}{20!}$, which (replacing $i$ as 20 and ignoring $\frac{x}{20!}$) is
$$\frac{1}{2}(3^{20}+1^{20}) = \frac{1}{2}(3^{20}+1).$$
The probability becomes: $\displaystyle\frac{\frac{1}{2}(3^{20}+1)}{3^{20}}$
(b)
$$g_b(x) = (\frac{e^x+e^{-x}}{2})^2(e^x) = \frac{1}{4}(e^{2x}+2+e^{-2x})e^x=\frac{1}{4}(e^{3x}+2e^x+e^{-x}) \\ =\frac{1}{4}(\displaystyle\sum_{i=0}^{\infty}\frac{(3x)^i}{i!}+2\displaystyle\sum_{i=0}^{\infty}\frac{(x)^i}{i!}+\displaystyle\sum_{i=0}^{\infty}\frac{(-x)^i}{i!}).$$
The number of sequences lies at the coefficient of $\frac{x^{20}}{20!}$, which (replacing $i$ as 20 and ignoring $\frac{x}{20!}$) is
$$\frac{1}{2}(3^{20}+2(1)^{20}+(-1)^{20})=\frac{1}{2}(3^{20}+2+1)=\frac{1}{2}(3^{20}+3).$$
The probability becomes: $\displaystyle\frac{\frac{1}{2}(3^{20}+3)}{3^{20}}$
\(c\)
odd number of 0’s (1's or 2's): $x+\frac{x^3}{3!}+\frac{x^5}{5!}+\ ... = \frac{e^x-e^{-x}}{2}$
$$g_c(x) = (\frac{e^x-e^{-x}}{2})(e^x)^2 = \frac{1}{2}(e^{3x}-e^x) =\frac{1}{2}(\displaystyle\sum_{i=0}^{\infty}\frac{(3x)^i}{i!}-\displaystyle\sum_{i=0}^{\infty}\frac{(x)^i}{i!}).$$
The number of sequences lies at the coefficient of $\frac{x^{20}}{20!}$, which (replacing $i$ as 20 and ignoring $\frac{x}{20!}$) is
$$\frac{1}{2}(3^{20}-1^{20}) = \frac{1}{2}(3^{20}-1).$$
The probability becomes: $\displaystyle\frac{\frac{1}{2}(3^{20}-1)}{3^{20}}$
(d)
When the number of 0's is even, that of 1's must be odd. On the other hand, when the former is odd, the latter must be even.
$$g_d(x) = (\frac{e^x+e^{-x}}{2})(\frac{e^x-e^{-x}}{2})(e^x)+(\frac{e^x+e^{-x}}{2})(\frac{e^x-e^{-x}}{2})(e^x) \\ = \frac{1}{4}e^x(e^{2x}-e^{-2x}+e^{2x}-e^{-2x}) = \frac{1}{2}e^x(e^{2x}-e^{-2x}) \\= \frac{1}{2}(e^{3x}-e^{-x}) = \frac{1}{2}(\displaystyle\sum_{i=0}^{\infty}\frac{(3x)^i}{i!}-\displaystyle\sum_{i=0}^{\infty}\frac{(-x)^i}{i!}).$$
The number of sequences lies at the coefficient of $\frac{x^{20}}{20!}$, which (replacing $i$ as 20 and ignoring $\frac{x}{20!}$) is
$$\frac{1}{2}(3^{20}-(-1)^{20}) = \frac{1}{2}(3^{20}-1).$$
The probability becomes: $\displaystyle\frac{\frac{1}{2}(3^{20}-1)}{3^{20}}$
(e)
When the number of 0's is even, that of 1's must be even. On the other hand, when the former is odd, the latter must be odd, too.
$$g_e(x) = (\frac{e^x+e^{-x}}{2})^2(e^x)+(\frac{e^x-e^{-x}}{2})^2(e^x) \\ = \frac{1}{4}e^x(e^{2x}+2+e^{-2x}+e^{2x}-2+e^{-2x}) = \frac{1}{2}e^x(e^{2x}+e^{-2x}) \\= \frac{1}{2}(e^{3x}+e^{-x}) \frac{1}{2} =(\displaystyle\sum_{i=0}^{\infty}\frac{(3x)^i}{i!}+\displaystyle\sum_{i=0}^{\infty}\frac{(-x)^i}{i!}).$$
The number of sequences lies at the coefficient of $\frac{x^{20}}{20!}$, which (replacing $i$ as 20 and ignoring $\frac{x}{20!}$) is
$$\frac{1}{2}(3^{20}+(-1)^{20}) = \frac{1}{2}(3^{20}+1).$$
The probability becomes: $\displaystyle\frac{\frac{1}{2}(3^{20}+1)}{3^{20}}$

---
Another reasoning via combinations:
(a)
The number of 1's may be 0, 2, 4, ... , 20. Suppose that it is $i, 0\le i\le 20$. The number of such sequences is $\binom{20}{i}2^{20-i}$ (choosing $i$ positions among the 20 to place 1's, while the other $20-i$ positions to place 0 or 2). Thus the totol nu,ber of sequences becomes
$$\displaystyle\sum_{i=0,\ \text{even}}^{20}\binom{20}{i}2^{20-i} = \binom{20}{0}2^{20}+\binom{20}{2}2^{18}+\binom{20}{4}2^{16}+...+\binom{20}{20}2^{0}.$$
By binomial theorem, we know that
$$(1+2)^{20}=\binom{20}{0}1^02^{20}+\binom{20}{1}1^12^{19}+\binom{20}{2}1^22^{18}+...+\binom{20}{20}1^{20}2^{0}\ \text{and}\\ \binom{20}{0}1^02^{20}+\binom{20}{2}1^22^{18}+...+\binom{20}{20}1^{20}2^{0} = \binom{20}{1}1^12^{19}+\binom{20}{3}1^32^{17}+...+\binom{20}{19}1^{19}2^{0}.$$
Therefore,
$$\binom{20}{0}2^{20}+\binom{20}{2}2^{18}+\binom{20}{4}2^{16}+...+\binom{20}{20}2^{0}=\frac{1}{2}(1+2)^{20}=\frac{1}{2}3^{20}$$