# discrete 8-1 排容原理

$S_0=𝑁$
$S_1=[𝑁(𝑐_1 )+𝑁(𝑐_2 )+𝑁(𝑐_3 )+…+𝑁(𝑐_𝑡 )]$
$S_2=[𝑁(𝑐_1 𝑐_2 )+𝑁(𝑐_1 𝑐_3 )+…+𝑁(𝑐_1 𝑐_𝑡 )+𝑁(𝑐_2 𝑐_3 )+𝑁(𝑐_2 𝑐_4 )+…+𝑁(𝑐_{(𝑡−1)} 𝑐_𝑡 )]$
## $\varphi$

# discete 8-2

<!-- $s(m,n) = \frac{1}{n!}\sum\limits_{x = 0}^n{(-1)^iC^{n}_{i}(n-i)^m}$ -->

$E_m = S_m -C^{m+1}_1S_{m+1}+C^{m+2}_2S_{m+2}-...+(-1)^{t-m}C^t_{t-m}S_t$
$E_2=S_2-C^3_1S_3+C^4_2S_4$

$L_m=S_m-C^m_{m-1}S_{m+1}+C^{m+1}_{m-1}S_{m+2}-...+(-1)^{t-m}C^{t-1}_{m-1}S_t$
$L_2 = S_2-C^2_1S_3+C^3_1S_4$

E means exactly
L means at least

<!-- For example, In (a)how many ways can one distribute ten distinct prizes among four students with exactly two students getting nothing?
Transform to exactly two students getting prizes?

$S_0=4^{10}$全部禮物分配情況
$S_1=C^4_12^{10}-1$有分給某一人的情況，有分給
$S_2 = C^4_2(2^{10}-2)$
<!-- $S_3 = C^4_33^{10}-3$ -->
<!-- $2^{10}-2$指十個禮物分給兩個人減掉十個都被一人獨拿的情況。 -->

<!-- $E_2=S_2$ -->
<!--
(b)How many ways have at least two students getting nothing?
convert to at exactly two students and exactly one student getting prizes ? -->
<!-- $E_2+E1=S_2+S_1-C^2_1S$ --> -->

# discrete8-3 Derangement
就是類似n個人交換禮物，不要拿到自己的，有幾種分配方法，先例如10人，要得到所有人都沒拿到自己的，所以是排容原理，然後乘10!有十個不同的人

| 情況\號碼 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|:---------------------:|:---:| --- | --- | --- | --- | --- | --- | --- | --- |:---:|
| 1個人拿到人拿到重覆的 | 1X | 3 | 7 | 8 | 9 | 10 | 4 | 6 | 2 | 5 |
| 2個人拿到人拿到重覆的 | 1X | 2X | 7 | 8 | 9 | 10 | 4 | 6 | 3 | 5 |

$d_{10}$=$N(\bar c_1\bar c_2...\bar c_{10})=$$10!-C^{10}_19!+C^9_28!...C^{10}_{10}0!$
又 $e^{-1}=\sum^\limits\infty_{n=0}\frac{(-1)^n}{n!}=1-1+\frac{1}{2!}-\frac{1}{3!}....$
$d_{10}$=$N(\bar c_1\bar c_2...\bar c_{10})=$$10!-C^{10}_19!+C^9_28!...C^{10}_{10}0!$
=$10!(1-1+\frac{1}{2!}-\frac{1}{3!}....)\doteq 10!*e^{-1}$
又因為每個人不一樣，所以範例題目是
$10!*10!*e^{-1}$
如果題目改成有10個格子，裡面放10個不一樣的東西，然後再拿出來重新分配，但是不能跟第一輪放一樣的東西，因為格子都一樣，這樣就$10!*e^{-1}$就好
## refference
[Discrete Math II - 8.6.4 Apply the Principle of Inclusion Exclusion: Derangements](https://www.youtube.com/watch?v=u44Y5FDeTRM)