# 二階數學補充-排列組合與構造

## 小技巧
### H
- 重複組合$H^n_k$
- n種物品 數量都無限 取k個的組合
想像成k個物品要丟到n個不同箱子 箱子代表不同的種類
- 再想像箱子都排成一排 每個箱子間都有隔板 共n-1個隔板
- OOOOOO|OO|OOO||OOOO
表示有6個物品屬於第一種 2個物品屬於第二種 3個物品屬於第三種 0個物品屬於第四種 4個物品屬於第五種
- 上述例子即為n=5, k=15的一種組合
- $H^n_k=\cfrac{(k+(n-1))!}{k!(n-1)!}=C^{n+k-1}_{k}$

- 求$x+y+z=10$的非負整數解組數
- 延伸:正整數解?
- 再延伸:$\le10$的正整數解?

### 格子構造法與卡特蘭數
詳見EC2017

### 生成函數
- 求$x+2y+3z=10$的非負整數解組數
- 相當於求$(1+x+x^2+x^3+...)(1+x^2+x^4+...)(1+x^3+x^6+...)$的$x^{10}$係數
- $\rightarrow$

## 寫寫考古

### EC2112 (窮舉)
$(x_1, x_2,x_3, x_4, x_5, x_6)=(6,6,6,1,1,2)$或$(6,6,5,1,1,1)$的排列組合
$\rightarrow3+3=6$種組合

### EC2113 (插空型)

### EC2114 (窮舉)

### EC2017 (爬格子構造法)

### EE1706 (爬格子)

### CS1714 (?)

### CS1716 (窮舉)
$(285+288+289)/3$

### EE1602 (遞迴)

### CS1612 (文氏圖)

### CS1620 (因數分解)
$n+(n+1)+...+(n+k)=\cfrac{[n+(n+k)](k+1)}2=1050$
注意$2n+k$和$k+1$奇偶性不同
$2100=2^2\times3\times5^2\times7$
奇數因數共有$2\times3\times2=12$個

### EE1401 (賽程表)
(a)$15\times14\times13\times12+15\times14\times13+15\times14+15=35715$

(b)$0.8\times0.8\times0.8\times0.3\times\cfrac18=0.0192$

### EE1304 (窮舉)
二同一異+三異

$=10\times9+C^{10}_3=210$

### CS1301 (二項式)
$=(C^{15}_0+C^{15}_1+C^{15}_2+...+C^{15}_{15})-C^{15}_{15}$
$=2^{15}-1$

### CS1307 (H)

相當於求$x_1+x_2+...+x_n=d$的解$=C^{n-1+d}_d$

### CS1212 (二項式)

$=C^2_0+C^3_1+C^4_2+...+C^{20}_{18}$
$=C^3_0+C^3_1+C^4_2+...+C^{20}_{18}$
$=C^4_1+C^4_2+...+C^{20}_{18}$
$=C^{21}_{18}$

### CS1010 (窮舉)
1 8 8
2 7 8
3 6 8
3 7 7
4 5 8
4 6 7
5 5 7
5 6 6

### CS0910 (H)
$\rightarrow(x_1-1)+(x_2-1)+(x_3-1)+(x_4-1)+x_5=6$ (非負整數和組合)
$\rightarrow C^{10}_{6}=210$

### EE0703 ()
估算:
$C^5_2=10, 10/2=5$

構造:
12vs34
13vs45
14vs25
15vs23
24vs35

### CS0705 (二項分布)
構造一個$n=50, p=\cfrac25$的二項分布
則機率最大值出現在$k=[(n+1)p]=[(50+1)\cfrac25]=20$

### EE0604 (H)
==(a)==
$(a_1-1)+(a_2-1)+(a_3-1)+(a_4-1)+(a_5-1)+(a_6-1)=24$
解的組合有$C^{29}_5$個

==(b)==
假設$a_1<a_2<a_3<a_4<a_5<a_6$
$a_3+a_4=10$
$a_6-a_1=9$
必有$6$
$\rightarrow$==Case 1==假設$a_4=5$
則眾數必不為$6$

$\rightarrow$==Case 2==假設$a_4=6$
$a_1+a_2+4+6+6+a_1+9=30$
$(a_1,a_2)=(1,3)$
幾何平均數$=^6\sqrt{1\times3\times4\times6\times6\times10}$

### EE0504 ()
$7^4=2401$
$\cfrac{C^7_3}{7^4}=\cfrac5{7^3}$
$\cfrac{H^7_4}{7^4}=\cfrac{C^{10}_4}{7^4}=\cfrac{30}{7^3}$

### EE0509 (因數分解)
$12600=2\times7\times9\times100=2^3\times3^2\times5^2\times7$
$4\times3\times3\times2=72$

### EE0401 (生成函數?)

### EE0403 (最小公倍數)

## 更多考古

### EC2102

### EC2018

### EC2020

### EE1806

### CS1811

### CS1708

### CS1717

### EE1601
我還是看不懂這題題目

### CS1607

### EE1503

### EE1303

### EE1203

### CS1217

### CS1218

### CS1219

### CS1220

### CS1117

### EE1006

### EE0902

### EE0803

### EE0804

### EE0701

### EE0603

### CS0205

### CS0206

###### tags: `電資二階` `Cosmos`