3  場合の数

組み合わせと順列

Exercise 3.1 写像の個数

集合 \(A = \{1, 2, 3, \cdots, r\}, B = \{1, 2, 3, \cdots, n\}, n\geq r\) を考える． このとき以下の条件を満たす写像 \(f: A\to B\) はそれぞれ全部でいくつあるか？

1. 任意の写像
2. １対１写像(＝単射)
3. 広義単調増加写像
4. 狭義単調増加写像

Solution

▶  (1) 任意の写像

Aの各元について，Bの元の個数分の割当先が考えられるので \(n^r\) 個

▶  (2) １対１写像(＝単射)

単射の定義として

\[ (\forall i, j \in A) [i\neq j\Rightarrow f(i)\neq f(j)] \]

Bからr個の要素を順番に取り出す順列と対応することがわかる．従って，

\[ \text{単射の個数} = \frac{n!}{(n-r)!} \]

▶  (3) 広義単調増加写像

n個のツボにr個の区別できないボールを空ツボを許容して割り当てる問題と同一視できるので

\[ \text{広義単調増加写像の個数} = {}_nH_r = \frac{n+r-1!}{r!(n-1)!} \]

▶  (4) 狭義単調増加写像

n個元からr個選ぶ組み合わせの問題と同一視できるので

\[ \text{狭義単調増加写像の個数} = {}_nC_r = \frac{n!}{r!(n-r)!} \]

Exercise 3.2

\[ x + y + z = 6 \]

を満たす非負の整数の組 \((x, y, z)\) は何組あるか？

Solution

6つのボールを区別できる３つのツボにアサインする問題と同一視できるので

\[ {}_3H_6 = 28\text{通り} \]

Exercise 3.3

\[ {}_{n}P_r = {}_{n-1}P_r + r \cdot {}_{n-1}P_{r-1} \]

を示せ

Solution

\[ \begin{align*} \text{RHS} &= \frac{(n-1!)}{(n-1-r)!} + r \frac{(n-1!)}{(n-r)!} \\ &= (n-1)! \bigg(\frac{1}{(n-1-r)!} + \frac{r}{(n-r)!}\bigg)\\ &= (n-1)! \frac{n + r - r}{(n-r)!}\\ &= \frac{n!}{(n-r)!} = \text{LHS} \end{align*} \]

Exercise 3.4

0から9を１回ずつ用いて一直線に並べる場合の数を求めよ．ただし，左右をひっくり返したものは同じと考える．

Solution

0から9を１回ずつ用いて一直線に並べる場合の数は \(10!\)．ここから左右ひっくり返したものを除かなくてはならないが， すべての要素が異なる順列に対しての反転なので，その数はちょうど半分となる．従って，\(10!/2\)

Exercise 3.5

赤玉５個，白玉４個を一直線に並べる場合の数を求めよ．ただし，左右をひっくり返したものは同じと考える．

Solution

一直線に並べる場合の数は

\[ \frac{9!}{5!}{4!} \]

この内，左右対称となるもの(=ひっくり返したら同じになる並び順が存在しない組)は次の条件を満たすもの

• 中央が赤玉
• 左右の枠４個ずつについて，赤白がそれぞれ２個ずつ使用されている

つまり，\({}_{4}C_2 = 6\) 通りが完全左右対称の並びとなる．従って，

\[ \frac{126 - 6}{2} + 6 = 66\text{通り} \]

Exercise 3.6

ある野球チームの9人の選手の打順を決める．投手と二塁手は，７番，８番，９番のどれかにするとしたとき，９人の打順の決め方は何通りあるか？

Solution

• 投手と２塁手以外の順番は \(7!\)
• 投手と二塁手の順番の表し方は \(2!\)
• 投手と二塁手が専有する打順の組み合わせは \({}_3C_2 = 3!/2!\)

従って，

\[ 7! \times 2! \times \frac{3!}{2!} = 7! \times 3! = 5040 \times 6 = 30240 \]

Exercise 3.7

4つのサイコロの出る目のくみあわせを求めよ． 例: \((4, 1, 1, 1)\) という組と \((1, 4, 1, 1)\) 組は出ている目の組み合わせが同じなので 同一の組とみなす．

Solution - 組み合わせ

• 4つすべて同じ目の場合: \(6\text{通り}\)
• 3つが同じ目の場合: \({}_6C_2 \times 2 = 30\text{通り}\)
• 2つ, 2つが同じ目の場合: \({}_6C_2 = 15\text{通り}\)
• 2つが同じ目，残り２つ異なる目の場合: \({}_6C_3 \times 3 = 60\text{通り}\)
• すべてが異なる場合: \({}_6C_4 = 15\text{通り}\)

従って，\(126\text{通り}\)

Solution - 重複組み合わせ

サイコロの枠 1, 2, 3, 4, 5, 6に対して区別されない４つのボールを重複を許してアサインする問題と考えることができるので

\[ {}_6H_4 = {}_{9}C_4 = 126\text{通り} \]

Exercise 3.8

サイコロを \(n\) 回なげるとき，その結果である標本点を \((x_1, x_2, \cdots, x_n)\) であらわす． この標本の個数を求めよ．

Solution

重複を許して \(\{1, 2, 3, 4, 5, 6\}\) からn個選んで順列を作る問題とみなせるので \(2^n\text{通り}\)

Exercise 3.9

サイコロを \(n\) 回なげるとき，\(i \in \{1, 2, 3, 4, 5, 6\}\) の目が \(r_i\) 回出たとする．各面の出る確率が \(p_i\) で表されるときの 確率関数 \(P( \mathbf{r})\) を求めよ．ただし，

\[ \begin{align*} \sum_{i=1}^6 p_i &= 1\\ \sum_{i=1}^6 r_i &= n \end{align*} \]

Solution

\[ P( \mathbf{r}) = \frac{n!}{r_1!r_2!r_3!r_4!r_5!r_6!}p_1^{r_1}p_2^{r_2}p_3^{r_3}p_4^{r_4}p_5^{r_5}p_6^{r_6} \]

Exercise 3.10

10円硬貨６枚，100円硬貨４枚，500円硬貨２枚から全部，または一部（どれも使わないはなし）を使って支払える金額は何通りあるか？

Solution

\[ 7\times 5 \times 3 - 1 = 104 \]

Exercise 3.11 支払金額の数と多項式

10円硬貨６枚，100円硬貨６枚，500円硬貨２枚から全部，または一部（どれも使わないはなし）を使って支払える金額は何通りあるか？

Solution

この問題は

\[ \begin{align*} f(x)\equiv &(1 + x^{10} + x^{20} + x^{30} + x^{40} + x^{50} + x^{60})\\ &\times (1 + x^{100} + x^{200} + x^{300} + x^{400} + x^{500} + x^{600})\\ &\times (1 + x^{500} + x^{1000}) \end{align*} \]

と式をおいたときに，\(x\)の項の数と置き換えて考えることができます．従って，

\[ \begin{align*} f(x) =& (1 + x^{10} + x^{20} + x^{30} + x^{40} + x^{50} + x^{60})\\ &\times (1 + x^{100} + x^{200} + x^{300} + x^{400} + 2x^{500} + 2x^{600}\\ & + x^{700} + x^{800} + x^{900} + 2x^{1000} + 2x^{1100} + x^{1200} + x^{1300} + x^{1400} + x^{1500} + x^{1600}) \end{align*} \]

従って，\(7 \times 15 - 1 = 84\text{通り}\)

▶  Rでの検算

x <- c(10, 100, 500)
y <- list(
    coin1 = seq(0, 4),
    coin2 = seq(0, 6),
    coin3 = seq(0, 2)
)

# Perform a product join using expand.grid()
product_join_result <- expand.grid(y)

# Convert the data frame to an array
product_join_array <- as.matrix(product_join_result)

# Get the matrix product
res <- product_join_array %*% x
length(unique(res))

[1] 85

Exercise 3.12

AABCCDEという７文字をすべて用いて並べるとき，以下の場合の数を求めよ

1. 異なる順列の総数
2. AAという並び方と，CCという並び方を，ともに含む順列の総数
3. ACまたはCAという並び方を少なくとも１つ含む順列の総数

Solution

▶  1. 異なる順列の総数

\[ \frac{7!}{2!2!} = 1260\text{通り} \]

▶  2. AAという並び方と，CCという並び方を，ともに含む順列の総数

\[ 5! = 120\text{通り} \]

▶  3. ACまたはCAという並び方を少なくとも１つ含む順列の総数

まずAABDEという文字列の並び方の総数は

\[ \frac{5!}{2!} = 60\text{通り} \]

このうち，以下の場合分けができる

• A同士が隣り合う場合 → Cが入れる枠は ○BAAD○E○ の○の位置数なので３通り
• A同士が隣り合わない場合 → Cが入れる枠は ABAD○E○ の○の位置数なので2通り

\[ \begin{align*} \text{A同士が隣り合う場合の数} &= 4! = 24\\ \text{A同士が隣り合わない場合の数} &= 60 - 24 = 36 \end{align*} \]

更に，○の位置へのCの割り当て方は区別できないボールを区別できるツボへ空を許容して割り当てる問題と同一視できるので

\[ \begin{align*} \text{A同士が隣り合う場合のCの組み合わせ} &= {}_3H_2 = 6\\ \text{A同士が隣り合わない場合のCの組み合わせ} &= {}_2H_2 = 3 \end{align*} \]

従って，AとCが隣り合わない場合の数は

\[ 6 \times 24 + 3 \times 36 = 252 \]

「ACまたはCAという並び方を少なくとも１つ含む順列の総数」は全事象から「AとCが隣り合わない場合の数」を引けば良いので

\[ 1260 - 252 = 1008\text{通り} \]

二項係数

Exercise 3.13

\[ \bigg(x^3 - \frac{3}{x}\bigg)^6 \]

の \(x^2\) の係数を求めよ

Solution

\(x^2\) の係数は

\[ \begin{align*} \frac{6!}{p!q!} (-3)^q\ \ \text{s.t. }& 3p - q = 2\\ & p + q = 6\\ & p \geq 0, q \geq 0 \end{align*} \]

上記の制約を満たす \((p, q) = (2, 4)\) なので

\[ \frac{6!}{2!4!}(-3)^4 = 15 \times 81 = 1215 \]

Exercise 3.14 パスカルの三角形

以下の等式を証明せよ

\[ {}_nC_r = {}_{n-1}C_{r} + {}_{n-1}C_{r-1} \]

Solution

\[ \begin{align*} {}_{n-1}C_{r} + {}_{n-1}C_{r-1} &= \frac{(n-1)!}{r!(n-1-r)!} + \frac{(n-1)!}{(r-1)!(n-r)!}\\ &= \frac{(n-1)!}{r!(n-r)!}((n-r) - r)\\ &= \frac{n!}{r!(n-r)!} = {}_nC_r \end{align*} \]

📘 REMARKS

• パスカルの三角形で「上の2つの数字の和が下と等しい」という性質を表している
• 組み合わせの文脈では，n 個のものから r 個のものを選ぶ組み合わせの集合は，Aを除いたn-1個からr個選ぶ集合 + Aを用いて残りのn-1個から r-1個選ぶ集合の和集合と等しい

Exercise 3.15

以下の等式を証明せよ

\[ \begin{align*} &\sum_{i=0}^n {}_nC_i = 2^n \tag{a}\\ &\sum_{i=0}^n (-1)^i{}_nC_i = 0 \tag{b} \end{align*} \]

Solution

▶  (a)

\[ \begin{align*} (1 + 1)^n = \sum_{i=0}^n {}_nC_i = 2^n \end{align*} \]

▶  (b)

\[ (1 - 1)^n = \sum_{i=0}^n (-1)^i{}_nC_i = 0 \]

Exercise 3.16

以下の等式を証明せよ

\[ {}_nC_1 + 2 {}_nC_2 + \cdots + r {}_nC_r + \cdots + n{}_nC_n = 2^{n-1}n \]

Solution

\[ \begin{align*} 2^{n-1}n &= (1 + 1)^{n-1}n\\ &= n\sum_{i=0}^{n-1}{}_{n-1}C_i\\ &=\sum_{i=0}^{n-1}\frac{n!}{i!(n-1-i)!}\\ &=\sum_{i=0}^{n-1}\frac{n!}{i!(n-i)!}(n-i)\\ &= \sum_{i=0}^{n}\frac{n!}{i!(n-i)!}(n-i)\\ &= \sum_{j=0}^{n}\frac{n!}{j!(n-j)!}j\\ &= {}_nC_1 + 2 {}_nC_2 + \cdots + r {}_nC_r + \cdots + n{}_nC_n \end{align*} \]

Solution - 微分を用いた別解

\((1 + x)^n\) を \(x\) について微分して以下のような式を得ます

\[ \begin{align*} n(1 + x)^{n-1} = \sum_{i=1}^n {}_nC_{i} i x^{i-1} \end{align*} \]

この式に対して \(x=0\) を代入すると

\[ 2^{n-1} n = \sum_{i=1}^n {}_nC_{i} i \]

Exercise 3.17

以下の等式を証明せよ

\[ {}_nC_0 + \frac{1}{2} {}_nC_1 + \cdots + \frac{1}{r+1} {}_nC_r + \cdots + \frac{1}{n+1}{}_nC_n = \frac{2^{n+1}-1}{n+1} \]

Solution

\[ \begin{align*} \frac{2^{n+1}-1}{n+1} &= \frac{(1 + 1)^{n+1} - 1}{n + 1}\\ &= \frac{1}{n+1}\sum_{i=0}^{n+1}\frac{(n+1)!}{i!(n+1-i)!} - \frac{1}{n+1}\\ &= \sum_{i=0}^{n}\frac{n!}{i!(n+1-i)!} + \frac{1}{n+1} - \frac{1}{n+1}\\ &= \sum_{i=0}^{n}\frac{n!}{i!(n-i)!}\frac{1}{n-i + 1}\\ &= \sum_{j=0}^n \frac{n!}{j!(n-j)!}\frac{1}{j + 1} \end{align*} \]

Solution - 積分を用いた別解

厳密さは欠くが \((1 + x)^n\) を積分すると

\[ \frac{1}{n+1}(1 + x)^{n+1} + C = \sum_{r=0}^n \frac{1}{r+1}x^{r+1} + \frac{1}{n+1} + C \]

を得るので，ここに \(x=1\) を代入すると

\[ \frac{2^{n+1} - 1}{n+1} = {}_nC_0 + \frac{1}{2} {}_nC_1 + \cdots + \frac{1}{r+1} {}_nC_r + \cdots + \frac{1}{n+1}{}_nC_n \]

Exercise 3.18

\(k\leq \min(n,m)\) としたとき，次の等式を証明せよ

\[ \sum_{i=0}^k {}_mC_i \cdot {}_nC_{k-i} = {}_{m+n}C_{k} \]

Solution

\[ (1+x)^{m+n} = (1 + x)^m(1 + x)^n \]

の両辺について，それぞれ \(x^k\) の係数 \(p_k\) を計算すると，まずLHSベースだと

\[ p_k = {}_{m+n}C_{k} \]

RHSベースで計算すると

\[ p_k = \sum_{i=0}^k {}_mC_i \cdot {}_nC_{k-i} \]

従って，

\[ \sum_{i=0}^k {}_mC_i \cdot {}_nC_{k-i} = {}_{m+n}C_{k} \]

Exercise 3.19

フェアなコインを２人が独立にｎ回ずつ投げるとき，表が同じ回数ずつ出る確率をもとめよ

Solution

プレーヤー \(i\in \{1, 2\}\) が \(n\) 回トライして表を出す回数を \(X_i\) とすると，独立性より

\[ \Pr(X_1 = k, X_2 = k) = \Pr(X_1 = k)\Pr(X_2 = k) \]

\[ \begin{align*} &\Pr(X_i = k) = {}_nC_k \bigg(\frac{1}{2}\bigg)^n\\ &\Rightarrow \Pr(X_1 = k, X_2 = k) = {}_nC_k {}_nC_k \bigg(\frac{1}{2}\bigg)^{2n} \end{align*} \]

表が同じ回数ずつ出る確率を求めたいので, \(\Pr(\text{n回トライしたとき表が同じ回数ずつ出る}) = p_n\) とすると

\[ \begin{align*} p_n &= \sum_{k=0}^n {}_nC_k {}_nC_k \bigg(\frac{1}{2}\bigg)^{2n}\\ &= \bigg(\frac{1}{2}\bigg)^{2n}\sum_{k=0}^n {}_nC_k {}_nC_k\\ &= \bigg(\frac{1}{2}\bigg)^{2n} \sum_{k=0}^n {}_nC_{k} {}_nC_{n-k}\\ &= \bigg(\frac{1}{2}\bigg)^{2n} {}_{2n}C_n \end{align*} \]

📘 REMARKS

\(\frac{1}{\sqrt{1 + x}}\) をマクローリン展開すると

\[ \begin{align*} \frac{1}{\sqrt{1 + x}} &= 1 + (-1)^1 \frac{1}{2}x + (-1)^2\frac{1}{2}\frac{3}{2}\frac{1}{2!}x^2 + (-1)^3\frac{1}{2}\frac{3}{2}\frac{5}{2}\frac{1}{3!}x^3 + \cdots\\ &= 1 + \sum_{k=1}^\infty (-1)^k\frac{2k!}{2^k 2^k k! k!}x^k\\ &= 1 + \sum_{k=1}^\infty (-1)^k\frac{{}_{2k}C_k}{2^{2k}}x^k\\ \end{align*} \]

と 数列 \(\{p_n\}\) の情報を持っていることがわかる．このとき，\(\frac{1}{\sqrt{1 + x}}\) を \(\{p_n\}\) の確率母関数という．

一般二項係数

Exercise 3.20

実数 \(\alpha\), 正の整数 \(n\) に対して，次の等式を証明せよ

\[ \dbinom{-\alpha}{r} = (-1)^r\dbinom{\alpha + r - 1}{r} \]

Solution

\[ \begin{align*} \text{LHS} &= \frac{(-\alpha)(-\alpha-1)\cdots(-\alpha-(r-1))}{r!}\\ &= (-1)^r\frac{(\alpha)(\alpha+1)\cdots(\alpha+r-1)}{r!}\\ &= (-1)^r\dbinom{\alpha + r - 1}{r} \end{align*} \]

Exercise 3.21

実数 \(\alpha\), 正の整数 \(n\) に対して，次の等式を証明せよ

\[ \dbinom{1/2}{n} = \frac{(-1)^{n-1}}{2^{2n-1}n}\dbinom{2n-2}{n-1} \]

Solution

\[ \begin{align*} \text{LHS} &= \frac{(\frac{1}{2})(\frac{1}{2}-1)\cdots(\frac{1}{2}-(n-1))}{n!}\\[6pt] &= (-1)^{n-1}\frac{\frac{1}{2}\frac{1}{2}\frac{3}{2}\cdots \frac{2n-3}{2}}{n!}\\[6pt] &= (-1)^{n-1}\frac{(2n-2)!}{2^n 2^{n-1}(n-1)!n!}\\[6pt] &= (-1)^{n-1}\frac{(2n-2)!}{2^{2n-1}n(n-1)!(n-1)!}\\[6pt] &= \frac{(-1)^{n-1}}{2^{2n-1}n}\dbinom{2n-2}{n-1} \end{align*} \]

Exercise 3.22

実数 \(\alpha\), 正の整数 \(n\) に対して，次の等式を証明せよ

\[ \dbinom{-1/2}{n} = \frac{(-1)^{n}}{2^{2n}n}\dbinom{2n}{n} \]

Solution

\[ \begin{align*} \text{LHS} &= \frac{(-\frac{1}{2})(-\frac{1}{2}-1)\cdots(-\frac{1}{2}-(n-1))}{n!}\\[6pt] &= (-1)^{n}\frac{\frac{1}{2}\frac{3}{2}\cdots \frac{2n-1}{2}}{n!}\\[6pt] &= (-1)^{n-1}\frac{(2n)!}{2^n 2^{n}n!n!}\\[6pt] &= \frac{(-1)^{n}}{2^{2n}n}\dbinom{2n}{n} \end{align*} \]