0以上の数5個の和は6以下 /「算数にチャレンジ!!」第1142問

問題概略
ボールと仕切りの順列
おまけ：動的計画法

問題概略

0 以上の 5 つの整数 $a$ , $b$ , $c$ , $d$ , $e$ があります。
$a+b+c+d+e$ は 6 以下であるとき， $(a,\, b,\, c,\, d,\, e)$ は何通りあるでしょうか。
http://www.sansu.org/used-html/index1142.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

ボールと仕切りの順列

$a+b+c+d+e=k\ (0\leqq k\leqq 6)$ のとき， $(a,\, b,\, c,\, d,\, e)$ は $k$ 個のボールと 4 個の仕切りの順列と同じ数だけあって ${}_{k+4}\mathrm{C}_4$ 通り。

これの和が答えです。462 通りですね。

$ans=\sum_{k=0}^6 {}_{k+4}\mathrm{C}_4=\mathbf{462}$

$f=6-(a+b+c+d+e)$ とおいて「〇〇以下」を等式に直す解法も有名です。

$a+b+c+d+e+f=6,\, a\geqq 0,\, b\geqq 0,\, c\geqq 0,\, d\geqq 0,\, e\geqq 0,\, f\geqq 0$

$(a,\, b,\, c,\, d,\, e,\, f)$ は 6 個のボールと 5 個の仕切りの順列と同じ数だけあります。

$ans={}_{6+5}\mathrm{C}_5={}_{11}\mathrm{C}_5=\mathbf{462}$

おまけ：動的計画法

動的計画法で解いてみました。
0 以上の整数 $n$ 個の組で和が $s$ のものが $dp(n,\, s)$ 個あるとします。

$n-1$ 個目の数までの和が $i\ (0\leqq i\leqq s)$ の組は $dp(n-1,\, i)$ 個です。
このとき $n$ 個目の数は $s-i$ と決まるので $n$ 個の数の組も $dp(n-1,\, i)$ 個です。

$dp(n,\, s)=\sum_{i=0}^s dp(n-1,\, i)$

求める個数は $\displaystyle\sum_{i=0}^6 dp(5,\, i)=dp(6,\, 6)$ です。
計算にはmathematicaを使いました。

  In[]:= AbsoluteTiming[
    dp[1, s_] = 1;
    dp[n_, s_] := dp[n, s] = Sum[dp[n - 1, i], {i, 0, s}];
    ans = dp[6, 6]]
   
  Out[]= {0.0000543, 462}

variee.hatenablog.com