差が 2 以上ある数はどう選ぶ？条件は置きかえで消せる

$1$ から $20$ までの数から 4 個を選び、どの 2 つも差が 3 以上になるようにします。答えは 1001 通り。

差の条件も、大小の条件も、置きかえてしまえば消えます。残るのはただの組合せです。

大小の条件は数えなくてよい

まず易しいほうから。$1$ から $9$ までの数から 3 個を選び、小さい順に $a<b<c$ と並べます。

選んだ 3 個を小さい順に並べる方法は 1 通りしかありません。だから、並べ方を掛ける必要がない。

$${}_9{\mathrm{C}}_3=84$$

84 通りです。「$a<b<c$ を満たす組はいくつか」と聞かれたら、それは「3 個選べ」と同じ意味になります。

3 個を選んで並べる ${}_9{\mathrm{P}}_3=504$ 通りのうち、大小の順が正しいのは 6 分の 1。$504÷6=84$ でも同じ値です。

例：各位が増える 3 桁の整数

$137$ や $258$ のように、上の位から下へ数字が大きくなる 3 桁の整数を数えます。

使える数字は $1$ から $9$。0 は入りません。0 を含むと、0 より小さい数字が下の位に来られないためです。

3 個を選べば並べ方が 1 通りに決まるので ${}_9{\mathrm{C}}_3=84$ 個。

例：各位が減る 3 桁の整数

$731$ や $940$ のように、上から下へ小さくなる整数なら 0 も使えます。0 は必ず一の位に来る。

$0$ から $9$ までの 10 個から 3 個を選んで ${}_{10}{\mathrm{C}}_3=120$ 個です。

先頭が 0 になる心配もありません。いちばん大きい数字が百の位に来るので、0 が先頭に立つことはない。

例：同じ数字を許す場合

$113$ や $455$ のように、等号を含めて増える整数を数えます。同じ数字が並んでもよい形です。

$1$ から $9$ までの 9 種類から、重複を許して 3 個を選ぶ。並べ方はやはり 1 通りに決まります。

$${}_9{\mathrm{H}}_3={}_{11}{\mathrm{C}}_3=165$$

165 個。等号を許すかどうかで、組合せから重複組合せに変わります。

差の条件は間隔を詰めて消す

ここからが本題です。$1$ から $20$ までから 4 個を選び、どの 2 つも差が 3 以上とする。

選んだ数を小さい順に $a_1<a_2<a_3<a_4$ とします。条件は、隣り合う 2 数の差が 3 以上ということ。

次のように置きかえます。

$$b_1=a_1,b_2=a_2-2,b_3=a_3-4,b_4=a_4-6$$

差が 3 以上あったところから、余分な 2 ずつを抜いています。すると $b$ どうしは差が 1 以上、つまりただの大小関係になる。

置きかえたあとの範囲

$b_4=a_4-6$ で、$a_4$ は最大 20 なので $b_4$ は最大 14。$b_1$ は最小 1 のままです。

つまり $b$ たちは $1$ から $14$ までの相異なる 4 個。もとの条件を満たす組と 1 対 1 に対応します。

$${}_{14}{\mathrm{C}}_4=1001$$

1001 通りです。差の条件は、選ぶ範囲を狭めることに置きかわりました。

一般の形

$1$ から $n$ までから $k$ 個を選び、どの 2 つも差が $d$ 以上とします。

隣り合う組が $k-1$ 組あり、それぞれ $d-1$ ずつ余分に空いている。合わせて $(k-1)(d-1)$ を範囲から抜きます。

$${}_{n-(k-1)(d-1)}{\mathrm{C}}_k$$

$d=2$ なら ${}_{n-k+1}{\mathrm{C}}_k$ で、連続しない選び方の式になります。差が 1 以上、つまり $d=1$ ならただの ${}_n{\mathrm{C}}_k$。

例：差が 4 以上

$1$ から $15$ までから 3 個を選び、どの 2 つも差が 4 以上とします。

$(k-1)(d-1)=2\times 3=6$ なので、範囲は $15-6=9$ に狭まります。

$${}_9{\mathrm{C}}_3=84$$

84 通りです。制限なしの ${}_{15}{\mathrm{C}}_3=455$ から大きく減っている。

小さい場合で確かめる

$1$ から $6$ までから 2 個を選び、差が 3 以上とします。式では ${}_{6-3}{\mathrm{C}}_2={}_3{\mathrm{C}}_2=3$ 通り。

書き出すと $\{1,4\}$、$\{1,5\}$、$\{1,6\}$、$\{2,5\}$、$\{2,6\}$、$\{3,6\}$ の 6 通り。合いません。

式を見直します。$(k-1)(d-1)=1\times 2=2$ なので範囲は $6-2=4$ で、${}_4{\mathrm{C}}_2=6$ 通り。今度は合いました。

$d-1$ ではなく $d$ を引いていました。ここが誤りです。小さい場合の書き出しが、こういうとり違えを拾ってくれます。

大小関係が一直線でない場合

$a<b>c$ のように、山の形をした条件もあります。真ん中がいちばん大きい。

$1$ から $5$ までから 3 個の相異なる数を選び、この形に並べます。

3 個を選ぶと ${}_5{\mathrm{C}}_3=10$ 通り。そのうち最大の数を真ん中に置き、残る 2 個を左右に振り分ける。

左右の振り分けが 2 通りなので $10\times 2=20$ 通りです。

例：谷の形

$a>b<c$ なら、真ん中がいちばん小さい形です。数え方は山と同じ。

3 個を選び、最小の数を真ん中に置き、残る 2 個を左右に振り分ける。$10\times 2=20$ 通り。

山と谷を合わせると 40 通り。全体 ${}_5{\mathrm{P}}_3=60$ 通りのうち、残る 20 通りが $a<b<c$ と $a>b>c$ の単調な形にあたります。

差の条件と大小の条件が混ざる場合

$1$ から $12$ までから 3 個を選び、どの 2 つも差が 2 以上で、しかも最小の数が 3 以上とします。

まず下限をそろえます。$3$ から $12$ までの 10 個が対象。

そこから差が 2 以上で 3 個を選ぶので、$(k-1)(d-1)=2\times 1=2$ を引いて範囲は 8。

$${}_8{\mathrm{C}}_3=56$$

56 通りです。下限は範囲を切り、差の条件は範囲を詰める。どちらも置きかえで消えます。

例：くじ引きの番号

$1$ から $30$ までの番号札から 5 枚を引きます。どの 2 枚も番号が 5 以上離れているとする。

$(5-1)(5-1)=16$ を引いて範囲は $30-16=14$。

$${}_{14}{\mathrm{C}}_5=2002$$

2002 通り。範囲が半分以下に縮んでも、選び方はまだ多く残ります。

よくある誤り

差も大小も、置きかえて消してしまう。残った形がただの組合せになれば、そこで手は止まります。

参考文献

^[1] が組合せと重複組合せ、^[2] が連続しない選び方の公式、^[3] が置きかえで条件を消す考え方、^[4] と ^[5] が各国語での整理です。