SENSEI AI
About App

自然数 $n$ と0以上の整数 $x_1, x_2, ..., x_{2n}$ について、以下の条件を考える。 条件1: $\sum_{k=1}^n x_k \leq n$ 条件2: $\sum_{k=1}^{n+1} x_k \geq n+1$ 条件3: $\sum_{k=n+1}^{2n} x_k = 2n$ (1) $\sum_{k=1}^n x_k = m$ ( $m$ は0以上 $n$ 以下の整数) のとき、条件2かつ条件3を満たす0以上の整数の組 $(x_{n+1}, x_{n+2}, ..., x_{2n})$ の個数を $m, n$ で表せ。 (2) $1$以上 $n$ 以下の整数 $m$ に対して、$_{2n+m-2}C_{2n-2} = {}_{2n+m-1}C_{2n-1} + {}_{2n+m-2}C_{2n-1}$ を示せ。 (3) 条件1かつ条件2かつ条件3を満たす0以上の整数の組 $(x_1, x_2, ..., x_{2n})$ の個数を $n$ で表せ。

離散数学組み合わせ数列不等式数え上げ
2025/5/8

1. 問題の内容

自然数 nn と0以上の整数 x1,x2,...,x2nx_1, x_2, ..., x_{2n} について、以下の条件を考える。
条件1: ∑k=1nxk≤n\sum_{k=1}^n x_k \leq n
条件2: ∑k=1n+1xk≥n+1\sum_{k=1}^{n+1} x_k \geq n+1
条件3: ∑k=n+12nxk=2n\sum_{k=n+1}^{2n} x_k = 2n
(1) ∑k=1nxk=m\sum_{k=1}^n x_k = m ( mm は0以上 nn 以下の整数) のとき、条件2かつ条件3を満たす0以上の整数の組 (xn+1,xn+2,...,x2n)(x_{n+1}, x_{n+2}, ..., x_{2n}) の個数を m,nm, n で表せ。
(2) 11以上 nn 以下の整数 mm に対して、2n+m−2C2n−2=2n+m−1C2n−1+2n+m−2C2n−1_{2n+m-2}C_{2n-2} = {}_{2n+m-1}C_{2n-1} + {}_{2n+m-2}C_{2n-1} を示せ。
(3) 条件1かつ条件2かつ条件3を満たす0以上の整数の組 (x1,x2,...,x2n)(x_1, x_2, ..., x_{2n}) の個数を nn で表せ。

2. 解き方の手順

(1) ∑k=1nxk=m\sum_{k=1}^n x_k = m のとき、条件2は ∑k=1n+1xk≥n+1\sum_{k=1}^{n+1} x_k \geq n+1 となるので、xn+1≥n+1−mx_{n+1} \geq n+1 - m。
条件3は ∑k=n+12nxk=2n\sum_{k=n+1}^{2n} x_k = 2n。
xn+1=xn+1′+n+1−mx_{n+1} = x'_{n+1} + n+1-m (xn+1′x'_{n+1} は0以上の整数)とおくと、xn+1′+n+1−m+∑k=n+22nxk=2nx'_{n+1} + n+1-m + \sum_{k=n+2}^{2n} x_k = 2n。よって、∑k=n+22nxk+xn+1′=2n−(n+1−m)=n−1+m\sum_{k=n+2}^{2n} x_k + x'_{n+1} = 2n - (n+1-m) = n-1+m。
この方程式の0以上の整数解の個数は、nn 個の変数についての和が n−1+mn-1+m となる場合の数なので、(n−1+m)+(n−1)Cn−1=2n+m−2Cn−1{}^{(n-1+m) + (n-1)}C_{n-1} = {}^{2n+m-2}C_{n-1}。
(2) パスカルの公式 nCk=n−1Ck+n−1Ck−1{}_{n}C_{k} = {}_{n-1}C_{k} + {}_{n-1}C_{k-1} を用いる。
2n+m−2C2n−2=2n+m−3C2n−2+2n+m−3C2n−3{}_{2n+m-2}C_{2n-2} = {}_{2n+m-3}C_{2n-2} + {}_{2n+m-3}C_{2n-3}。
与えられた式 2n+m−2C2n−2=2n+m−1C2n−1−2n+m−2C2n−1{}_{2n+m-2}C_{2n-2} = {}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1} を示す。
右辺 =2n+m−1C2n−1−2n+m−2C2n−1= {}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1}
2n+m−1C2n−1=2n+m−2C2n−1+2n+m−2C2n−2{}_{2n+m-1}C_{2n-1} = {}_{2n+m-2}C_{2n-1} + {}_{2n+m-2}C_{2n-2}より、
2n+m−1C2n−1−2n+m−2C2n−1=2n+m−2C2n−2{}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1} = {}_{2n+m-2}C_{2n-2}。
よって、2n+m−2C2n−2=2n+m−1C2n−1−2n+m−2C2n−1{}_{2n+m-2}C_{2n-2} = {}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1} が示された。
(3) 条件1: ∑k=1nxk≤n\sum_{k=1}^n x_k \leq n
条件2: ∑k=1n+1xk≥n+1\sum_{k=1}^{n+1} x_k \geq n+1
条件3: ∑k=n+12nxk=2n\sum_{k=n+1}^{2n} x_k = 2n
条件1より∑k=1nxk=m\sum_{k=1}^n x_k = m (m=0,1,...,nm=0,1,...,n)とおく。条件1, 2, 3を同時に満たす整数の組の個数を求める。
mm を固定して、条件2, 3を満たす個数を求める。
∑k=1nxk=m\sum_{k=1}^n x_k = mのとき、(1)より条件2, 3を満たす個数は2n+m−2Cn−1{}^{2n+m-2}C_{n-1}。
よって、条件1, 2, 3を満たす整数の組の個数は、
∑m=0n2n+m−2Cn−1\sum_{m=0}^n {}^{2n+m-2}C_{n-1}となる。
ここで2n−2Cn−1+2n−1Cn−1+...+3n−2Cn−1=3n−1Cn{}_{2n-2}C_{n-1} + {}_{2n-1}C_{n-1} + ... + {}_{3n-2}C_{n-1} = {}_{3n-1}C_n
${}_{2n-2}C_{n-1} = {}_{2n-1}C_{n}
n=3n−1Cn−1n = {}_{3n-1}C_{n-1}を用いる。
よって、答えは3n−1Cn{}_{3n-1}C_{n}

3. 最終的な答え

(1) 2n+m−2Cn−1{}^{2n+m-2}C_{n-1}
(2) 2n+m−2C2n−2=2n+m−1C2n−1−2n+m−2C2n−1{}_{2n+m-2}C_{2n-2} = {}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1} (証明終わり)
(3) 3n−1Cn{}_{3n-1}C_n

「離散数学」の関連問題

"baseball"という単語の8個の文字全てを使ってできる文字列の総数を求める問題です。

順列組み合わせ文字列階乗重複順列
2025/6/9

7個の文字 a, a, a, b, b, c, c をすべて使ってできる文字列の総数を求める問題です。

順列組み合わせ重複順列
2025/6/9

赤玉2個、白玉2個、青玉2個を1列に並べる並べ方の総数を求める問題です。

順列組み合わせ場合の数重複順列
2025/6/9

A地点からB地点まで、図に示された経路を最短距離で移動する方法が何通りあるかを求める問題です。図は4x3の格子状の道で、A地点は左上、B地点は右下に位置しています。

組み合わせ最短経路二項係数格子状の道
2025/6/9

A地点からB地点を経由してC地点まで、最短距離で行く道順が何通りあるかを求める問題です。

組み合わせ最短経路場合の数
2025/6/9

問題は、6個の文字 a, a, b, c, c, c をすべて使ってできる文字列が何通りあるかを求める問題です。

順列組み合わせ場合の数重複順列
2025/6/9

"fifteen" という単語の7個の文字すべてを使ってできる文字列は何通りあるかを求める問題です。

順列組み合わせ文字列重複順列
2025/6/9

全体集合 $U = \{x \mid x \text{ は10以下の自然数} \}$ が与えられ、その部分集合として $A = \{1, 2, 3, 4, 8\}$, $B = \{3, 4, 5, ...

集合集合演算
2025/6/9

全体集合$U$の部分集合$A, B$について、$n(U)=100, n(A)=36, n(B)=42, n(A \cap B)=15$であるとき、次の個数を求めよ。 (1) $n(\overline{...

集合集合演算ド・モルガンの法則要素数
2025/6/9

A, B, Cの3種類の商品を合わせて12個買うとき、以下の問いに答えよ。 (1) 買わない商品があってもよい場合の買い方は何通りあるか。 (2) どの商品も少なくとも1個買う場合の買い方は何通りある...

組み合わせ重複組み合わせ場合の数
2025/6/9