与えられた自然数 ｎ に対して、０ から ｎ までの整数の中からいくつか選んで大きさの順
番に並べるということはとても素朴な行為である。このページでは、選ばれる整数に幾つか
条件を指定して、その選び方が何通りあるかを考えていこうと思う。
問 ０＜ａ＜ｂ＜ｃ＜ｄ＜ｅ＜ｎ を満たす整数の組 （ ａ ， ｂ ， ｃ ， ｄ ， ｅ ） は何通りあるか。
（解） １ から ｎ−１ までの ｎ−１ 個の整数から５個とる組合せの数に等しいので、
求める場合の数は、 ｎ-1Ｃ5 通りある。 （終）
問 ０≦ａ≦ｂ≦ｃ≦ｄ≦ｅ≦ｎ を満たす整数の組 （ ａ ， ｂ ， ｃ ， ｄ ， ｅ ） は何通りあるか。
（解） ０ から ｎ までの ｎ＋１ 個の整数から重複を許して５個とる組合せの数に等しいので、
求める場合の数は、 ｎ+1Ｈ5＝ｎ+5Ｃ5 通りある。 （終）
上記の解では、重複組合せの考えを用いたが、次のように考えることもできる。
（別解） 求める整数の組 （ ａ ， ｂ ， ｃ ， ｄ ， ｅ ） に対して、整数の組
（ ａ＋１ ， ｂ＋２ ， ｃ＋３ ， ｄ＋４ ， ｅ＋５ ）
が１対１に対応し、 １≦ａ＋１＜ｂ＋２＜ｃ＋３＜ｄ＋４＜ｅ＋５≦ｎ＋５ を満たす。
よって、求める場合の数は、１ から ｎ＋５ までの ｎ＋５ 個の整数から５個とる組合
せの数に等しいので、ｎ+5Ｃ5 通りある。 （終）
（コメント） 各項にそれぞれ １〜５ を加えて、等しくなりうる可能性を回避している点に感
動しました。
上記別解のアイデアは、次のような問題にも応用される。
問 １ から ｎ までの ｎ 個の整数から、異なる ｋ 個の整数をとり、大きさの順に並べる。
このとき、どの２つの整数も隣り合うことのない ｋ 個の整数の組
（ ａ1 ， ａ2 ， ａ3 ， ・・・ ， ａk ） （ただし、 ａ1＜ ａ2＜ ａ3＜ ・・・＜ ａk）
は、何通りあるか。
（このような整数の組（ ａ1 ， ａ2 ， ａ3 ， ・・・ ， ａk ） は、非友好的と言われる。）
例 １ から ５ までの５個の整数から非友好的な２個の整数の組を作ると、
（ １ ， ３ ）、（ １ ， ４ ）、（ １ ， ５ ）、（ ２ ， ４ ）、（ ２ ， ５ ）、（ ３ ， ５ ）
の６組ある。
２番目の数から全て１引くと、
（ １ ， ２ ）、（ １ ， ３ ）、（ １ ， ４ ）、（ ２ ， ３ ）、（ ２ ， ４ ）、（ ３ ， ４ ）
これは、１ から ４ までの４個の整数から異なる２個を取る組合せに一致し、求める場
合の数は、 4Ｃ2＝６ （通り） となる。この結果は、上記と一致する。
例 １ から ６ までの６個の整数から非友好的な３個の整数の組を作ると、
（ １ ， ３ ， ５ ）、（ １ ， ３ ， ６ ）、（ １ ， ４ ， ６ ）、（ ２ ， ４ ， ６ ）
の４組ある。
２番目の数から全て１を引き、さらに、３番目の数から全て２を引くと、
（ １ ，２ ， ３ ）、（ １ ， ２ ， ４ ）、（ １ ， ３ ， ４ ）、（ ２ ， ３ ， ４ ）
これは、１ から ４ までの４個の整数から異なる３個を取る組合せに一致し、求める場
合の数は、 4Ｃ3＝４ （通り） となる。この結果は、上記と一致する。
この例におけるアイデアを用いて、問は解かれる。
（解） 求める整数の組 （ ａ1 ， ａ2 ， ａ3 ， ・・・ ， ａk ） に対して、整数の組
（ ａ1 ， ａ2−１ ， ａ3−２ ， ・・・ ， ａk−ｋ＋１ ）
が１対１に対応し、
１≦ａ1＜ ａ2−１＜ ａ3−２ ＜ ・・・ ＜ ａk−ｋ＋１≦ｎ−ｋ＋１
を満たす。
よって、求める場合の数は、１ から ｎ−ｋ＋１ までの ｎ−ｋ＋１ 個の整数から異なる ｋ
個をとる組合せの数に等しいので、ｎ-ｋ+1Ｃk 通りある。 （終）
以下、工事中