場合の数 基礎Ⅱ
場合の数基礎Ⅱ
０．目次
６．組合せ
n種 類 の 異 な る も の {1,2,3,… ,n}か ら r個 取 出 し 、 並 べ る 順 序 を 考 え な い
1組 を 組 合 せ と い う 。
７．重複組合せ
n個 の 異 な る も の {1,2,3,… ,n}か ら 重 複 を 許 し て r個 選 ぶ 組 合 せ を
重複組合せという。
問題１
整数解の個数
- 1 -
場合の数 基礎Ⅱ
６．組合せ
n種 類 の 異 な る も の {1,2,3,… ,n}か ら r個 取 出 し 、 並 べ る 順 序 を 考 え な い 1組 を
組合せという。
●具体例
n=6,r=3の 場 合 、 20個 の 組 合 せ が あ る 。
（１）１番目の要素は、昇順に分類する。
（２）２番目の要素は、１番目の要素を越える要素で昇順に分類する。
（３）３番目の要素は、２番目の要素を越える要素で昇順に分類する。
（４）４番目以降も同様。
・樹形図
組合せ
1
2
3
4
5
6
4
5
6
5
6
6
4
5
6
5
6
6
5
6
6
6
3
4
2
5
3
4
3
5
4
4
5
5
- 2 -
123
124
125
126
134
135
136
145
146
156
234
235
236
245
246
256
345
346
356
456
辞書式順序
( 1)
( 2)
( 3)
( 4)
( 5)
( 6)
( 7)
( 8)
( 9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
場合の数 基礎Ⅱ
●組合せの個数
・考え方１
求 め る 組 合 せ を f(n,r)と す る 。
1番 目 に 1を 選 ん だ 場 合 、 以 降 、 n-1種 類 の 要 素 （ 2,3,… ,n） か ら r-1個 を 選 ぶ こ と
になる。
1番 目 に 2を 選 ん だ 場 合 、 以 降 、 n-2種 類 の 要 素 （ 3,4,… ,n） か ら r-1個 を 選 ぶ こ と
になる。
・・・
1番 目 に n-r+1を 選 ん だ 場 合 、 以 降 、 r-1種 類 の 要 素 （ n-r+2,n-r+3,… ,n） か ら r-1
個を選ぶことになる。
1
n-1種 類 r-1個
f(n-1,r-1)
2
n-2種 類 r-1個
f(n-2,r-1)
n-r+1
r-1種 類 r-1個
f(r-1,r-1)
n種 類 r個
f(n,r)
し た が っ て 、 f(n,r) = f(n-1,r-1)+f(n-2,r-1)+… +f(r-1,r-1) が 成 り 立 つ 。
n
0
1
2
3
4
5
6
7
8
9
r
0
1
2
3
4
5
6
7
8
9
1
1
1
1
1
1
1
1
1
1
2
3
4
5
6
7
8
9
1
3
6
10
15
21
28
36
1
4
10
20
35
56
84
1
5
15
35
70
126
1
6
21
56
126
1
7
28
84
1
8
36
1
9
1
f(8,4) = f(7,3)+f(6,3)+f(5,3)+f(4,3)+f(3,3)
f(8,4) = f(7,4)+f(7,3)
（参考）
f(n,r) = f(n-1,r-1) + f(n-2,r-1) + f(n-3,r-1) + … + f(r-1,r-1)
f(n-1,r) = f(n-2,r-1) + f(n-3,r-1) + … + f(r-1,r-1)
f(n,r) - f(n-1,r) = f(n-1,r-1)
より
f(n,r) = f(n-1,r) + f(n-1,r-1)
が導ける。
- 3 -
場合の数 基礎Ⅱ
・考え方２
n種 類 か ら r個 取 り 出 す 組 合 せ を 特 定 の 要 素 （ た と え ば 1） を 含 む も の と 含 ま な
いものに分類する。
1
x 1 ,x 2 ,… ,x r-1
１
x 1 ,x 2 ,… ,x r
前 者 は 、 要 素 １ 以 外 の n-1個 か ら r-1個 取 り 出 す の で f(n-1,r-1)通 り 、
後 者 は 、 要 素 １ 以 外 の n-1個 か ら r個 取 り 出 す の で f(n-1,r)通 り と な る 。
したがって、
f(n,r) = f(n-1,r-1) + f(n-1,r)
が成り立つ。
・考え方3
取 り 出 し た r個 の 要 素 か ら な る 1組 を 1列 に 並 べ る と 、 r! 通 り の 順 列 が で き る 。
こ れ ら は n個 の 異 な る も の か ら r個 取 り 出 し た 順 列 に 一 致 す る 。
し た が っ て 、 求 め る 組 合 せ の 個 数 f(n,r)は 、
f(n,r)× r! = 順 列 の 個 数 = P(n,r)
になる。よって、
f(n,r) =
P(n,r)
r!
=
n!
r!(n-r)!
と な る 。 f(n,r)は 、 C(n,r)と 書 か れ る 。
- 4 -
場合の数 基礎Ⅱ
●組合せの問題
（ １ ） 4個 の 異 な る 赤 玉 か ら 2個 、 5個 の 異 な る 白 玉 か ら 3個 選 ぶ
選 び 方 は 60通 り 。
4個 の 赤 玉 か ら 2個 選 ぶ 選 び 方 は 、 C(4,2)=6通 り 。
5個 の 白 玉 か ら 3個 選 ぶ 選 び 方 は 、 C(5,3)=10通 り 。
求 め る 選 び 方 は 、 積 の 法 則 を 適 用 し て 、 C(4,2)× C(5,3)=60通 り 。
（ ２ ） 4個 の 異 な る 赤 玉 と 5個 の 異 な る 白 玉 か ら 4個 選 ぶ と き 、
赤 玉 を 2個 以 上 選 ぶ 選 び 方 は 81通 り 。
選 ぶ 玉 の 個 数 は 4個 、 赤 玉 を 2個 以 上 選 ぶ と い う こ と が 決 ま っ て い る が 、
白玉、赤玉の個数は、いろいろ考えられるので、まず分類する必要がある。
白玉、赤玉の個数は、次のように分類できる。
(a)赤 玉 2個 、 白 玉 2個 の 場 合 ： C(4,2)× C(5,2)=60通 り 。
(b)赤 玉 3個 、 白 玉 1個 の 場 合 ： C(4,3)× C(5,1)=20通 り 。
(c)赤 玉 4個 、 白 玉 0個 の 場 合 ： C(4,4)× C(5,0)=1通 り 。
(a),(b),(c)、 そ れ ぞ れ 重 な ら な い 。
し た が っ て 、 和 の 法 則 を 適 用 し て 、 60+20+1=81通 り 。
（ ３ ） 6個 の 異 な る 赤 玉 を 3個 入 る 箱 Aと 3個 入 る 箱 Bに 分 け る 方 法 は 20通 り 。
（ 注 意 ） 箱 A,Bは 区 別 す る 。
箱 Aに 6個 の 赤 玉 か ら 3個 選 ぶ 選 び 方 は 、 C(6,3)=20通 り 。
箱 Bに 残 り の 3個 の 赤 玉 か ら 3個 選 ぶ 選 び 方 は 、 C(3,3)=1通 り 。
し た が っ て 、 積 の 法 則 を 適 用 し て 、 C(6,3)× C(3,3)=20通 り 。
（ ４ ） 6個 の 異 な る 赤 玉 を 3個 入 る 箱 と 3個 入 る 箱 に 分 け る 方 法 は 10通 り 。
（注意）箱は区別しない。
箱 を 区 別 し な い で 箱 A,Bに 分 け た 1組 に つ い て 、 箱 を 区 別 す る 方 法 は 、
2!倍 に な る 。 し た が っ て 、 求 め る 方 法 を a通 り と す る と 、 a× 2!は 、
(3)の 分 け 方 に な る 。
a× 2! = C(6,3)× C(3,3) = 20
a = 20/2! = 10通 り 。
①②③
④⑤⑥
同一視
①②③
④⑤⑥
- 5 -
①②③
④⑤⑥
場合の数 基礎Ⅱ
（ ５ ） 9個 の 異 な る 赤 玉 を 3個 入 る 箱 A、 3個 入 る 箱 B、 3個 入 る 箱 Cに
分ける方法は何通りか。
（ 注 意 ） 箱 A,B,Cは 区 別 す る 。
箱 Aに 9個 の 赤 玉 か ら 3個 選 ぶ 選 び 方 は 、 C(9,3)=84通 り 。
箱 Bに 残 り の 6個 の 赤 玉 か ら 3個 選 ぶ 選 び 方 は 、 C(6,3)=20通 り 。
箱 Cに 残 り の 3個 の 赤 玉 か ら 3個 選 ぶ 選 び 方 は 、 C(3,3)=1通 り 。
し た が っ て 、 積 の 法 則 を 適 用 し て 、 C(9,3)× C(6,3)× C(3,3)=1680通 り 。
（ ６ ） 9個 の 異 な る 赤 玉 を 3個 入 る 箱 、 3箱 に 分 け る 方 法 は 何 通 り か 。
（注意）箱は区別しない。
箱 を 区 別 し な い と 、3!通 り の 入 れ 方 を ひ と つ の 入 れ 方 と 見 な す こ と が で き る 。
①②③
④⑤⑥
⑦⑧⑨
①②③
④⑤⑥
⑦⑧⑨
①②③
④⑤⑥
⑦⑧⑨
同一視
①②③
④⑤⑥
⑦⑧⑨
①②③
④⑤⑥
⑦⑧⑨
①②③
④⑤⑥
⑦⑧⑨
①②③
④⑤⑥
⑦⑧⑨
求 め る 方 法 を a通 り と す る と 、 a× 3!は 、 (6)の 分 け 方 に な る 。 し た が っ て 、
a× 3! = 1680
a = 1680/3! = 280通 り 。
- 6 -
場合の数 基礎Ⅱ
● 二 項 係 数 C(n,r)の 性 質
（ １ ） n個 の 異 な る も の か ら r個 取 り 出 し た １ 組 の 個 数 を C(n,r)と す る 。
次の式が成り立つ。
（ ａ ） C(n,r) = C(n-1,r) + C(n-1,r-1)
・解１
C(n-1,r) + C(n-1,r-1)
=
=
(n-1)!
+
(n-1-r)!r!
n!
(n-r)!r!
(n-1)!
(n-r)!(r-1)!
=
n!
(n-r)!r!
(
n-r
n
+
r
n
)
= C(n,r)
・解２
ｎ個の中の特定の１個をＡとする。ｒ個の要素をもつ部分集合は
Ａ を 含 む も の と 、Ａ を 含 ま な い も の に 分 け ら れ る 。前 者 は 、C(n-1,r-1)通 り あ る 。
後 者 は 、 C(n-1,r)通 り あ る 。
し た が っ て 、 C(n-1,r-1) + C(n-1,r) 通 り 。
（ ｂ ） C(n,r) = C(n,n-r)
解
C(n,r) =
n!
(n-r)!r!
C(n,n-r) =
n!
(n-r)!r!
（ ２ ） 次 の 式 (a)～ (e)を 示 せ 。
（ ａ ） (1 + x) n = C(n,0) + C(n,1)x 1 + C(n,2)x 2 + … + C(n,n-1)x n-1
+ C(n,n)x n
(a)の 解
(a + b)(c + d)(e + f)は 、
(a + b)(c + d)(e + f) = (ac + ad + bc + bd)(e + f)
= ace + acf + ade + adf + bce + bcf + bde + bdf
と な る 。 各 項 ace,… ,bdfは 、 も と の (a+b),(c+d),(e+f)の そ れ ぞ れ か ら １ つ ず つ
選ばれた３個の文字の積になっている。
- 7 -
場合の数 基礎Ⅱ
こ の 考 え 方 を (1 + x) 3 に 適 用 し て み る 。
(1 + x)(1 + x)(1 + x) = 1× 1× 1 + 1× 1× x + 1× x× 1 + 1× x× x
+ x× 1× 1 + x× 1× x + x× x× 1 + x× x× x
x 1 の 係 数 は 、 1× 1× x, 1× x× 1, x× 1× 1
x 2 の 係 数 は 、 1× x× x, x× 1× x, x× x× 1
x 3 の 係 数 は 、 x× x× x か ら 1 と な る 。
から 3 となる。
から 3 となる。
同 様 に 、 (1 + x) n の x r の 係 数 を 考 え る 。
n個
x r の 係 数 は 、 (1 + x)(1 + x)(1 + x)… (1 + x) の 中 か ら
xを r 個 、 1を n-r 個 選 ん で 作 ら れ る 項 の 個 数 と な る 。
そ の 選 び 方 は 、 C(n,r)通 り あ る 。 し た が っ て 、 x r の 係 数 は 、 C(n,r)と な る 。
（ ｂ ） 2 n = C(n,0) + C(n,1) + C(n,2) + … + C(n,n-1) + C(n,n)
(b)の 解
（ａ）において、x = 1 とする。
（ ｃ ） 0 = C(n,0) + C(n,1)(-1) 1 + C(n,2)(-1) 2 + …
+ C(n,n-1)(-1) n-1 + C(n,n)(-1) n
(c)の 解
（ ａ ） に お い て 、 x = -1 と す る 。
（ ｄ ） n(1 + x) n-1 = C(n,1) + 2C(n,2)x 1 + …
+ (n-1)C(n,n-1)x n-2 + nC(n,n)x n-1
(d)の 解
（ ａ ） に お い て 、 xで 両 辺 を 微 分 す る 。
（ ｅ ） n2 n-1 = C(n,1) + 2C(n,2) + … + (n-1)C(n,n-1) + nC(n,n)
(e)の 解
（ｄ）において、x = 1 とする。
- 8 -
場合の数 基礎Ⅱ
７．重複組合せ
n個 の 異 な る も の {1,2,3,… ,n}か ら 重 複 を 許 し て r個 選 ぶ 組 合 せ を 重 複 組 合 せ と
いう。
●具体例
n=3,r=5の 場 合 、 21個 の 重 複 組 合 せ が あ る 。
（１）１番目の要素は、昇順に分類する。
（２）２番目の要素は、１番目の要素以上の要素で昇順に分類する。
（３）３番目の要素は、２番目の要素以上の要素で昇順に分類する。
（４）４番目以降も同様。
・樹形図
1
1
1
1
2
2
3
2
3
2
2
3
2
3
3
2
3
2
3
3
2
3
3
3
2
3
3
3
3
3
3
3
3
3
- 9 -
1
2
3
2
3
3
2
3
3
3
2
3
3
3
3
2
3
3
3
3
3
重複組合せ
11111
11112
11113
11122
11123
11133
11222
11223
11233
11333
12222
12223
12233
12333
13333
22222
22223
22233
22333
23333
33333
辞書式順序
( 1)
( 2)
( 3)
( 4)
( 5)
( 6)
( 7)
( 8)
( 9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
場合の数 基礎Ⅱ
●重複組合せの個数
・考え方１
求 め る 重 複 組 合 せ を f(n,r)と す る 。
1番 目 に 1を 選 ん だ 場 合 、 以 降 、 n種 類 の 要 素 （ 1,2,… ,n） か ら r-1個 を 選 ぶ こ と に
な る 。 こ の 方 法 は 、 f(n,r-1) 通 り あ る 。
1番 目 に 2を 選 ん だ 場 合 、 以 降 、 n-1個 の 要 素 （ 2,3,… ,n） か ら r-1個 を 選 ぶ こ と に
な る 。 こ の 方 法 は 、 f(n-1,r-1) 通 り あ る 。
・・・
1番 目 に nを 選 ん だ 場 合 、 以 降 、 1個 の 要 素 （ n） か ら r-1個 を 選 ぶ こ と に な る 。
こ の 方 法 は 、 f(1,r-1) 通 り あ る 。
n種 類 r個
f(n,r)
1
n種 類 r-1個
f(n,r-1)
2
n-1種 類 r-1個
f(n-1,r-1)
n
1種 類 r-1個
f(1,r-1)
し た が っ て 、 f(n,r) = f(n,r-1) + f(n-1,r-1) + … + f(1,r-1) が 成 り 立 つ 。
n
0
1
2
3
4
5
6
7
r
0
1
2
3
4
5
1
2
3
4
5
6
1
3
6
10
15
21
1
4
10
20
35
56
1
5
15
35
70
126
1
6
21
56
126
252
6
7
8
9
f(6,5) = f(6,4)+f(5,4)+f(4,4)+f(3,4)+f(2,4)+f(1,4)
f(6,5) = f(6,4)+f(5,5)
（参考）
f(n,r) = f(n,r-1) + f(n-1,r-1) + f(n-2,r-1) + … + f(1,r-1)
f(n-1,r) = f(n-1,r-1) + f(n-2,r-1) + … + f(1,r-1)
f(n,r) - f(n-1,r) = f(n,r-1)
より
f(n,r) = f(n,r-1) + f(n-1,r)
が導ける。
- 10 -
場合の数 基礎Ⅱ
・考え方２
n種 類 か ら 重 複 を 許 し て r個 取 り 出 す 重 複 組 合 せ を 、 特 定 の 要 素 （ た と え ば 1）
に着目して、その要素を含む重複組合せとその要素を含まない重複組合せに分類
する。
1
x 1 ,x 2 ,… ,x r-1
１
x 1 ,x 2 ,… ,x r
前 者 は 、 要 素 １ を 含 む n個 か ら 重 複 を 許 し て r-1個 取 り 出 す の で f(n,r-1)通 り 、
後 者 は 、 要 素 １ 以 外 の n-1個 か ら r個 取 り 出 す の で f(n-1,r)通 り と な る 。
まとめると、
f(n,r) = f(n,r-1) + f(n-1,r)
となる。
・考え方３
（ １ ）「 4種 類 (① ,② ,③ ,④ )の 玉 か ら 、 重 複 を 許 し て 6個 選 ぶ 選 び 方 」
たとえば、①①①③③④。
（ ２ ）6個 の 玉 に 付 け ら れ た 番 号 に 従 い 、4種 類 の 箱 (箱 1,箱 2,箱 3,箱 4)に 入 れ る 。
同時に玉から番号を消す。
こうすると、重複組合せ①①①③③④につぎの配置が対応する。
○○○
箱1
○○
箱3
箱2
○
箱4
（ ３ ） 上 記 配 置 と 「 6個 の 区 別 の つ か な い 玉 を １ 列 に 並 べ 、 3(=4-1)個 の 仕 切 を
入れる入れ方」が対応する。
箱1
箱2
○○○｜
箱3
箱4
｜ ○○｜ ○
（ ４ ） 上 記 入 れ 方 と 「 9(=6+4-1) 個 の 区 別 の つ か な い 玉 を １ 列 に 並 べ 、 そ の な か
か ら 3(=4-1)個 を 選 び 、 仕 切 と す る 選 び 方 」 が 対 応 す る 。
○
○
○
○
○
○
○
｜
○
｜
○
○
○
○
○
｜
○
○
こ の 選 び 方 は 、 C(6+4-1,4-1) =84 通 り と な る 。
し た が っ て 、「 n種 類 の も の か ら 、 重 複 を 許 し て r個 選 ぶ 選 び 方 」 は 、
C(r+n-1,n-1) = C(r+n-1,r) 通 り
となる。
- 11 -
場合の数 基礎Ⅱ
・考え方４
{1,2,… ,n}か ら 重 複 を 許 し て r個 選 ば れ た 重 複 組 合 せ の 集 合 を A、 そ の 要 素 を a=
a(1)a(2)… a(r)と す る 。 集 合 Aの そ れ ぞ れ の 要 素 に つ い て 、 そ の 先 頭 か ら i番 目 の
要 素 a(i)に (i-1)を 加 え る 操 作 f(a)を し て 得 ら れ た 新 た な 新 た な 組 合 せ を x=x(1)x
(2)… x(r)と し 、 そ の 集 合 を Xと す る 。 x=f(a)と 書 く こ と に す る 。
x(1) =
x(2) =
・・・
x(i) =
・・・
x(r) =
a(1) + 0
a(2) + 1
a(i) + i-1
a(r) + r-1
x(1)<x(2)<… <x(r) と な る の で 、 集 合 Xは 、 {1,2,… ,n,n+1,… ,n+r-1}の も の か
ら r個 取 り 出 す 組 合 せ 集 合 Xの 部 分 集 合 と 考 え ら れ る 。
n=3,r=5の と き 、
集合A
11111
11112
11113
11122
11123
11133
11222
11223
11233
11333
12222
12223
12233
12333
13333
22222
22223
22233
22333
23333
33333
集合X
12345
12346
12347
12356
12357
12367
12456
12457
12467
12567
13456
13457
13467
13456
13457
23456
23457
23467
23567
24567
34567
- 12 -
場合の数 基礎Ⅱ
さ て 、 集 合 Aの 要 素 を a,bと す る と 、
「 a≠ bな ら ば 、 f(a)≠ f(b), f(a)∈ X,f(b)∈ X」
が 成 り 立 つ こ と か ら 、 |A|≦ |X|が 導 か れ る 。
A
X
a○
● f(a)
b○
● f(b)
●
一 方 、 操 作 fの 逆 操 作 gを つ ぎ の よ う に 定 義 す る と 、
b(1) =
b(2) =
・・・
b(i) =
・・・
b(r) =
x(1) - 0
x(2) - 1
x(i) - (i-1)
x(r) + r-1
b=b(1)b(2)… b(r)は 集 合 Aの 要 素 と な る 。 b=g(x)と 書 く こ と に す る 。
こ こ で 、 集 合 Xの 要 素 を x,yと す る と 、
「 x≠ yな ら ば 、 g(x)≠ g(y), g(x)∈ A,g(y)∈ A」
が 成 り 立 つ こ と か ら 、 |X|≦ |A|が 導 か れ る 。
A
X
g(x)○
●x
g(y)○
●y
○
両 者 （ |A|≦ |X|、 |X|≦ |A|） か ら 、 |A|=|X|を 得 る こ と が で き る 。
|X|=C(n+r-1,r)よ り 、 |A|=C(n+r-1,r)を 得 る 。
- 13 -
場合の数 基礎Ⅱ
問題
問題１
整数解の個数
（ １ ） x + y + z = 6 ( x≧ 1,y≧ 1,z≧ 1 ) を 満 た す 解 (x,y,z)は 、 ①
通り。
（ ２ ） x + y + z = 4 ( x≧ 0,y≧ 0,z≧ 0 ) を 満 た す 解 (x,y,z)は 、 ②
通り。
（ ３ ） x + y + z = 8 ( x≧ 0,y≧ 1,z≧ 2 ) を 満 た す 解 (x,y,z)は 、 ③
通り。
（ ４ ）x + y + z ≦ 5 ( x≧ 0,y≧ 0,z≧ 0 ) を 満 た す 解 (x,y,z)は 、④
通り。
- 14 -
© Copyright 2024 ExpyDoc
