組合數(shù)學(xué) 筆記

0001：從? $n$ ?個不同的元素中取? $r$ ?個可重復(fù)元素的組合數(shù)為： $\left(\begin{array}{c}n+r-1 \\r\end{array}\right)$

? ? ? ? ? ?方程? $x_1 + x_2 + \dots + x_n = r, n \in N, r \in Z^+$ 的非負整數(shù)解的個數(shù)為： $\left(\begin{array}{c}n+r-1 \\r\end{array}\right)$

0002：從 $n$ ?個不同的元素中取 $r$ ?個最多可出現(xiàn)? $k(1 \leq k \leq r)$ ?次元素的組合數(shù)為： $\left( \begin{array}{c} n+r-\lceil \frac{r}{k} \rceil \\r\end{array}\right)$

? ? ? ? ? ?~~拋擲? $n$ ?個骰子，點數(shù)之和為? $r, n \leq r \leq 6n$ ?的組合數(shù)為： $\left(\begin{array}{c} r-\lceil \frac{r-n}{5} \rceil \\ r-n \end{array}\right)$~~

0003：從? $n$ ?個不同的元素中取? $r$ ?個不相鄰元素的組合數(shù)為： $\left(\begin{array}{c}n-r+1 \\r\end{array}\right)$

0004：組合數(shù)公式： $\left(\begin{array}{c}n \\r\end{array}\right) = \left(\begin{array}{c}n - 1 \\ r \end{array}\right) +\left(\begin{array}{c}n - 1 \\ r - 1 \end{array}\right), n - 1 \geq r$ 袒炉，由此公式可推出：

$\left(\begin{array}{c}n + 1 \\ r \end{array}\right) = \left(\begin{array}{c}n \\ r \end{array}\right) +\left(\begin{array}{c}n - 1 \\ r - 1 \end{array}\right) + \dots +\left(\begin{array}{c}n - r + 1 \\ 1 \end{array}\right) +\left(\begin{array}{c}n - r \\ 0 \end{array}\right) = \sum_{i = 0}^{r} \left(\begin{array}{c}n - i \\ r - i \end{array}\right), n \geq r$

$\left(\begin{array}{c}n + 1 \\ r + 1 \end{array}\right) = \left(\begin{array}{c}n \\ r \end{array}\right) +\left(\begin{array}{c}n - 1 \\ r \end{array}\right) + \dots +\left(\begin{array}{c} r + 1 \\ r \end{array}\right) +\left(\begin{array}{c} r \\ r \end{array}\right) = \sum_{i = 0}^{n - r} \left(\begin{array}{c}n - i \\ r \end{array}\right), n \geq r + 1$

0005：組合數(shù)公式： $\left(\begin{array}{c}n \\ l \end{array}\right) \left(\begin{array}{c}l \\ r \end{array}\right) =\left(\begin{array}{c}n \\ r \end{array}\right) \left(\begin{array}{c}n - r \\ l - r \end{array}\right), n \geq l \geq r$

0006：組合數(shù)公式：

$\left(\begin{array}{c}m + n \\ r \end{array}\right) =\left(\begin{array}{c}m \\ 0 \end{array}\right) \left(\begin{array}{c}n \\ r \end{array}\right) +\left(\begin{array}{c}m \\ 1 \end{array}\right) \left(\begin{array}{c}n \\ r - 1 \end{array}\right) +\dots +\left(\begin{array}{c}m \\ r \end{array}\right) \left(\begin{array}{c}n \\ 0 \end{array}\right) =\sum_{i=0}^r\left(\begin{array}{c}m \\ i \end{array}\right) \left(\begin{array}{c}n \\ r - i \end{array}\right), r \leq min \{ m, n\}$

由此公式可推出：

$\left(\begin{array}{c}m + n \\ m \end{array}\right) =\left(\begin{array}{c}m \\ 0 \end{array}\right) \left(\begin{array}{c}n \\ 0 \end{array}\right) +\left(\begin{array}{c}m \\ 1 \end{array}\right) \left(\begin{array}{c}n \\ 1 \end{array}\right) +\dots +\left(\begin{array}{c}m \\ m \end{array}\right) \left(\begin{array}{c}n \\ m \end{array}\right) =\sum_{i=0}^m\left(\begin{array}{c}m \\ i \end{array}\right) \left(\begin{array}{c}n \\ i \end{array}\right), n \geq m$

$\left(\begin{array}{c}2n \\ n \end{array}\right) =\left(\begin{array}{c}n \\ 0 \end{array}\right) ^2+\left(\begin{array}{c}n \\ 1 \end{array}\right)^2 +\dots +\left(\begin{array}{c}n \\ n \end{array}\right) ^2 =\sum_{i=0}^n\left(\begin{array}{c}n \\ i \end{array}\right)^2$

0007： $x, y$ ?坐標(biāo)系中從? $(0, 0)$ ?點沿兩個坐標(biāo)軸方向移動到? $(m, n)$ ?點的最短路徑中（其中? $m < n$ ）寂祥，經(jīng)過的點的坐標(biāo)始終滿足? $x < y$ ?的路徑數(shù)量為：

$\frac{(m + n - 1)!}{m! n!} (n - m)$

此結(jié)論可解決下面的問題：

電影院的票價為50元纲酗， $n$ ?個人持50元好港， $m (m \leq n)$ ?個人持100元影所，每人只買一張票赠制，相互之間不拆借，售票處開始營業(yè)時沒有錢经柴。能使售票順利進行狸窘，不出現(xiàn)找不出錢的排隊方式數(shù)量為：

$\frac{(m + n)!}{m! (n+1)!} (n + 1 - m)$

順利售票的概率為： $1 - \frac{m}{n+1}$

最小概率為： $\frac{1}{n+1}$

0008：階乘公式：

$\sum_{i=1}^{n} i \cdot i! = \sum_{i=1}^{n} (i+1-1) \cdot i! = \sum_{i=1}^{n} [(i+1)! - i!] = (n+1)! - 1$

$(2n)! = (2n)!!(2n-1)!! = 2^nn!(2n-1)!!$

0009：組合數(shù)函數(shù)? $f(r) = \left(\begin{array}{c}n \\r\end{array}\right), n \geq r \geq 1$ ，先遞增后遞減坯认。函數(shù)在? $\frac{n-1}{2}, \frac{n+1}{2} \ (n為奇數(shù))$ ?或? $\frac{n}{2} \ (n為偶數(shù))$ ?處取得最大值翻擒。

0010：分堆排列組合數(shù)： $n$ ?個有區(qū)別的小球放入? $m$ ?個盒子里，每個盒子里放入? $k_i, i =1,2, \dots ,m$ ?個小球牛哺，其中? $\sum_{i=1}^m k_i = n$ 陋气，則：

若盒子是有標(biāo)志的，則分堆方案數(shù)為： $\frac{n!}{ \prod_{i=1}^m k_i! }$ 引润，且有：

$\sum_{k_1 + k_2 + \dots + k_m = n} \frac{n!}{ \prod_{i=1}^m k_i! } = m^n$ （每個小球放入時有 $m$ ?個選擇）

若盒子是無標(biāo)志的恩伺，則分堆方案數(shù)為： $\frac{n!}{ m! \prod_{i=1}^m k_i! }$

0011：證明： $n^2, n \in N$ ?的正因數(shù)的個數(shù)是奇數(shù)；

方法一：

根據(jù)算術(shù)基本定理椰拒，必存在質(zhì)數(shù)? $P_1,P_2,\dots,P_m$ ?和非負整數(shù) $a_1,a_2,\dots,a_m$ ，使：

$n = \prod_{i=1}^m P_m^{a_m}, \ \ \ N = n^2 = \prod_{i=1}^m P_m^{2a_m}$

可以看出? $N$ ?可以分解為? $m$ ?個質(zhì)因數(shù)冪的乘積凰荚，故? $N$ ?的因數(shù)個數(shù)為：

$\prod_{i=1}^m (2a_m+1)$ 燃观，這是一個奇數(shù)，證畢便瑟。

方法二：

設(shè)? $a, 1 \leq a < n$ 缆毁，是? $n^2$ ?的一個正因數(shù)，則存在自然數(shù)? $b, n < b \leq n^2$ 到涂，滿足? $n^2 = a * b$ 脊框。

可以看出? $a, b$ ?成對出現(xiàn)，這樣的正因數(shù)有偶數(shù)個践啄。

$n$ ?也是 $n^2$ ?的一個正因數(shù)浇雹，所以所有正因數(shù)的總個數(shù)是奇數(shù)。

證畢屿讽。

0012：證明：

? $0*0! + 1*1!+2*2!+\dots+(n-1)*(n-1)! = \sum_{j=0}^{n-1} (j*j!) = n!-1,n \ge 1$

使用母函數(shù)的證明方法：

設(shè)? $a_n = \sum_{j=0}^{n-1} (j*j!)$ 昭灵，則有遞推關(guān)系：

? $a_n - a_{n-1} = (n-1)*(n-1)!, n \ge 2, a_1 = 0$ ；

設(shè)? $b_n = \frac{a_n}{n!}$ ，可得遞推關(guān)系：

? $nb_n - b_{n-1} = n-1, n \ge 2, b_1 = 0$ 烂完；

設(shè)? $b_n$ ?的母函數(shù)為： $G(x) = b_1x+b_2x^2+\dots+b_nx^n+\dots$

根據(jù) $b_n$ ?的遞推關(guān)系可得：

? $\frac{dG(x)}{dx} - G(x) = x(1-x)^{-2},G(0) = 0$

解微分方程可得： $G(x) = (1-x)^{-1} - e^x$

故试疙， $b_n = 1-\frac{1}{n!}$ ， $a_n = b_n*n! = n! - 1$

證畢抠蚣。

0013：證明：所有的正整數(shù)? $n$ ?都可以表示為（下標(biāo)）不同的 Fibonacci 數(shù)之和祝旷。

使用數(shù)學(xué)歸納法證明， $n = 1$ ?時命題顯然成立嘶窄，假設(shè)? $n = k$ ?時命題成立怀跛，即：

存在自然數(shù)? $1 \leq l_1 < l_2 < \dots <l_m$ ，滿足： $k = \sum_{j=1}^m F_{l_j}$ 护侮，則：

$k+1 = F_1 + F_{l_1} + F_{l_2} + \dots + + F_{l_m}$ 敌完，分析如下：

若? $l_1 > 1$ ，則命題成立羊初；若? $l_1 = 1$ 滨溉，則? $l_2 \geq 2$ ，且：

$k+1 = F_1 + F_2 + F_{l_2} + F_{l_3} + \dots + + F_{l_m}$

若? $l_2 > 2$ 长赞，則命題成立晦攒；若? $l_2 = 2$ ，則? $l_3 \geq 3$ 得哆，且：

$k+1 = F_3 + F_2 + F_{l_3} + F_{l_4} + \dots + + F_{l_m}$

若? $l_3 > 3$ 脯颜，則命題成立；若? $l_3 = 3$ 贩据，則? $l_4 \geq 4$ 栋操，且：

? $k+1 = F_4 + F_3 + F_{l_4} + F_{l_5} + \dots + + F_{l_m}$

以此類推，將這樣的分析進行下去饱亮，直到：

$k+1 = F_{m} + F_{m-1} + F_{l_m}$ 矾芙，其中， $l_m \geq m$ 近上，則：

若? $l_m > m$ 剔宪，則命題成立；若? $l_m = m$ 壹无，則有：

$k+1 = F_{m + 1} + F_{m}$ 葱绒，此時命題成立。

由上可得斗锭，當(dāng)? $n = k + 1$ ?時命題也成立地淀。

證畢。

0014：設(shè)? $F_n$ ?是斐波那契數(shù)列岖是， $a,b,c$ ?是正整數(shù)骚秦，證明：

$F_{a+b+c+3} = F_{a+2} ( F_{b+2} F_{c+1} + F_{b+1} F_c) + F_{a+1} ( F_{b+1} F_{c+1} + F_b F_c )$

解：利用遞推關(guān)系? $F_n = F_{n-1} + F_{n-2}$ ?可化簡等式的右邊為：

? $F_{a+2} ( F_{b+2} F_{c+1} + F_{b+1} F_c) + F_{a+1} ( F_{b+1} F_{c+1} + F_b F_c )$

? $= F_{a+2} F_{b+2} F_{c+2} + F_{a+1} F_{b+1} F_{c+1} - F_a F_b F_c$

將通項公式? $F_n = \frac{\alpha^n - \beta^n}{\sqrt{5}}, \alpha = \frac{1 + \sqrt{5}}{2}, \beta = \frac{1 - \sqrt{5}}{2}$ ?代入上式她倘，并利用關(guān)系式

? $\alpha + \beta = 1, \alpha \beta = -1, 1 + \alpha^2 \beta = \beta, 1 + \alpha \beta^2 = \alpha$ ?可得：

? $F_{a+2} F_{b+2} F_{c+2} + F_{a+1} F_{b+1} F_{c+1} - F_a F_b F_c$

? $= \frac{1}{5 \sqrt{5}} ( \alpha^{a+b+c+6} + \alpha^{a+b+c+3} - \alpha^{a+b+c} - \beta^{a+b+c+6} - \beta^{a+b+c+3} + \beta^{a+b+c})$

? $= \frac{1}{5} ( F_{a+b+c+6} + F_{a+b+c+3} - F_{a+b+c} )$

? $= F_{a+b+c+3}$

證畢。

0015：將整數(shù)序列? $\{1,2,\dots,2^8\}$ ?任意剖分為? $P$ ?和? $Q$ ?兩部分作箍，證明這兩部分中的一個必包含三個構(gòu)成等比關(guān)系的數(shù)硬梁。

解：使用反證法。假設(shè)? $P$ ?和? $Q$ ?中都不包含能夠構(gòu)成等比關(guān)系的數(shù)胞得，則? $1,2^4,2^8$ ?這3個數(shù)必不能屬于同一部分荧止，下面分別討論之。

1. 若? $1, 2^4 \in P$ 阶剑，則? $2^8 \in Q$ 跃巡，則有：

? $\implies 2^2,2^8 \in Q$

? $\implies 1, 2^4,2^5 \in P$

? $\implies 2^2,2^3,2^6,2^8 \in Q$

? $\implies 1,2, 2^4,2^5,2^7 \in P$

? $\implies 矛盾$

2. 若? $2^4,2^8 \in P$ ，則? $1 \in Q$ 牧愁，則有：

? $\implies 1, 2^6 \in Q$

? $\implies 2^3,2^4,2^8 \in P$

? $\implies 1, 2^2,2^5,2^6 \in Q$

? $\implies 2,2^3,2^4,2^7,2^8 \in P$

? $\implies 矛盾$

3. 若? $2^4 \in P$ 素邪，則? $1, 2^8 \in Q$ ，這分兩種情況來討論猪半。

3.1 若? $2^4,2^6 \in P$ 兔朦， $1, 2^8 \in Q$ ，則有：

? $\implies 1,2^2,2^5, 2^8 \in Q$

? $\implies 矛盾$

3.2 若? $2^4 \in P$ 磨确， $1,2^6, 2^8 \in Q$ 沽甥，則有：

? $\implies 2^3,2^4,2^7 \in P$

? $\implies 1,2^2,2^5,2^6, 2^8 \in Q$

? $\implies 矛盾$

綜上，在所有情況下均推出了矛盾乏奥，所以假設(shè)不正確摆舟，命題得證。

0016：證明循環(huán)群的子群也是循環(huán)群邓了。

證明：設(shè)? $G$ ?是循環(huán)群恨诱， $x$ ?是? $G$ ?的生成元， $H$ ?是? $G$ ?的子群骗炉。

則有? $\forall p \in H, \exists i \in N, x^i = p$ 照宝，設(shè)? $S = \{i | x^i \in H \}, k = S_{min}$

下面證明? $H$ ?的所有元素都是? $x^k$ ?的整數(shù)冪。

假設(shè)? $\exists m, r \in N, r < k, x^{mk+r} \in H$ ,

則有： $x^{-mk}x^{mk+r} = x^r \in H$ ，即? $r \in S$ ?且? $r < k$

這與? $k = S_{min}$ ?相矛盾，所以? $x^k$ ?是? $H$ ?的一個生成元凿渊，故? $H$ ?也是循環(huán)群带到，命題得證。

0017：證明有限群中元素的階能夠整除群的階旨别。

證明：設(shè)? $G$ ?為有限群诗赌， $x$ ?是? $G$ ?中的任意一個元素， $r = |x|, g = |G|$ 秸弛。

易證? $H = \{ x^1, x^2, \dots,x^r = e \}$ ?是? $G$ ?的一個子群铭若，若任意子群的階都能夠整除群的階洪碳，則問題就得以證明，下面對此事實進行證明叼屠。

設(shè)? $H$ ?是? $G$ ?的任意子群瞳腌， $x, y$ ?是? $G$ ?的任意兩個元素。

若? $x \notin H$ 镜雨，則? $xH \cap H = \oslash$

證明：假設(shè)? $xH \cap H \neq \oslash$ 嫂侍，則? $\exists a, b \in H, xa = b, x = ba^{-1}\in H$ ，這與 $x \notin H$ ?矛盾

? $\forall x \in G, |xH| = |H|$

證明：假設(shè)? $|xH| < |H|$ 荚坞，則? $\exists a, b \in H, xa = xb, a = b$ 挑宠，這與? $a \neq b$ ?矛盾

$\forall x,y \in G, xH \cap yH = \oslash，或颓影，xH = yH$

證明：若? $xH \cap yH = \oslash$ 各淀，則命題成立。

若? $xH \cap yH \neq \oslash$ 诡挂，則? $\exists a, b \in H, xa = yb, x = yba^{-1}, y = xab^{-1}$

? $\forall p \in H, xp = yba^{-1}p \in yH, xH \subset yH$

? $\forall p \in H, yp = xab^{-1}p \in xH, yH \subset xH$

故碎浇， $xH = yH$

設(shè)? $|H| = h$ , $x_1, \dots, x_{g-h} \in G - H , I = x_1H + \dots + x_{g - h}H$ ，則 $I = G - H$

證明：

? $\forall x \in G - H, xH \cap H = \oslash, xH \subset G - H, I \subset G - H$

? $\forall x \in G - H, \exists p \in H, y \in G - H, xp = y, x = yp^{-1} \in I, G - H \subset I$

故咆畏， $I = G - H$

綜上南捂，可得? $G = H + I = I = H + x_1H + \dots + x_{g - h}H$

設(shè)? $A_1 = H + x_1H$ ，則? $|A_1| = 2h$

設(shè)? $A_2 = H + x_1H + X_2H$ 旧找，則? $|A_2| = 2h, or, 3h$

依次類推溺健，可得 $|G| = |A_{g-d}| = n|H|,n >= 1$

即? $G$ ?的階是? $H$ ?的整數(shù)倍，由此可以得出以下結(jié)論：

1. 有限群的任意子群的階能夠整除群的階钮蛛；

2. 有限群的任意元素的階能夠整除群的階鞭缭；

命題證明完畢。

占位符

最后編輯于：2020.03.14 17:37:46

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末魏颓，一起剝皮案震驚了整個濱河市岭辣，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌甸饱，老刑警劉巖沦童，帶你破解...
沈念sama閱讀 218,682評論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異叹话，居然都是意外死亡偷遗，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,277評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門驼壶，熙熙樓的掌柜王于貴愁眉苦臉地迎上來氏豌，“玉大人，你說我怎么就攤上這事热凹”么” “怎么了泪电？”我有些...
開封第一講書人閱讀 165,083評論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長纪铺。經(jīng)常有香客問我相速，道長，這世上最難降的妖魔是什么霹陡？我笑而不...
開封第一講書人閱讀 58,763評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任和蚪，我火速辦了婚禮，結(jié)果婚禮上烹棉，老公的妹妹穿的比我還像新娘攒霹。我一直安慰自己，他們只是感情好浆洗，可當(dāng)我...
茶點故事閱讀 67,785評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布催束。她就那樣靜靜地躺著，像睡著了一般伏社。火紅的嫁衣襯著肌膚如雪抠刺。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,624評論 1贊 305
城市分裂傳說
那天摘昌，我揣著相機與錄音速妖，去河邊找鬼。笑死聪黎，一個胖子當(dāng)著我的面吹牛罕容，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播稿饰，決...
沈念sama閱讀 40,358評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼锦秒，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了喉镰？” 一聲冷哼從身側(cè)響起旅择，我...
開封第一講書人閱讀 39,261評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎侣姆，沒想到半個月后生真，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,722評論 1贊 315
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡捺宗，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,900評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年柱蟀，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片偿凭。...
茶點故事閱讀 40,030評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡产弹，死狀恐怖派歌，靈堂內(nèi)的尸體忽然破棺而出弯囊，到底是詐尸還是另有隱情痰哨，我是刑警寧澤，帶...
沈念sama閱讀 35,737評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布匾嘱，位于F島的核電站斤斧，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏霎烙。R本人自食惡果不足惜撬讽，卻給世界環(huán)境...
茶點故事閱讀 41,360評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望悬垃。院中可真熱鬧游昼，春花似錦、人聲如沸尝蠕。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,941評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽看彼。三九已至廊佩，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間靖榕，已是汗流浹背标锄。一陣腳步聲響...
開封第一講書人閱讀 33,057評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留茁计，地道東北人料皇。一個月前我還...
沈念sama閱讀 48,237評論 3贊 371
代替公主和親
正文我出身青樓，卻偏偏與公主長得像簸淀，于是被迫代替她去往敵國和親瓶蝴。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,976評論 2贊 355

組合數(shù)學(xué) 筆記

推薦閱讀更多精彩內(nèi)容