Σ[k=1,m]x_k=nなどの解の個数

次の方程式、または不等式を満たす解の個数は以下のようになります。

ただし、全て \(m,n \in \mathrm{N}\), \(m \leq n\), \(x_1,x_2,x_3 \cdots ,x_m \in \mathrm{Z}\)
\(a_1,a_2,a_3 \cdots ,a_m \in \mathrm{Z}\) とする。

\((1)\)  \(\displaystyle\sum_{k=1}^m x_k=n  (x_1,x_2,x_3, \cdots ,x_m \geq 0)\)
          解の個数: \({}_m\mathrm{H}_n\) 通り

\((2)\)  \(\displaystyle\sum_{k=1}^m x_k=n  (x_1,x_2,x_3, \cdots ,x_m \geq 1)\)  
          解の個数: \({}_{n-1}\mathrm{C}_{m-1}\) 通り

\((3)\)  \(\displaystyle\sum_{k=1}^m x_k=n  (x_1 \geq a_1,x_2 \geq a_2,x_3 \geq a_3, \cdots ,x_m \geq a_m)\)

          解の個数: \({}_{n+m-1-\sum_{k=1}^m a_k}\mathrm{C}_{m-1}\) 通り

\((4)\)  \(\displaystyle\sum_{k=1}^m x_k \leq n  (x_1,x_2,x_3, \cdots ,x_m \geq 0)\)
          解の個数: \({}_{n+m}\mathrm{C}_m\) 通り

\((5)\)  \(1 \leq x_1 \lt x_2 \lt x_3 \lt \cdots \lt x_m \leq n\)

          解の個数:\({}_{n}\mathrm{C}_{m}\) 通り

\((6)\)  \(1 \leq x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_m \leq n\)

          解の個数:\({}_{n}\mathrm{H}_{m}\) 通り








<証明(考え方)>

\((1)\)  \(\displaystyle\sum_{k=1}^m x_k=x_1+x_2+x_3+ \cdots +x_m=n  (x_1,x_2,x_3, \cdots ,x_m \geq 0)\)

これは \(n\) 個のボールと \(m-1\) 個の仕切りを並べるときの場合の数に等しい。

          よって、解の個数は \({}_{n+m-1}\mathrm{C}_{m-1}={}_{n+m-1}\mathrm{C}_{n}={}_{m}\mathrm{H}_{n}\)







\((2)\)  \(\displaystyle\sum_{k=1}^m x_k=x_1+x_2+x_3+ \cdots +x_m=n  (x_1,x_2,x_3, \cdots ,x_m \geq 1)\)  

\((1)\) の不等式に帰着させるように式を変形します。

すなわち、両辺から \(m\) を引きます。$$(x_1-1)+(x_2-1)+(x_3-1)+ \cdots +(x_m-1)=n-m$$このとき、それぞれ$$x_1-1 \geq 0, x_2-1 \geq 0, x_3-1 \geq 0,  \cdots  ,x_m-1 \geq 0$$となるので、これは \(n-m\) 個のボールと \(m-1\) 個の仕切りを並べるときの場合の数に等しい。

           よって、解の個数は \({}_{n-m+(m-1)}\mathrm{C}_{m-1}={}_{n-1}\mathrm{C}_{m-1}\)







\((3)\)  \(\displaystyle\sum_{k=1}^m x_k=n  (x_1 \geq a_1,x_2 \geq a_2,x_3 \geq a_3, \cdots ,x_m \geq a_m)\)

\((1)\) の不等式に帰着させるように式を変形します。

すなわち、両辺から \(\displaystyle\sum_{k=1}^m a_k\) を引きます。$$(x_1-a_1)+(x_2-a_2)+(x_3-a_3)+ \cdots +(x_m-a_m)=n-\displaystyle\sum_{k=1}^m a_k$$このとき、それぞれ$$x_1-a_1 \geq 0, x_2-a_2 \geq 0, x_3-a_3 \geq 0,  \cdots  ,x_m-a_m \geq 0$$となるので、これは \(n-\displaystyle\sum_{k=1}^m a_k\) 個のボールと \(m-1\) 個の仕切りを並べるときの場合の数に等しい。

          よって、解の個数は \({}_{n+m-1-\sum_{k=1}^m a_k}\mathrm{C}_{m-1}\) 通り







\((4)\)  \(\displaystyle\sum_{k=1}^m x_k=x_1+x_2+x_3+ \cdots +x_m \leq n  (x_1,x_2,x_3, \cdots ,x_m \geq 0)\)

上記の不等式を満たす解の個数を求めるためには

次のように「 \(x_{m+1}\,(\geq 0)\) の項を加えた方程式」を考えます。

(\(x_1+x_2+x_3+ \cdots +x_m\) が \(n\) に至らないときは、その不足分を \(x_{m+1}\) が補う)$$x_1+x_2+x_3+ \cdots +x_m+x_{m+1} =n  (x_1,x_2,x_3, \cdots ,x_m,x_{m+1} \geq 0)$$これは \(n\) 個のボールと \(m\) 個の仕切りを並べるときの場合の数に等しい。


          よって、解の個数は \({}_{n+m}\mathrm{C}_m\) 通り







\((5)\)  \(1 \leq x_1 \lt x_2 \lt x_3 \lt \cdots \lt x_m \leq n\)

これは \(1\) から \(n\) までの数字から \(m\) 個を選んで、小さい数字から

\(x_1,x_2,x_3, \cdots,x_m\) に割り当てれば良い。よって

          解の個数:\({}_{n}\mathrm{C}_{m}\) 通り







\((6)\)  \(1 \leq x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_m \leq n\)

\((5)\) の不等式に帰着させるように変形します。

例えば \(x_1 \leq x_2\) について、右辺に \(1\) を加えれば
等号が成り立つことは無いので \(x_1 \lt x_2+1\)

同様に \(x_2 \leq x_3\) は \(x_2 \lt x_3+1\)

    \(x_3 \leq x_4\) は \(x_3 \lt x_4+1\)

          \(\cdots \)

    \(x_{m-1} \leq x_m\) は \(x_{m-1} \lt x_m+1\)

これらの不等式を全て繋げると、元の不等式は$$1 \leq x_1 \lt x_2 +1 \lt x_3+2 \lt \cdots \lt x_{m-1}+(m-2) \lt x_m+(m-1) \leq n+m-1$$

これは \(1\) から \(n+m-1\) までの数字から \(m\) 個を選んで、小さい数字から

\(x_1,x_2+1,x_3+2, \cdots,x_m+(m-1)\) に割り当てれば良い。

          よって、解の個数は \({}_{n+m-1}\mathrm{C}_{m}={}_n\mathrm{H}_{m}\) 通り


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です