集団を含んだ順列

男が四人, 女が五人いる。
この九人を一列に並べることを考える。
この時, 男三人 (だけ) が連続して並ぶ場合の数を求めよ。
(1) □女□女□女□女□女□
と並べることを考える。 □のところには, 男が三人入るか, 一人だけが入るかということになる。
女五人の並びは 5!
男三人と残りの一人をどこに入れるか, というのが ₆P₂
その男三人の並び 4!
ということになるので, 結局
5!×₆P₂×4! = 86400.

(2) 男が三人一塊になっているのを都合一人と考えて一列に並べると 7!
その一塊になっている三人の並びが 4!
しかしこれでは数え過ぎである。 つまり三人と一人を並べたときに, そこがくっついてしまって余人一塊になってしまっている場合を引かなければならない。
つまり 6!×4!
これだけでは足りなくて, 実は四人が一塊になってしまっているときには例えば
A; B, C, D (一人 + 三人) と
A, B, C; D (三人 + 一人) が違う場合に数えられてしまっているので, 上記の二倍つまり
6!×4!×2
を引かなければならない。
結局
7!×4! - 6!×4!×2 = 120960 - 34560 = 86400.

---

僕は順列組み合わせが不得意な上に, そそっかしいので, (2) の解答をしたときに, 二倍するのを忘れてしまって間違えたのである。
丁寧に貝解説してくださった相川祐太教諭に感謝する。

組み合わせ・重複組み合わせ

四つの整数 a, b, c, d は 0 から 9 までのどれかの数を表しているとする。
次のようになる場合の数を求めよ。
(1) a ₁₀C₄ = 10・9・8・7/(4・3・2・1) = 210 [通り]
(2) = の数が 0 の場合は (1). = の数が 1 の場合は, = がどこに入るのかも考えると
₁₀C₃・₃C₁ = 360.
= の数が 2 の場合も
₁₀C₂・₃C₂ = 135.
= の数が 3 即ち, すべて等しい場合は 10 通りだから全部合わせて
210 + 360 + 135 + 10 = 715 [通り]
[別解]
問題の条件を満たすとき (a, b, c, d) の組を (x, y, z, w, u) = (a, b - a, c - b, d - c, 9 - d) に変換すると, x + y + z + w + u = 9 であり, x, y, z, w は 0 から 9 までの整数となる。
このようにした時, この (x, y, z, w, u) の個数は, 9 を (0 であることを許して) 五つに分配するときの場合の数を数えることとなり, それは九つの○と四つの区切り線を並べる場合の数と同一となる。
つまり例えば (a, b, c, d) = (1, 1, 1, 3) は (x, y, z, w, u) = (1, 0, 0, 2, 6) に変換され, それは
○|||○○|○○○○○○ と同一視される。
即ち, 求める数は ₁₃C₄ = 715 [通り]

---

生徒から聞いた問題である。

並び方指定のある順列

質問 <3801> 2010/8/22 from = confuse

並び方指定のある順列でどう考えたらいいか悩んでいます。 考え方の指導と解答をお願いします。
1, 2, 3, 4, 5, 6, 7 の七個の数字を横一列に並べるとき 1 が 3 よりも右にあるものの並び方は何通りありますか。
　これは 4, 2 を一つの塊として考えれば良いのでしょうか?

---

解答:
[基本的方針]
並び方の指定のあるものは, 全て同じもの (例えば □) と考えて一列に並べ, 後から指定された順序に入れる。

つまり, 今の問題だと □, 2, □, 4, 5, 6, 7 を一列に並べる。
例えば 7, 5, □, 4, 2, □, 6 となったとする。
そしたら, 1 が 3 より右と指定されているので, 左から 3, 1 と入れて 7, 5, 3, 4, 2, 1, 6 とすれば指定通りになる。

というわけなので, 答は 7!/2! = 2520 [通り]

数列

QNo.6118275 bellechap

数列の問題で質問です。 現在, 学校では漸化式まで習っています。 数学的帰納法は二学期に習います。
夏休みの宿題で, どうしてもわからないものが一題あります。 教えて頂けないでしょうか。

f(x) = (x + 1)(x + 2)(x + 3)……………………(x + n) を展開したときの x^k の係数を a_k とする。
(1) a_{n - 1} を求めよ。
(2) a_{n - 2} を求めよ。
(3) a₀ + a₁ + a₂ + a₃ + ………… + a_n を求めよ。

投稿日時 - 2010-08-18 15:59:21

---

解答:
ANo.1 naniwacchi

こんにちわ。

この問題, 漸化式も帰納法も使わないのですが, 少々ヘビー級な問題です。＾＾
ヘビーというのは 「計算量」 です。
このような展開係数については, 場合の数 (組合せ) の問題でも出てきますね。

(1) は a(n-1) = x^(n-1) の係数を求めなさい。 ということになりますが,
「どれか 1 つの (…) から定数項を選んで, 残りの (…) からは x を選ぶ」
と x^(n-1) の項ができあがります。

定数項を選ぶ選び方が何通りあるかはわかりますよね。
それらを足し合わせると a(n-1) になります。

(2) も同様です。 が, 非常にヘビーです。
計算方法としては, 「ダブルで Σ」 を使います。
添付に計算のはじめだけを書いておきます。
一度, よーく考えてみてください。

a_{n - 2}
= 1・2 + 1・3 + 1・4 + …… + 1・(n - 1) + 1・n
　　　　+ 2・3 + 2・4 + …… + 2・(n - 1) + 2・n
　　　　　　 　+ 3・4 + …… + 3・(n - 1) + 3・n
　　　　　　　　　+ ………………………… +
　　　　　　　　　　　　　　　+ (n - 2)(n - 1) + (n - 2)n
　　　　　　　　　　　　　　　　　　　　　　　　+ (n - 1)n

(3) これとんでもない問題に見えると思います。
でも, 一番これが簡単だったりします。 というか, わかると秒殺なんです。＾＾
ヒント: なんでわざわざ 「f(x)」 って書いてるんでしょうね。
そして, f(x) を書き下すと f(x) = Σ[k=0~n] a(k)* x^k となりますよね。

投稿日時 - 2010-08-18 17:07:10

ANo.3 nag0720
(2) は#1さんの回答のとおり、
a[n-2]=1*2+1*3+1*4+……+1*n
　　　+2*3+2*4+2*5+……+2*n
　　　+3*4+3*5+3*6+……+3*n
　　　+…………+
　　　+(n-3)(n-2)+(n-3)(n-1)+(n-3)*n
　　　+(n-2)(n-1)+(n-2)*n
　　　+(n-1)*n

ですが, これをそのまま計算しようとすると大変です。
(1+2+3+……+n)(1+2+3+……+n)
=1*1+1*2+1*3+1*4+……+1*n
+2*1+2*2+2*3+2*4+……+2*n
+3*1+3*2+3*3+3*4+……+3*n
+…………+
+(n-2)*1+(n-2)*2+……+(n-2)*n
+(n-1)*1+(n-1)*2+……+(n-1)*n
+n*1+n*2+……+n*n

を利用すれば、

(1+2+3+……+n)(1+2+3+……+n) = a[n-2]*2 + (1*1+2*2+3*3+……+n*n)

の関係式から a[n-2] を求めることができます。

投稿日時 - 2010-08-18 20:00:06

---

(1) a_{n - 1}
= 　2 + 3 + 4 + …… + (n - 1) + n
+1 　 + 3 + 4 + …… + (n - 1) + n
+ 1 + 2 　 + 4 + …… + (n - 1) + n
+ …… +
+ 1 + 2 + 3 + 4 + …… 　　　　 + n
+ 1 + 2 + 3 + 4 + …… + (n - 1)
= (n - 1)(1 + 2 + 3 + … + n)
= (n - 1)n(n + 1)/2

(2) a_{n - 2}
= (1/2)((Σ_k=1ⁿ k)² -Σ_k=1ⁿ k²)
= (1/2)((n(n + 1)/2)² - n(n + 1)(2n + 1)/6)
= (1/24)n(n + 1)(3n(n + 1) - 4(2n + 1))
= (1/24)n(n + 1)(3n² - 5n - 4)

(3) 与式 = f(1) = (n + 1)!

等式の証明

等式の証明
ba3516
ランダムウォークについて、色々計算しているんですけど、その過程でこういう等式がでてきたんですが
Σ_k=0ⁿ _nC_k(n - 2k)² = n・2ⁿ (n ≧ 1)
これを証明する手立てがありません。
どなたかご教授お願いします

---

証明:
左辺を展開すると
lhs = n²Σ_k=0ⁿ_nC_k - 4nΣ_k=0ⁿ k_nC_k + 4Σ_k=0ⁿ k²_nC_k …… (0)
である。
そこで二項定理より
(x + y)ⁿ = Σ_k=0ⁿ_nC_k x^ky^n-k …… (1)
を用いる。
先ず (1) に x = y = 1 を代入することにより (良く知られているように)
2ⁿ = Σ_k=0ⁿ_nC_k …… (2)
を得る。
次に (1) の両辺を x で微分すると
n(x + y)^n-1 = Σ_k=0ⁿ k_nC_k x^k-1y^n-k
で, これに再び x = y = 1 を代入することにより
n・2^n-1 = Σ_k=0ⁿ k_nC_k …… (3)
を得る。
更に (1) の両辺を x で微分すると
n(n - 1)(x + y)^n-2 = Σ_k=0ⁿ k(k - 1)_nC_k x^k-2y^n-k
これに又 x = y = 1 を代入することにより
n(n - 1)・2^n-2 = Σ_k=0ⁿ k(k - 1)_nC_k
=Σ_k=0ⁿ k²_nC_k -Σ_k=0ⁿ k_nC_k
つまり (3) と合わせて
Σ_k=0ⁿ k²_nC_k = n(n + 1)・2^n-2 …… (4)
を得る。
以上を合わせて
(0) の右辺
= n²・2ⁿ - 4n²・2^n-1 + 4n(n + 1)・2^n-2
= n²・2ⁿ - 2n²・2ⁿ + n(n + 1)・2ⁿ
= (n² - 2n² + n(n + 1))・2ⁿ
= n・2ⁿ.