桁数字の和が4以下で5桁の数の個数 /「算数にチャレンジ!!」第1035問

問題概略
全部書く（解法１）
二項係数であらわす（解法２）
漸化式（解法３）
- 右に1桁足して立式
- 行列で書いて一般項を求める

問題概略

次の条件をみたす整数の個数を求めてください。

10000 以上 99999 以下

各位の数の和は 4 以下

http://www.sansu.org/used-html/index1035.html

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

drive.google.com

全部書く（解法１）

この問題は全部書くのが手っ取り早いと思います。 $abcde$ の形の数を考えます。

和が 1 のときは 10000 のみの 1 個。

和が 2 のときは $1\square\square\square\square$ と 20000 が条件をみたします。この形の数は $4+1=5$ 個。

和が 3 のときは $1\square\square\square\square$ , $2\square\square\square\square$ , 30000 が条件をみたします。

$1\square\square\square\square$ のときは「1 つの $\square$ に 2 を入れる」と「2 つの $\square$ に 1 を入れる」の 2 つの場合があります。これは $4+{}_4\mathrm{C}_2=10$ 個。

$2\square\square\square\square$ の形の数は 4 個で，全部で $10+4+1=15$ 個。

和が 4 のときは $1\square\square\square\square$ , $2\square\square\square\square$ , $3\square\square\square\square$ , 40000 が条件をみたします。

$1\square\square\square\square$ のときは「1 つの $\square$ に 3 を入れる」「2 つの $\square$ に 1 と 2 を入れる」「3 つの $\square$ に 1 を入れる」の 3 つの場合があって $4+4\cdot 3+{}_4\mathrm{C}_3=20$ 個。

$2\square\square\square\square$ のときは「1 つの $\square$ に 2 を入れる」と「2 つの $\square$ に 1 を入れる」の 2 つの場合があります。これは $4+{}_4\mathrm{C}_2=10$ 個。

和が 4 のときは全部で $20+10+4+1=35$ 個。

以上の和をとると $1+5+15+35=56$ になるので，求める個数は「56 個」です。

二項係数であらわす（解法２）

首位の数字を固定

首位の数字を $a=k\ (1\leqq k\leqq 4)$ と固定して，残りの桁数字の組を考えます。

条件は $b+c+d+e\leqq 4-k$ です。 $f=4-(a+b+c+d+e)$ とおきます。

$b+c+d+e+f=4-a$

これをみたす $b$ ～ $f$ （すべて 0 以上）の組は $4-k$ 個のボールと 4 個の仕切りの順列と同じ数だけあります。

${}_{(4-k)+4}\mathrm{C}_4={}_{8-k}\mathrm{C}_4\,\text{個}$

$k$ についての和をとったものが答えです。
\begin{align*}
\sum_{k=1}^4 {}_{8-k}\mathrm{C}_4 &=
{}_{7}\mathrm{C}_4+{}_{6}\mathrm{C}_4+{}_{5}\mathrm{C}_4+{}_{4}\mathrm{C}_4\\
&=35+15+5+1=56\mbox{　……$\spadesuit$}
\end{align*}

公式を使って改善

$\spadesuit$ では二項係数の左側の添字が変化するときの和を求めました。この計算では次の公式が使えます。

$\sum_{k=r}^n {}_{k}\mathrm{C}_r={}_{n+1}\mathrm{C}_{r+1}$

右辺は「1～ $n+1$ から $r+1$ 個の整数を選ぶときの場合の数」です。

左辺ではこの場合の数を「最大値が $r+1$ ～ $n+1$ のどれか」で場合分けして求めています。たとえば最大値が $r+1$ のとき，残り $r$ 個の数は 1～ $r$ から選ぶわけですね。

公式の説明が終わったところで，もとの問題に戻りましょう。 $\spadesuit$ の計算は次のようになります。

\begin{align*}
\sum_{k=1}^4 {}_{8-k}\mathrm{C}_4 &=\sum_{l=4}^7 {}_{l}\mathrm{C}_4\quad (8-k=l)\\
&={}_{8}\mathrm{C}_5={}_{8}\mathrm{C}_3=56
\end{align*}

一般化

同じように考えると，もとの問題を一般化した問題も解けます。
「 $n$ 桁の整数で桁数字の和が $k\ (1\leqq k\leqq 9)$ のものの個数を求めよ」を考えます。
桁数字を首位から順に $a_1$ ～ $a_n$ とします。

まず $a_1+a_2+\cdots+a_n \leqq k$ で $a_1$ を固定します。

$a_2+\cdots+a_n \leqq k-a_1$

$b=k-(a_1+a_2+\cdots+a_n)$ とおきます。

$a_2+\cdots+a_n +b=k-a_1$

$a_2$ ～ $a_n$ と $b$ はすべて 0 以上なので，これをみたす $a_2$ ～ $a_n$ と $b$ の組は $k-a_1$ 個のボールと $n-1$ 個の仕切りの順列と同じだけあります。

${}_{(k-a_1)+(n-1)}\mathrm{C}_{n-1}={}_{n+k-a_1-1}\mathrm{C}_{n-1}\,\text{個}$

$a_1$ について和をとって，公式を使います。

\begin{align*}
\sum_{a_1=1}^k {}_{n+k-a_1-1}\mathrm{C}_{n-1}
&=\sum_{l=n-1}^{n+k-2} {}_{l}\mathrm{C}_{n-1} \quad (l=n+k-a_1-1) \\
&={}_{n+k-1}\mathrm{C}_{n}
\end{align*}

一般化した問題の答えは「 ${}_{n+k-1}\mathrm{C}_{n}$ 個」です。

漸化式（解法３）

右に1桁足して立式

$n$ 桁の数で桁数字の和が $k$ のものが $dp(n,\, k)$ 個あるとして漸化式を立てます。

いま考えている問題では $k$ は 1 以上 4 以下なので初期条件は次のようになります。

\begin{align*}dp(1,\, k)=\begin{cases}
1 & (1\leqq k\leqq 4)\\[3pt]
0 & (\text{上記以外})
\end{cases}\end{align*}

$n-1$ 桁で桁数字の和が $l\ (1\leqq l\leqq k)$ のとき右に $k-l$ を書き足すと $n$ 桁で桁数字の和が $k$ の数ができます。

\begin{align*}
dp(n,\, k) &=dp(n-1,\, 1)+dp(n-1,\, 2)+\cdots+dp(n-1,\, k)\\
&=\sum_{l=1}^k dp(n-1,\, l)
\end{align*}

式で書くと難しそうですが，表を書くと簡単です。

f:id:variee:20220110232557p:plain

1 行目は $n=1$ なので 1 を 4 つ書きます。
2 行目以降は「1 行上を見て，左端から自分の真上までの数の和を書きこむ」の繰り返しです。
要するに累積和を繰り返し求めることで表が完成します。

行列で書いて一般項を求める

漸化式を行列で書くと次のようになります。

\begin{align*}
\begin{pmatrix}
dp(n+1,1)\\dp(n+1,2)\\dp(n+1,3)\\dp(n+1,4)
\end{pmatrix}
=\begin{pmatrix}
1&0&0&0\\1&1&0&0\\1&1&1&0\\1&1&1&1
\end{pmatrix}
\begin{pmatrix}
dp(n,1)\\dp(n,2)\\dp(n,3)\\dp(n,4)
\end{pmatrix}
\end{align*}

この下三角行列の $n$ 乗は簡単に求められるので $dp(n,\, 1)$～$dp(n,\, 4)$ の一般項が求められます。

\begin{align*}
\begin{pmatrix}
dp(n,1)\\dp(n,2)\\dp(n,3)\\dp(n,4)
\end{pmatrix}
&=\begin{pmatrix}
1&0&0&0\\1&1&0&0\\1&1&1&0\\1&1&1&1
\end{pmatrix}^{n-1}
\begin{pmatrix}
1\\1\\1\\1
\end{pmatrix}\\
&=\begin{pmatrix}
1&0&0&0\\n-1&1&0&0\\\frac{1}{2}n(n-1)&n-1&1&0\\\frac{1}{6}(n+1)n(n-1)&\frac{1}{2}n(n-1)&n-1&1
\end{pmatrix}
\begin{pmatrix}
1\\1\\1\\1
\end{pmatrix}\\
&=\begin{pmatrix}
1\\n\\ \frac{1}{2}n(n+1) \\ \frac{1}{6}n(n+1)(n+2)
\end{pmatrix}
\end{align*}