この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

離散数学・組合せ論の問題

難易度 3期末試験の応用レベル大学数学離散数学・組合せ論

整数 $x_{1}, x_{2}, x_{3}, x_{4}$ の組 $(x_{1}, x_{2}, x_{3}, x_{4})$ で、
$x_{1} + x_{2} + x_{3} + x_{4} = 20, 0 \leq x_{i} \leq 7 (i = 1, 2, 3, 4)$
を満たすものの個数を求めよ。

この問題で使うもの

一般の包除原理（説明と入口の問題）
同じものを含む順列・重複組合せ（説明と入口の問題）

この問題を解けるようになるまで（9 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

上限 $x_{i} \leq 7$ を外した 0 以上の整数解の個数は重複組合せで求められます。そこから上限を破るものを包除原理で除きましょう。

ヒント 2

$A_{i}$ を「 $x_{i} \geq 8$ 」という条件とすると、 $x_{i} = y_{i} + 8$ と置き換えることで $∣ A_{i} ∣$ や $∣ A_{i} \cap A_{j} ∣$ も重複組合せで数えられます。

ヒント 3

$∣ U ∣ = (3 23)$ 、 $∣ A_{i} ∣ = (3 15)$ 、 $∣ A_{i} \cap A_{j} ∣ = (3 7)$ で、3 つ以上の $A_{i}$ が同時に成り立つことはありません。

答えと解説

答えを見る

161

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

0 以上の整数解 $(x_{1}, \dots, x_{4})$ で $x_{1} + \dots + x_{4} = 20$ となるもの全体を $U$ とする。重複組合せにより
$∣ U ∣ = (3 20 + 3) = (3 23) = 1771.$
$i = 1, \dots, 4$ に対し $A_{i} = {x_{i} \geq 8}$ とおき、どの $A_{i}$ にも属さない解を包除原理で数える。

$∣ A_{i} ∣$ : $x_{i} = y_{i} + 8$ ( $y_{i} \geq 0$ ) とおくと、和が $12$ の 0 以上の整数解になるので $(3 12 + 3) = (3 15) = 455$ 。
$∣ A_{i} \cap A_{j} ∣$ ( $i \neq = j$ ): 同様に 16 を引いて和が 4 の解になるので $(3 4 + 3) = (3 7) = 35$ 。
3 つ以上の共通部分: $3 \cdot 8 = 24 > 20$ なので空集合。

よって求める個数は
$1771 - (1 4) \cdot 455 + (2 4) \cdot 35 = 1771 - 1820 + 210 = 161.$

確認: $y_{i} = 7 - x_{i}$ とおくと、条件は $y_{1} + \dots + y_{4} = 8$ , $0 \leq y_{i} \leq 7$ と同値になる。0 以上の整数解は $(3 11) = 165$ 個で、そのうち $y_{i} \geq 8$ となるのは $y_{i} = 8$ でほかが 0 の 4 個だけなので、 $165 - 4 = 161$ で一致する。

別解

$x_{i} \leq 7$ の条件を包除原理で処理する。条件なし（ $x_{i} \geq 0$ ）の解は $(3 23) = 1771$ 。ある $x_{i} \geq 8$ の解は $y_{i} = x_{i} - 8$ として和 12 で $(3 15) = 455$ 、4 変数分で $4 \cdot 455 = 1820$ 。2 つが $\geq 8$ だと和 4 で $(3 7) = 35$ 、組は 6 通りで $210$ 。3 つが $\geq 8$ だと和が負で 0。よって $1771 - 1820 + 210 = 161$ 。検算: $x_{i} \to 7 - x_{i}$ で和 $28 - 20 = 8$ の解と対応し、和 8 で $x_{i} \leq 7$ なら $(3 11) - 4 (3 3) = 165 - 4 = 161$ と一致。

離散数学・組合せ論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題