---
tags: 數讀
---
# 計數模型
這份講義大概是在說計數以及簡單的組合對應
> [name=W_Ice_Tri] [time=Sun, March 7, 2021] [color=#1f1e33]

[TOC]
## 1. 課綱排組
### Definition (C)
$\displaystyle{C^n_k=\frac{n!}{k!(n-k)!}=\binom{n}{k}=C^k_n={}^nC_k}\ (n,k\in \mathbb{N}\cup\{0\})$
若$n<k$,顯然$\displaystyle{C^n_k=0}$

#### Example1.1
求ABC...Z這$26$個字母取四個全相異字母的方法數。

#### Example1.2
ABC...Z這$26$個字母可創造多少種四字母全相異的單字？

#### Example1.3
求滿足$a+b+c+d=26$的非負整數解數。

#### Example1.4
將ABC...Z分成五堆(非空)，試問有幾種分法？

#### Problem1.1
求ABCDEF的排列方法數，使得BD不相鄰、C在EF中間。

#### Example1.5
平面上兩點$A(0,0),B(5,7)$，每次移動只能走x軸或y軸的ㄧ個單位。求從$A$到$B$的最短路徑方法數。

#### Problem1.2
ㄅㄆ兩隊各出$5$名隊員按事先排好順序上場參加「本一家羅馬競技生死鬥」。雙方先由$1$號隊員比賽，勝者被膜拜，負者被淘汰，之後勝者再與負方$2$號隊員比賽，以此類推，直到有一方隊員全被淘汰為止，則另一方獲得勝利，此時比賽結束。試求可能出現的比賽過程的種數。

## 2. 圖解公式
### Formula2.1
$\displaystyle{\sum^n_{k=0}k=\frac{n(n+1)}{2}}$
### Formula2.2
$\displaystyle{\sum^n_{k=0}k^3=(\frac{n(n+1)}{2})^2=(\sum^n_{k=0}k)^2}$
### Formula2.3
$\displaystyle{\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}}$
### Formula2.4
$\displaystyle{(x+y)^n=\sum^{n}_{i=0} \binom{n}{i}x^{n-i}y^i}$
### Formula2.5
$\displaystyle{\sum^n_{k=0}\binom{n}{k}=2^n}$
## 3 水題啦
#### Example3.1
令$A:\{1,2,3,4\}$，試問有多少種$A_1,A_2,A_3$的取法，滿足$A_1,A_2,A_3\subset A,A_1\cap A_2\cap A_3=\phi$
#### Example3.2
試證：$\displaystyle{\sum^m_{k=0}\binom{n+k}{n}=\binom{n+m+1}{n+1}}$
#### Example3.3
試證：$\displaystyle{\sum^p_{k=0}\binom{n}{k}\binom{m}{p-k}=\binom{n+m}{p}}$
#### Example3.4
試證：$\displaystyle{\sum^n_{k=m}\binom{k}{m}\binom{m+n-k}{m}=\binom{m+n+1}{2m+1}}$
#### Problem3.1
試證：$\displaystyle{\sum_{r=0}^n r7^{n-r} \binom{n}{r} = n8^{n-1}}$
#### Problem3.2
試證$\forall n=2,3\cdots\ ,\ \displaystyle{4^n>\binom{2n}{n}\geq \frac{4^n}{n+1}}$皆成立
#### Problem3.3
試求：$\displaystyle{\sum^{12}_{k=1} \binom{12}{k} \cos{\frac{2k\pi}{3}}}$
#### Example3.5
試求：$\displaystyle{\sum^8_{k=0}\binom{16-k}{k}}$
## 4. 雙射
### Definition (bij.)
雙射=單射+滿射
#### Example4.1
試證：對於所有正整數n，分成數個奇數和的方法數等於分成數個相異正整數和的方法數
#### Example4.2
平面上兩點$A(0,0),B(7,5)$，每次移動只能走x軸或y軸的ㄧ個單位，若移動時的座標$(x,y)$滿足$x\geq y$。求從$A$到$B$的最短路徑方法數。
#### Problem4.1
試證$n+1$邊的樹$(Tree)$的形式有$\displaystyle{\frac{1}{n+1}\binom{2n}{n}}$種
## 5. 蛤
#### Example5.1
ㄅㄆㄇㄈㄉㄊ六人現要重排，求滿足ㄅㄆㄇㄈ皆不在原位的方法數。
#### Example5.2
ㄅㄆㄇㄈㄉㄊ六人現要重排，求滿足ㄅㄆㄇㄈ皆不在原位且ㄇㄈ不能互換的方法數。
#### Problem5.1
試證對於所有質數$p$與正整數$n$滿足$\displaystyle{p \mid \binom{n}{p}-\left\lfloor \frac{n}{p}\right\rfloor}$
#### Problem5.2
求和式$\displaystyle{\sum^{10}_{k=1}k^2\binom{{10}}{k}}$之值
#### Problem5.3
(廖郅暟電神)試證：$$\displaystyle{\sum^n_{k=1}\frac{(-1)^{k+1}\binom{n}{k}}{k} =1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}}$$
#### Problem5.4
(IMOC\ 2020\ C2)\ 因為疫情影響，台灣每天生產2020個一樣的口罩，政府決定將口罩分成若干堆，現在有2021個人排隊在搶口罩，而吳尚昱是第2021個人，因為人類是貪心的，每個人都會搶走目前剩下的口罩中最多的那堆，政府想要計算給定正整數$a,b$，有幾種分法使得前$a$個人都可以拿到至少$b$個口罩，將其記為$f(a,b)$。現在記者問了吳尚昱兩個問題。\\(1).\ 請問你有拿到口罩嗎？\\(2).\ 請問$f(a,b)=f(b,a)$嗎？\\但是因為吳尚昱詞窮，所以請幫他回答這兩個問題。
#### Problem5.5
試求：$\displaystyle{\sum^{671}_{k=0}\binom{2014}{3k+1}}$之末三位數字。
#### Problem5.6
(Putnam 2005 B4)For positive integers $m$ and $n$, let $f\left(m,n\right)$ denote the number of $n$-tuples $\left(x_1,x_2,\dots,x_n\right)$ of integers such that $\left|x_1\right| + \left|x_2\right| + \cdots + \left|x_n\right|\le m$. Show that $f\left(m,n\right) = f\left(n,m\right)$.
#### Problem5.7
(1974 P3) 試證：$$\displaystyle{5 \nmid \sum^n_{k=0}\binom{2n+1}{2k+1}2^{3k}} ,\ \forall n\in \mathbb{N}\cup \{0\}$$