組み合わせ

1,2,3のカードがそれぞれa,b,c枚ずつ入っている場合、その横並びの総数は、
$_{a+b+c}C_a+_{b+c}C_b+_cC_{c}=\frac{(a+b+c)!}{a!b!c!}$

$_nC_r=_{n-1}C_{r-1}+_{n-1}C_r$

n個の中からr個取り出すと言うことは、
n個のうち、特定の一つを取り出した後その他のn-1個の中から2つを取り出す場合の数と、
特定の一つを除いたn-1個の中からr個取り出す場合の数の和である。
したがってこれが成り立つ。

$\sum_{k=r}^m _kC_r=_rC_r+\sum_{k=r+1}^m\left(_{k+1}C_{r+1}-_kC_{r+1}\right)=_{m+1}C_{r+1}$

x+y+z=k

x+y+z=k(x>0,y>0,z>0)となる整数x,y,zの組の数は、
k個の球を横に一列に並べ、
そのk-1個の隙間から2つを選んでポールを立てる動作と等しい。
故に、その場合の数は、
$_{k-1}C_{2}$

x+y+z=k(x≧0,y≧0,z≧0)となる整数x,y,zの組の数は、
k個の球と2つのポールを合わせたk+2個の物質が入る空間k+2個から、
ポールが入るべき2つの空間を選ぶ動作に等しい。
故に、その場合の数は、
$_{k+2}C_2$
また、x+y+z≦mとなる整数x,y,zの組の数は、
$\sum_{k=0}^m_{k+2}C_2=_{m+3}C_3$ 通り

文字の並び替え

ABCDEFGを並び替えた一列にCAFEがふくまれる場合の数は、
これは(CAFE)○○○と、CAFEという一文字と、残りの文字を全て○として考えられるから、
$\frac{4!}{3!}\cdot 3!=24$ 通り

AACCEEFを並び替えた一列にCAとFEがこの順で現れる場合の数は、
○○FE○○○,○○○FE○○,○○○○FE○,○○○○○FE　と考えられる。
ここで、この考え方をすると、○○...の中にCAが2つ並ぶものは重複することになるから、
これは具体的にはCACAFEE,CACAEFE,CAECAFE,ECACAFE の4つである。
したがって、
$1\cdot 3! + 2\cdot 3! + (3\cdot 3! - 1) + (4\cdot 3! - 3)=56$ 通り

間隔を保ちながら並べる場合の数

n個の空間が一列に並んでいるとする。
この空間にそれぞれが隣り合わないように2つの球を入れるとき、
その場合の数の総数を考える。

そこで、一つ目の球1を固定して考える。
今、「球1の入る空間の番号＜球2の入る空間の番号」とする。
空間1に球1を入れるとき、球2は(n-2)個の空間に入りうる。
空間2に球1を入れるとき、球2は(n-3)個の空間に入りうる。
...
空間kに球1を入れるとき、球2は(n-(k+1))個の空間に入りうる。
...
空間(n-2)に球1を入れるとき、球2は1個の空間に入りうる。

この試行結果から、
一列に並ぶn個の空間に二つの同一の球を入れる組み合わせの数 $a_2(n)$ は、
$a_2(n)=\sum_{k=1}^{n-2}k=\frac{(n-2)(n-1)}{2}$

同様に、 $a_3(n)$ も考える。
空間1に球1を入れると、空間3～空間nに2球が間隔を置いて入りうる。
空間2に球1を入れると、空間4～空間nに2球が間隔を置いて入りうる。
...
空間kに球1を入れると、空間(k+2)～空間nに2球が間隔を置いて入りうる。
...
空間(n-4)に球1を入れると、空間(n-2)～空間nに2球が間隔を置いて入りうる。

ところで、n-(k+2)+1=(n-(k+1))個の空間に2球を間隔を置いて入れる場合の数は、
$a_2(n-k-1)$ である。
よって、
$a_3(n)=\sum_{k=1}^{n-4}a_2(k)=\sum_{k=1}^{n-2}a_2(k)$
同様に帰納的に考えると、以下の漸化式が成り立つ。
$a_m(n)=\sum_{k=1}^{n-2}a_{m-1}(k)$

タグ：

+ タグ編集

「組み合わせ」をウィキ内検索

最終更新：2012年07月08日 23:17

ツールボックス

下から選んでください:

新しいページを作成する

ヘルプ / FAQ もご覧ください。

center_math @ ウィキ