当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。（平成２１年１０月５日）
３人（Ａ、Ｂ、Ｃ)の客がツアー旅行を希望している。旅行会社は次の企画が可能である。
１． Ａ、Ｂ、Ｃで一緒に行く。
２． Ａ、Ｂで第１陣、Ｃだけで第２陣
３． Ｂ、Ｃで第１陣、Ａだけで第２陣
４． Ｃ、Ａで第１陣、Ｂだけで第２陣
５． Ａで第１陣、Ｂ、Ｃで第２陣
６． Ｂで第１陣、Ｃ、Ａで第２陣
７． Ｃで第１陣、Ａ、Ｂで第２陣
８． Ａで第１陣、Ｂで第２陣、Ｃで第３陣
９． Ａで第１陣、Ｃで第２陣、Ｂで第３陣
１０． Ｂで第１陣、Ａで第２陣、Ｃで第３陣
１１． Ｂで第１陣、Ｃで第２陣、Ａで第３陣
１２． Ｃで第１陣、Ａで第２陣、Ｂで第３陣
１３． Ｃで第１陣、Ｂで第２陣、Ａで第３陣
以上の１３通りの可能性が生まれる。
では、４人の客が現れたら何通りが考えられるだろうか？
一般に、ｎ 人の客ならどうなるでしょう？
（答） 順列組合せの手頃な問題ですね！また、自然数をいくつかの和に分解する問題とも
関係がありそう．．．。
３人の場合は、 ３＝２＋１＝１＋２＝１＋１＋１ に注意して、
求める場合の数は、 3Ｃ3＋3Ｃ2・1Ｃ1＋3Ｃ1・2Ｃ2＋3Ｃ1・2Ｃ1・1Ｃ1＝１３（通り）
４人の場合は、
４＝３＋１＝２＋２＝２＋１＋１＝１＋３＝１＋２＋１＝１＋１＋２＝１＋１＋１＋１
に注意して、
4Ｃ4＋4Ｃ3・1Ｃ1＋4Ｃ2・2Ｃ2＋4Ｃ2・2Ｃ1・1Ｃ1＋4Ｃ1・3Ｃ3
＋4Ｃ1・3Ｃ2・1Ｃ1＋4Ｃ1・3Ｃ1・2Ｃ2＋4Ｃ1・3Ｃ1・2Ｃ1・1Ｃ1
＝１＋４＋６＋１２＋４＋１２＋１２＋２４＝７５（通り）
（追記） 平成２１年１１月２４日付け
上記の計算で、３は４通りの自然数の和（和の順番も考慮）に、４は８通りの自然数
の和（和の順番も考慮）に分解されている。
一般に次の公式が知られている。
自然数 ｎ をいくつかの自然数の和（和の順番も考慮）に分解する方法の数は、
２ｎ-1 通り
である。この公式は、次の事実を用いる。
自然数 ｎ を ｍ 個の自然数の和（和の順番も考慮）に分解する方法の数は、
ｎ-1Ｃｍ-1 通り （ただし、 ｍ≦ｎ ）
この証明は易しい。
（証明） ｎ＝１＋１＋１＋・・・・・・＋１ と分解すると、ｎ−１個の「＋」がある。
この中から、ｍ−１個の「＋」を取る組合せの数が求める場合の数である。
（証終）
したがって、 ｎ-1Ｃ0＋ｎ-1Ｃ1＋ｎ-1Ｃ2＋・・・＋ｎ-1Ｃｎ-1＝２ｎ-1 が成り立つ。
さて、上記の計算は、重複順列の考えを用いても出来る。
ｎ 人を番号のついた ｋ 個の部屋に振り分ける方法の数は、 ｋｎ 通りある。ただし、この
方法の数の中にはどこかの部屋が空室の場合も含まれることに注意する。
３人を空室がないようにいくつかの部屋に振り分ける場合の計算
３人を１個の部屋に振り分ける方法の数は、 １3＝１ 通り
３人を２個の部屋に振り分ける方法の数は、 ２3−２＝６ 通り
３人を３個の部屋に振り分ける方法の数は、 ３3−３−３（２3−２）＝６ 通り
（２個の部屋が空室になる場合が 3Ｃ2 通り、１個の部屋のみが空室になる場合が
3Ｃ1・（２3−２）通り。これらを起こりうる全ての場合 ３3 通りから引けばよい。）
以上から、空室がないように、３人をいくつかの部屋に振り分ける方法の数は、
１＋６＋６＝１３（通り）
４人を空室がないようにいくつかの部屋に振り分ける場合の計算
４人を１個の部屋に振り分ける方法の数は、 １4＝１ 通り
４人を２個の部屋に振り分ける方法の数は、 ２4−２＝１４ 通り
４人を３個の部屋に振り分ける方法の数は、 ３4−３−３（２4−２）＝３６ 通り
（２個の部屋が空室になる場合が 3Ｃ2 通り、１個の部屋のみが空室になる場合が
3Ｃ1・（２4−２）通り。これらを起こりうる全ての場合 ３4 通りから引けばよい。）
４人を４個の部屋に振り分ける方法の数は、
４4−４−６（２4−２）−４｛３4−３−３（２4−２）｝＝２４ 通り
（３個の部屋が空室になる場合が 4Ｃ3 通り、２個の部屋のみが空室になる場合が
4Ｃ2・（２4−２）通り。１個の部屋のみが空室になる場合が
4Ｃ1・｛３4−３−３（２4−２）｝通り。これらを起こりうる全ての場合 ４4 通りから引け
ばよい。）
以上から、空室がないように、４人をいくつかの部屋に振り分ける方法の数は、
１＋１４＋３６＋２４＝７５（通り）
上記の計算を振り返ると、次のように機械的に計算できることが分かる。
５人を空室がないようにいくつかの部屋に振り分ける場合の計算
５人を１個の部屋に振り分ける方法の数は、 １5＝１ 通り
５人を２個の部屋に振り分ける方法の数は、 ２5−２＝３０ 通り
５人を３個の部屋に振り分ける方法の数は、 ３5−3Ｃ2−3Ｃ1・３０＝１５０ 通り
５人を４個の部屋に振り分ける方法の数は、
４5−4Ｃ3−4Ｃ2・３０−4Ｃ1・１５０＝２４０ 通り
５人を５個の部屋に振り分ける方法の数は、
５5−5Ｃ4−5Ｃ3・３０−5Ｃ2・１５０−5Ｃ1・２４０＝１２０ 通り
以上から、空室がないように、５人をいくつかの部屋に振り分ける方法の数は、
１＋３０＋１５０＋２４０＋１２０＝５４１（通り）
（コメント） Ｅｘｃｅｌ さんにお願いすれば、瞬時に求める場合の数が得られますね！
これまでの計算をまとめると、次のような数列が得られる。
１ ， ３ ， １３ ， ７５ ， ５４１ ， ・・・・・
ＧＡＩ さんによれば、次のような算出方法があるらしい。（平成２１年１０月１９日付け）
１．まずパスカルの三角形から、右端の １ は取り除く。
２．左端から右に偶数番目の数に、−をつける。
３．各段目の左端から右斜め下に順々に表示されている数字をすべて加える。
４．この合計段の数の左から順に、 ４4、３4、２4、１4 を掛け、すべてを加える。
すなわち
よって、 ２５６−２４３＋６４−２＝７５（通り）
（コメント） 組合せの計算は結構気を使いますが、これだと機械的にどんどん算出できそう
ですね！ただ、ＧＡＩ さんによれば、その算出の根拠が未だ不明とのこと。研究し
てみる価値がありそう．．．。
重複順列の考え方を用いた先の計算で、
３人を空室がないようにいくつかの部屋に振り分ける場合の計算
１3＋２3−2Ｃ1＋３3−3Ｃ1・２3＋3Ｃ1＝３3・１＋２3（１−3Ｃ1）＋１−2Ｃ1＋3Ｃ1
４人を空室がないようにいくつかの部屋に振り分ける場合の計算
１4＋２4−2Ｃ1＋３4−3Ｃ1・２4＋3Ｃ1＋４4−4Ｃ3＋4Ｃ2（２4−２）−4Ｃ1・（３4−３）
＝４4・１＋３4（１−4Ｃ1）＋２4（１−3Ｃ1＋4Ｃ2）＋１−2Ｃ1＋3Ｃ2−4Ｃ3
と式変形してみると、ＧＡＩ さんによる算出方法のカラクリが見えてくる。
ＧＡＩ さんの算出方法について、平成２１年１０月２１日付けで、ＨＮ「ａｔ」さんより、ご教示い
ただいた。（一部文言等を修正・加筆させていただきました。）
ｎ 人の客のツアー旅行計画の総数を、ａ（ｎ） とする。また、１≦ｋ≦ｎ に対して、ｎ 人を異
なる ｋ 個の部屋にどの部屋も空でないように分配する方法の総数を、ｂ（ ｎ ， ｋ ） とする。
このとき、明らかに、 ａ（ｎ）＝Σ[ ｋ＝１，ｎ] ｂ（ ｎ ， ｋ ） である。
例 ｂ（ ２ ， １ ）＝１ 、 ｂ（ ２ ， ２ ）＝２ より、 ａ（２）＝３
ｂ（ ３ ， １ ）＝１ 、 ｂ（ ３ ， ２ ）＝６ 、 ｂ（ ３ ，３ ）＝６ より、 ａ（３）＝１３
この ｂ（ ｎ ， ｋ ） について、次の漸化式が成り立つことは明らかだろう。
ｂ（ ｎ＋１ ， ｋ ）＝ｋ・ｂ（ ｎ ， ｋ−１ ）＋ｋ・ｂ（ ｎ ， ｋ ）
ただし、 ｂ（ ｎ ， １ ）＝１ 、 ｂ（ ｎ ， ｎ＋１ ）＝０
実際に、ｂ（ ｎ＋１ ， ｋ ） は、ｎ＋１ 人を異なる ｋ 個の部屋にどの部屋も空でないように
分配する方法の総数であるが、ある特定な人、例えば、ｎ＋１ 人目の人について、
一人部屋の場合 または 複数部屋の場合
の２つの場合に分けられる。
前者の場合は、まず、ｎ＋１ 人目の人がどの部屋に入るかで、ｋ 通りあり、その １
通りに対して、残り ｎ 人を ｋ−１ 個の部屋にどの部屋も空でないように分配する方
法の数は、ｂ（ ｎ ， ｋ−１ ） 通りなので、合わせて、 ｋ・ｂ（ ｎ ， ｋ−１ ） 通りとなる。
後者の場合は、ｎ＋１ 人目の人がどの部屋に入るかで、ｋ 通りあり、その １ 通り
に対して、残り ｎ 人を ｋ 個の部屋にどの部屋も空でないように分配する方法の数
は、ｂ（ ｎ ， ｋ ） 通りなので、合わせて、 ｋ・ｂ（ ｎ ， ｋ ） 通りとなる。
よって、 ｂ（ ｎ＋１ ， ｋ ）＝ｋ・ｂ（ ｎ ， ｋ−１ ）＋ｋ・ｂ（ ｎ ， ｋ ） が成り立つ。
例 ｂ（ ２ ， １ ）＝１ で、 ｂ（ ２ ， ２ ）＝２・ｂ（ １ ， １ ）＋２・ｂ（ １ ， ２ ）＝２
ｂ（ ３ ， １ ）＝１ で、 ｂ（ ３ ， ２ ）＝２・ｂ（ ２ ， １ ）＋２・ｂ（ ２ ， ２ ）＝６
ｂ（ ３ ，３ ）＝３・ｂ（ ２ ， ２ ）＋３・ｂ（ ２ ， ３ ）＝６
さて、包含と排除の原理から直ちに、（ただし、二項係数 ｋＣｊ ＝Ｃ（ ｋ ，ｊ ） とする。）
ｂ（ ｎ ， ｋ ）＝ｋｎ−Ｃ（ ｋ ，１ ）（ｋ−１）ｎ＋Ｃ（ ｋ ，２ ）（ｋ−２）ｎ−・・・
＋（−１）ｋ-1Ｃ（ ｋ ，ｋ−１ ）（１）ｎ
＝Σ[ ｊ＝０ ，ｋ−１] Ｃ（ ｋ ，ｊ ）・（−１）ｊ・（ｋ−ｊ）ｎ
＝Σ[ ｍ＝１ ，ｋ] Ｃ（ ｋ ，ｋ−ｍ ）・（−１）ｋ-ｍ・ｍｎ
＝Σ[ ｊ＝１ ，ｋ] （−１）ｋ−ｊ・Ｃ（ ｋ ，ｋ−ｊ ）・ｊｎ
が分かるので、
ａ（ｎ）＝Σｂ（ ｎ ， ｋ ）
＝Σ[ ｋ＝１，ｎ]Σ[ ｊ＝１，ｋ]（−１）ｋ−ｊ・Ｃ（ ｋ ，ｋ−ｊ ）・ｊｎ
＝Σ[ ｊ＝１，ｎ]Σ[ ｋ＝ｊ，ｎ]（−１）ｋ−ｊ・Ｃ（ ｋ ，ｋ−ｊ ）・ｊｎ
＝｛Σ[ ｋ＝１，ｎ]（−１）ｋ−1・Ｃ（ ｋ ，ｋ−１ ）・１ｎ
＋｛Σ[ ｋ＝２，ｎ]（−１）ｋ−2・Ｃ（ ｋ ，ｋ−２ ）・２ｎ
＋・・・・・・・・・・・・・・・・・・・
＋｛Σ[ ｋ＝ｎ，ｎ]（−１）ｋ−ｎ・Ｃ（ ｋ ，ｋ−ｎ ）・ｎｎ
＝｛Ｃ（ １ ，０ ）−Ｃ（ ２ ，１ ）＋Ｃ（ ３ ，２ ）−・・・＋（−１）ｎ−1Ｃ（ ｎ ，ｎ−１ ）｝・１ｎ
＋｛Ｃ（ ２ ，０ ）−Ｃ（ ３ ，１ ）＋Ｃ（ ４ ，２ ）−・・・＋（−１）ｎ−2Ｃ（ ｎ ，ｎ−２ ）｝・２ｎ
＋・・・・・・・・・・・・・・・・・・・
＋Ｃ（ ｎ ，０ ）・ｎｎ
となる。これは GAI さん が書かれた計算法そのものである。
ａ（ｎ）の導出方法は他にもあり、次のＨＰが参考になると思う。
http://web2.incl.ne.jp/yaoki/jyun.htm
http://web2.incl.ne.jp/yaoki/ajyun.htm
（コメント） ａｔ さん、ありがとうございます。奥が深い解答ですね！もう少し勉強させていた
だいて、行間を補充したいと思います。
以下、工事中