---
# System prepended metadata

title: discrete 8-1 排容原理

---

# 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
![](https://i.imgur.com/XmcNaWz.png)








<!-- 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)




