【アルゴ式数学】場合の数、重複組み合わせ
Q&A
Closed
アルゴ式の「N個の整数（1）」という問題が解けず、順に解説を見ていっているが、理解がおいつきません。
解答の最後に
これは グループ分け (3) の設定の $N,M$ を入れ替えたものなので
とあるので、「グループ分け（3）」という問題から記載していきます。
グループ分け（3）
問題文
カメのアルルの手元には $N$ 個のボールと $M$ 個の箱があります。 各ボールは区別ができませんが、各箱には $0$ ~ $M−1$ までの数字が書かれており区別できます。
全てのボールを箱に入れるとき、入れ方が全部で何パターン考えられるか計算するプログラムを作成してください。 ただし、どの箱にも $1$ 個以上のボールを入れる必要があるものとします。
これはまだ分かります。
前提として、箱よりボールの数が少ない場合、どう頑張ってもボールが入らない箱が生まれます。
以下、そうでない場合を考えます。
$N = 5, M = 4$ とすると、箱$4$個、ボール$5$個。
箱:□、ボール:⚪︎で表現するとします。
一旦全ての箱にボールを一つ入れると、ボールが1つ余ります。
[!NOTE]
□□□□
↑ ↑ ↑ ↑
⚪︎⚪︎⚪︎⚪︎ ⚪︎<余りです
あとは4つの箱のうち好きなものを選べばいいので、${}_4 C_1$ でよいです。
一般化して$N, M$を用いて表せば、下記の通りとなります。
コードでは下記の通り。
import math
def combinations(n, r):
"""nCrを計算する関数"""
return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
N, M = map(int, input().split())
ans = combinations(N-1, N-M) if N >= M else 0
print(ans)
N個の整数（1）
問題文
次の条件を満たす $N$ 個の自然数の組 $(A_{0},A_{1},…,A_{N−1})$ の個数を求めるプログラムを作成してください。
$$\displaystyle\sum_{i=0}^{N−1}A_i=M$$
本題です。
とっかかりから分からなかったため、私は大人しく解説を読みました。
解説はこの通り語っていました。
以下解説を引用します。私のリアクションと共にどうぞ。
一見すると手がかりのない問題に見えますが、条件をわかりやすいものに言い換えてみましょう。
私：せやな、頼むわ。
$N$ 個の整数を箱に例え、割り当てられる数の総和 $M$ をボールの個数に例えると、与えられた条件は次のように言い換えられます。
- $N$ 個の箱にはそれぞれ 1 つ以上のボールが入る。
- $N$ 個の箱に入っているボールの総和は $M$ 個である。
私：う、うん？
これは グループ分け (3) の設定の $N,M$ を入れ替えたものなので
私：そんなわけなくない？
というわけで、この問題は例えたあたりからついていけなくなった形です。どういうこっちゃ…。
回答としては文字通り、 グループ分け (3) の設定の $N,M$ を入れ替え ればいいので、下記の計算式を表現すれば良いとのことでした。
なんなら式変形もわからんねぇ。
以上、私の突っかかりについて、どなたか解説いただいてもよろしいでしょうか。
ついでにLaTeXでCombinationの式の書き方も教えてくださると幸いです。
{}{M-1} C{N-1} じゃダメなんですかね。
