重複組合せ

重複組合せ　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　相異なるｎ個のものから重複を許してｒ個とる組合せの数は、

　　_ｎＨ_ｒ＝_{ｎ＋ｒ－1}Ｃ_ｒ　（通り）

で与えられる。これは、順列組合せの基本公式だろう。

　当ＨＰの掲示板「出会いの泉」に、平成２２年４月１５日付けで、ＨＮ「Ｈ．Ｉ．」さんが、「長年
の悩みに決着を」と題して次のような書き込みをされた。

　組合せ数学の話ですが、詳しい方がいましたらご教授ください。高校で順列・組合せを学
んで以来、謎の設問があります。

　重複順列や重複組合せは使用する種別毎の個数に制限がありません。ならば、個数に
制限がある場合はどうなるのか？

　具体的に言うと、

　　ｎ種のものからｒ個取り出す組合せ（並べ方）の総数を求めよ。

　ただし、同種のもの同士に区別はなく、それぞれ a₁、a₂、a₃、・・・、a_ｎ個ずつ存在

　し、ｎ＝a₁＋a₂＋a₃＋・・・＋a_ｎ≧ｒ　とする。

　ごく簡単なものについては計算出来ますが、より一般的なものについての包括的な式や
定理はどういったものになるのでしょうか？

　この問いかけに対して、４月１５日付けで、らすかるさんは、

　おそらく、「ごく簡単なものについては計算は出来ますが、より一般的なものについての包
括的な式や定理は存在しない」と思いますと述べられている。

　私もらすかるさんに同感で、解法の指針は与えられても、具体的な公式を得ることは出来
ないだろうな～と直観的に思いました。

　４月１６日付けで、ＧＡＩさんが次の書籍を紹介されている。

　日評数学選書「数え上げ組合せ論入門」
（成嶋　弘著　日本評論社 ISBN4-535-60138-0）

　いろいろな数え上げに関する考察をコーシー・フロベニウスの定理により統一的視点から
記述されているとのことである。

　私は、次の書籍がこの問題については大いに参考になるものと確信する。

　Ｇ．ポリア、Ｒ．Ｅ．タージャン、Ｄ．Ｒ．ウッズ　著　　今宮淳美　訳
　組合せ論入門　　（近代科学社）

　４月１６日付けで、ａｔさんが

　求める場合の数は、

　

の展開式におけるｘ^ｒの係数に等しい

と述べられているが、この母関数利用の方法は、上記の本の　１１頁～１５頁に詳しく記述
されている。

　ａｔさんの計算によれば、例えば、

　ｎ＝５００　、ｒ＝１０００　、ａｊ＝ｊ　（ｊ＝１、２、・・・、ｎ）　のときの求める場合の数は、

＝67437688485159846865006105864543188233416431144570419716970023167492
754668340141452921577497235988038714364199582084267957349987726052909
174078840391375692844915973708233511193723261021381047652042172309628
558600375293549516060052492993528323385553789663008670297550191557409
356154541417380100551204881129712233947783683031299391260471601457521
58683103936526198611180521259061206710617857809451727609003289269893.

になるとのこと。

　当ＨＰの掲示板「出会いの泉」に、平成２２年４月２９日付けで、ＨＮ「和哉ーｋ」さんが次の
ような書き込みをされた。

　先日の授業で「ｎ回サイコロ投げたとき、出た目の数の和がｎ＋５になる確率を求めよ。」
という問題は、通常の解答以外に重複組み合わせでも解けると先生が言われたのですが、
分かる人教えてくれませんか？

　この問いかけに対して、４月３０日付けで、らすかるさんは、

　全部が 1 のとき合計がｎなので、あと 5 をどこかに足せばｎ＋５になります。よって、ｎ
回のうち重複を許して５個選べば場合の数が出るので、求める確率は _ｎＨ₅/６^ｎとなります。

と明解に答えられた。この問題では、「＋５」が大きな意味を持っていて、らすかるさんの解
答で、１に５を足しても６となり、さいころの目の数を超えないという点がミソだろう。

　そうすると、さいころの目の数を超える可能性のある「目の和がｎ＋６となる場合の数は？」
という問いかけが気になってくる。

　これについても、４月３０日付けで、らすかるさんは、明解に答えられた。らすかるさんに感
謝します。

　ａ≦５　のとき、和がｎ＋ａとなるのは、 _ｎＨ_ａ通り

　ａ＝６　のとき、和がｎ＋６となるのは、７以上の目を許せば、 _ｎＨ₆ 通り

　　このうち、７の目が出来てしまうものは、ｎ通り

　　よって、和がｎ＋６となるのは、　_ｎＨ₆－ｎ通り

　ａ＝７　のとき、和がｎ＋７となるのは、７以上の目を許せば、 _ｎＨ₇ 通り

　　このうち、７以上の目が出来てしまう箇所は、ｎ通りで、そのうちの１通りに対して、８の目

　　または７と２の目が出来る場合の数は、_ｎＨ₁ 通り

　　よって、和がｎ＋７となるのは、　_ｎＨ₇－ｎ・_ｎＨ₁ 通り

（上記の、ｎ・_ｎＨ₁＝ｎ² 通りの計算は次のように考えてもよい。
　８の目が出来てしまうものは、ｎ通り
　７の目と２の目が出来てしまうのは、ｎ・（ｎ－１）通り
　よって、７以上の目が出来てしまうのは、　ｎ＋ｎ・（ｎ－１）＝ｎ² 通り）

　ａ＝７における考え方を振り返ると、ａ＝６の場合は、_ｎＨ₆－ｎ・_ｎＨ₀ 通りとも考えられる。

同様にして、

　和が、ｎ＋８となるのは、　_ｎＨ₈－ｎ・_ｎＨ₂ 通り

　和が、ｎ＋９となるのは、　_ｎＨ₉－ｎ・_ｎＨ₃ 通り

　和が、ｎ＋１０となるのは、　_ｎＨ₁₀－ｎ・_ｎＨ₄ 通り

　和が、ｎ＋１１となるのは、　_ｎＨ₁₁－ｎ・_ｎＨ₅ 通り

　和が、ｎ＋１２となる場合、上記と同様に考えると、 _ｎＨ₁₂－ｎ・_ｎＨ₆ 通りである。

しかし、ｎ・_ｎＨ₆ 通りの中には、２箇所で７になる場合も含まれているので、この場合は除外

しなければならない。２箇所で７になる場合の数は、_ｎＣ₂・_ｎＨ₀ 通りなので、

　求める場合の数は、　_ｎＨ₁₂－ｎ・_ｎＨ₆＋_ｎＣ₂・_ｎＨ₀ 通り

　上記の考え方を振り返ると、　_ｎＨ₁₂－_ｎＣ₁・_ｎＨ₆＋_ｎＣ₂・_ｎＨ₀ 通りとも考えられる。

同様にして、

　和が、ｎ＋１３となるのは、　_ｎＨ₁₃－_ｎＣ₁・_ｎＨ₇＋_ｎＣ₂・_ｎＨ₁ 通り

　和が、ｎ＋１４となるのは、　_ｎＨ₁₄－_ｎＣ₁・_ｎＨ₈＋_ｎＣ₂・_ｎＨ₂ 通り

　和が、ｎ＋１５となるのは、　_ｎＨ₁₅－_ｎＣ₁・_ｎＨ₉＋_ｎＣ₂・_ｎＨ₃ 通り

　和が、ｎ＋１６となるのは、　_ｎＨ₁₆－_ｎＣ₁・_ｎＨ₁₀＋_ｎＣ₂・_ｎＨ₄ 通り

　和が、ｎ＋１７となるのは、　_ｎＨ₁₇－_ｎＣ₁・_ｎＨ₁₁＋_ｎＣ₂・_ｎＨ₅ 通り

　和が、ｎ＋１８となるのは、　_ｎＨ₁₈－_ｎＣ₁・_ｎＨ₁₂＋_ｎＣ₂・_ｎＨ₆－_ｎＣ₃・_ｎＨ₀ 通り

　和が、ｎ＋１９となるのは、　_ｎＨ₁₉－_ｎＣ₁・_ｎＨ₁₃＋_ｎＣ₂・_ｎＨ₇－_ｎＣ₃・_ｎＨ₁ 通り

　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　以上から、一般に、和が、ｎ＋ａとなる場合の数は、

　

となる。（→　参考：「個数定理」　包除原理」）

（コメント）　今まで知らない公式で、感動しました！重複組合せの考え方が巧妙に使われ
　　　　　ていますね。

　この話題について、ＧＡＩさんからご教示頂きました。（平成２２年５月２日付け）

　ｎ個のサイコロを投げるとき、目の和がＮとなる場合の数は、多項式

　（ｘ＋ｘ²＋ｘ³＋ｘ⁴＋ｘ⁵＋ｘ⁶）^ｎ

を展開したときの、ｘ^Ｎの係数を調べればいいと聞いたことがあります。

適当なソフト（MathematicaやPARI/GP）で展開してやれば比較的簡単に求まります。

（コメント）　この解法は、４月１６日付けで、ａｔさんが紹介した多項式の特別な場合になりま
　　　　　すね！

（追記）　平成２６年１０月１１日付け

　上記の公式の考え方を次の問題に応用してみよう。

問題　　異なる３個のさいころを投げて，目の和が１２となる場合の数を求めよ。

　問題を方程式で表せば、

　ｘ＋ｙ＋ｚ＝１２　、　１≦ｘ、ｙ、ｚ≦６

である。

　単に、ｘ＋ｙ＋ｚ＝１２　、１≦ｘ、ｙ、ｚ　を満たす整数解の組が何組あるかを問う問題だった
ら、　（ｘ－１）＋（ｙ－１）＋（ｚ－１）＝９　として、　₃Ｈ₉＝₁₁Ｃ₉＝₁₁Ｃ₂＝５５（通り）であるが、
「ｘ、ｙ、ｚ≦６」が問題を難しくしている。

　そこで、ｘ₁＝ｘ－１、ｘ₂＝ｙ－１、ｘ₃＝ｚ－１　とおいて、

　ｘ₁＋ｘ₂＋ｘ₃＝９　、　０≦ｘ₁、ｘ₂、ｘ₃≦５

を満たす組（ｘ₁，ｘ₂，ｘ₃）の総数を求めてみよう。

　Ｅ₀＝｛（ｘ₁，ｘ₂，ｘ₃）｜ｘ₁＋ｘ₂＋ｘ₃＝９、ｘ₁≧０、ｘ₂≧０、ｘ₃≧０｝
　Ｅ₁＝｛（ｘ₁，ｘ₂，ｘ₃）｜ｘ₁＋ｘ₂＋ｘ₃＝９、ｘ₁≧６、ｘ₂≧０、ｘ₃≧０｝
　Ｅ₂＝｛（ｘ₁，ｘ₂，ｘ₃）｜ｘ₁＋ｘ₂＋ｘ₃＝９、ｘ₁≧０、ｘ₂≧６、ｘ₃≧０｝
　Ｅ₃＝｛（ｘ₁，ｘ₂，ｘ₃）｜ｘ₁＋ｘ₂＋ｘ₃＝９、ｘ₁≧０、ｘ₂≧０、ｘ₃≧６｝

とおくと、求める場合の数は、包除原理により、

　ｎ（Ｅ₀）－ｎ（Ｅ₁）－ｎ（Ｅ₂）－ｎ（Ｅ₃）＋ｎ（Ｅ₁₂）＋ｎ（Ｅ₂₃）＋ｎ（Ｅ₃₁）－ｎ（Ｅ₁₂₃）

となる。ただし、Ｅ₁₂＝Ｅ₁∩Ｅ₂、・・・等。

　よって、　ｎ（Ｅ₀）＝５５、ｎ（Ｅ₁）＝ｎ（Ｅ₂）＝ｎ（Ｅ₃）＝₃Ｈ₃＝１０、
　　　　　　ｎ（Ｅ₁₂）＝ｎ（Ｅ₂₃）＝ｎ（Ｅ₃₁）＝ｎ（Ｅ₁₂₃）＝０

より、求める場合の数は、　５５－１０×３＝２５（通り）　となる。

　実際に、２５通りを列挙すれば、

　（５，４，０）ｔｙｐｅ　・・・　６通り
　（５，３，１）ｔｙｐｅ　・・・　６通り
　（５，２，２）ｔｙｐｅ　・・・　３通り
　（４，４，１）ｔｙｐｅ　・・・　３通り
　（４，３，２）ｔｙｐｅ　・・・　６通り
　（３，３，３）ｔｙｐｅ　・・・　１通り

　読者のために、練習問題を残しておこう。

練習問題　４個のさいころを投げるとき、目の和が１７となる場合の数を求めよ。

（解）　ｘ＋ｙ＋ｚ＋ｗ＝１７　、　１≦ｘ、ｙ、ｚ、ｗ≦６　より、

　ａ＋ｂ＋ｃ＋ｄ＝１３　、　０≦ａ、ｂ、ｃ、ｄ≦５　を満たす組（ａ，ｂ，ｃ，ｄ）の総数を求める。

包除原理により、

　₄Ｈ₁₃－₄Ｃ₁・₄Ｈ₇＋₄Ｃ₂・₄Ｈ₁＝５６０－４・１２０＋６・４＝１０４（通り）　　（終）

（追記）　平成２６年９月１９日付け

　重複組合せはいらないという方も多く、最近の学校教育では重複組合せの陰が薄くなって
いるように感じる。Ｈという便利な記号なのだが、考え方がしっかりできていれば確かに記号
そのものはいらないかもしれない。

例　題　　区別のつかない１０個のものを、Ａ、Ｂ、Ｃ、Ｄの４人に分配する方法の数を求めよ。
　　　　　ただし、各人には少なくとも１個以上はもらえるものとする。

　この問題に対して、私はこれまで次のように考えて解いてきた。

（解）　あらかじめ４人に１個ずつ分け与え、残りの６個を、１個ももらわない場合もありとして
　　　４人に分ける方法の数は、　₄Ｈ₆＝₉Ｃ₆＝₉Ｃ₃＝８４（通り）　　（終）

　このような考え方に対して、次のような考え方もあることを最近知ることができた。

（別解）　１０個を横一列に並べたとき、その隙間は全部で９個ある。また、Ａ、Ｂ、Ｃ、Ｄの４人
　を横一列に並べたとき、その隙間は全部で３個ある。

このとき、１０個のものを４人が１個以上もらうような分け方の総数は、９個の隙間から４人を
識別する３つの隙間を選べばよいので、求める場合の数は、　₉Ｃ₃＝８４（通り）　　（終）

　ただ、この別解の考え方は、次の問題になると少し途方に暮れてしまう。もっとも、「分配」と
いうと、１個はもらえるだろうと考えるのが自然で、問題の方が特殊なのかもしれない。

例　題　　区別のつかない１０個のものを、Ａ、Ｂ、Ｃ、Ｄの４人に分配する方法の数を求めよ。
　　　ただし、１個ももらえない場合もありえるものとする。

　この場合は、　₄Ｈ₁₀＝₁₃Ｃ₁₀＝₁₃Ｃ₃＝２８６（通り）　と求められるが、仕切り棒を考えても
できる。

　すなわち、○が１０個と仕切り棒｜が３個の同じものを含む順列と考えて、

　１３！/（１０！３！）＝２８６（通り）

　上記のように考えれば解決するが、では、「１個以上はもらえる」場合の解法は途方に暮
れるだけで、為す術はないのだろうか？実は、あるのである。

　次のように考えればよい。

　Ａ、Ｂ、Ｃ、Ｄの４人に１個ずつ計４個を分ける分を、１０個のものに合算して、

　区別のつかない１４個のものを、Ａ、Ｂ、Ｃ、Ｄの４人に分配する方法の数を求めよ。ただし、
各人には少なくとも１個以上はもらえるものとする。

と問題を翻訳すれば、求める場合の数は、　₁₃Ｃ₃＝２８６（通り）　として求められる。

　さて、上記の仕切り棒を用いる考え方は久しく高校数学を席巻している（昭和６０年代以降）
が、次のような考え方も以前はあったらしい。（順序組分配法と言われる。）

例　題　　区別のつかない１０個のものを、Ａ、Ｂ、Ｃ、Ｄの４人に分配する方法の数を求めよ。
　　　　　ただし、１個ももらえない場合もありえるものとする。

　Ａ→１、Ｂ→２、Ｃ→３、Ｄ→４　と考え、問題は、４個の数字　１、２、３、４　から重複を許して
１０個取る組合せの数を求めよということである。例えば、（１、１、１、１、・・・、１）のように、１０
個全部が１の場合は、Ａが１０個もらい、Ｂ、Ｃ、Ｄは１個ももらえないということである。

　このような組合せの数を求めるのは単純にはいかないが、（０、１、２、３、・・・、９）を加える
ことによって、全ての数字が相異なるようにできる。すなわち、求める場合の数は、

　相異なる４＋９＝１３（個）から１０個取る組合せの個数に等しいので、

　₁₃Ｃ₁₀＝₁₃Ｃ₃＝２８６（通り）

と求められる。

　ＧＡＩさんより、重複組合せに関する話題を頂きました。（平成２６年１０月１１日付け）

問　題　１０個のうち同じものをそれぞれ４、３、２、１個ずつ含む
　ａ，ａ，ａ，ａ，ｂ，ｂ，ｂ，ｃ，ｃ，ｄ
を、Ａ、Ｂ、Ｃ、Ｄの４人に分配する方法の数を求めよ。

ただし、（条件１）：１個ももらえない場合もありえるものとする。

　（条件２）：各人には少なくとも１個以上はもらえるものとする。

とした、それぞれについて場合の数を求めよ。

　らすかるさんが考察されました。（平成２６年１０月１１日付け）

（条件１）の場合

　ａの分配方法は、₄H₄通り、ｂの分配方法は、₄H₃通り、ｃの分配方法は、₄H₂通り、
ｄの分配方法は、₄H₁通りだから、全部で、

　　　₄H₄・₄H₃・₄H₂・₄H₁＝３５・２０・１０・４＝２８０００（通り）

（条件２）の場合

　特定の１人に全部分配する方法は、１通り

　特定の２人に全部分配する方法は、　₂H₄・₂H₃・₂H₂・₂H₁＝５・４・３・２＝１２０（通り）
このうち、２通りはどちらか１人だけがもらう場合なので、特定の２人が少なくとも１個はもら
うのは、
　　　　１２０－２＝１１８（通り）

　特定の３人に全部分配する方法は、　₃H₄・₃H₃・₃H₂・₃H₁＝１５・１０・６・３＝２７００（通り）
このうち、３通りは誰か1人だけがもらう場合、　₃C₂・１１８＝３５４（通り）は、ちょうど２人がも
らう場合なので、特定の３人が少なくとも１個はもらうのは、
　　　　２７００－３－３５４＝２３４３（通り）

　特定の４人に全部分配する方法は、　₄H₄・₄H₃・₄H₂・₄H₁＝２８０００（通り）
このうち、４通りは誰か１人だけがもらう場合、₄C₂・１１８＝７０８（通り）はちょうど２人がもら
う場合、₄C₃・２３４３＝９３７２（通り）はちょうど3人がもらう場合なので、特定の４人が少なく
とも１個はもらうのは、
　　　　２８０００－４－７０８－９３７２＝１７９１６（通り）

（コメント）　ＧＡＩさんが仰るとおり、確かに「ややこしい分配」ですね！らすかるさんの解法で
　　　　　は配られない人に注目して場合分けされています。常套手段の「とりあえず全員に
　　　　　１個あげる」手法ではどうかと思案しましたが、何か膨大な場合分けが発生しそうで
　　　　　解き進めるのを断念しました。多分、らすかるさんの解法が一番自然ですね！

　ＧＡＩさんからのコメントです。（平成２６年１０月１２日付け）

　１０個を分割する方向から攻めていました。１０を分割してみると、

（１）　特定の１人がもらう　→　{10}

（２）　特定の２人がもらう　→　{5,5}、{6,4}、{7,3}、{8,2}、{9,1}

（３）　特定の３人がもらう　→　{4,3,3}、{4,4,2}、{5,3,2}、{5,4,1}、{6,2,2}、{6,3,1}、{7,2,1}、{8,1,1}

（４）　４人が少なくとも１個はもらう
　　→　{3,3,2,2}、{3,3,3,1}、{4,2,2,2}、{4,3,2,1}、{4,4,1,1}、{5,2,2,1}、{5,3,1,1}、{6,2,1,1}、{7,1,1,1}

（前準備）　Union[Subsets[{a, a, a, a, b, b, b, c, c, d}, {2}]]　から

{{a,a},{a,b},{a,c},{a,d},{b,b},{b,c},{b,d},{c,c},{c,d}}

{{a,a,a},{a,a,b},{a,a,c},{a,a,d},{a,b,b},{a,b,c},{a,b,d},{a,c,c},{a,c,d},{b,b,b},{b,b,c},{b,b,d},{b,c,c},{b,c,d},{c,c,d}}

{{a,a,a,a},{a,a,a,b},{a,a,a,c},{a,a,a,d},{a,a,b,b},{a,a,b,c},{a,a,b,d},{a,a,c,c},{a,a,c,d},{a,b,b,b},{a,b,b,c},{a,b,b,d},
　{a,b,c,c},{a,b,c,d},{a,c,c,d},{b,b,b,c},{b,b,b,d},{b,b,c,c},{b,b,c,d},{b,c,c,d}}

{{a,a,a,a,b},{a,a,a,a,c},{a,a,a,a,d},{a,a,a,b,b},{a,a,a,b,c},{a,a,a,b,d},{a,a,a,c,c},{a,a,a,c,d},{a,a,b,b,b},{a,a,b,b,c},
　{a,a,b,b,d},{a,a,b,c,c},{a,a,b,c,d},{a,a,c,c,d},{a,b,b,b,c},{a,b,b,b,d},{a,b,b,c,c},{a,b,b,c,d},{a,b,c,c,d},{b,b,b,c,c},
　{b,b,b,c,d},{b,b,c,c,d}}

{{a,a,a,a,b,b},{a,a,a,a,b,c},{a,a,a,a,b,d},{a,a,a,a,c,c},{a,a,a,a,c,d},{a,a,a,b,b,b},{a,a,a,b,b,c},{a,a,a,b,b,d},
　{a,a,a,b,c,c},{a,a,a,b,c,d},{a,a,a,c,c,d},{a,a,b,b,b,c},{a,a,b,b,b,d},{a,a,b,b,c,c},{a,a,b,b,c,d},{a,a,b,c,c,d},
　{a,b,b,b,c,c},{a,b,b,b,c,d},{a,b,b,c,c,d},{b,b,b,c,c,d}}

{{a,a,a,a,b,b,b},{a,a,a,a,b,b,c},{a,a,a,a,b,b,d},{a,a,a,a,b,c,c},{a,a,a,a,b,c,d},{a,a,a,a,c,c,d},{a,a,a,b,b,b,c},
　{a,a,a,b,b,b,d},{a,a,a,b,b,c,c},{a,a,a,b,b,c,d},{a,a,a,b,c,c,d},{a,a,b,b,b,c,c},{a,a,b,b,b,c,d},{a,a,b,b,c,c,d},
　{a,b,b,b,c,c,d}}

{{a,a,a,a,b,b,b,c},{a,a,a,a,b,b,b,d},{a,a,a,a,b,b,c,c},{a,a,a,a,b,b,c,d},{a,a,a,a,b,c,c,d},{a,a,a,b,b,b,c,c},
　{a,a,a,b,b,b,c,d},{a,a,a,b,b,c,c,d},{a,a,b,b,b,c,c,d}}

を元に調査を進めました。

（１）は明らかに、４通り発生する。

（２）での、{5,5}-->11通り構成可能、{6,4}-->20　、{7,3}-->15　、{8,2}-->9　、{9,1}-->4

　２人の選択も含め結局４人うち２人で分配するのは、(11+20+15+9+4)*4!/2!=59*12=708(通り）

（３）では、{4,3,3}-->60通り（例外が３個:{a,a,b},{a,a,c},{a,b,c}は同じもので他の3個分ができる。）
　{4,4,2}-->52 　　(例外が１個:{a,a,b,c}は同じもので他の4個分ができる。）
　{5,3,2}-->93　、{5,4,1}-->62
　{6,2,2}-->30 　　(例外が４個:{a,a},{a,b},{a,c},{b,c}は同じもので重なる。）
　{6,3,1}-->50　、{7,2,1}-->32
　{8,1,1}-->6 　　(例外が３個:{a},{b},{c}は同じもので重なる。)

　これから３人だけで分配してしまうのが、

　(60+52+93+62+30+50+32+6)*4!+(3+1+4+3)*4!/2!=385*24+11*12=9240+132=9372（通り）

　こうしてみると、らすかるさんの考え方が如何に的を射たものであるかが思い知らされます。
重複組合せの道具がこんな問題を考察するときに如何に大切かが身に滲みます。

　敢えて重複組合せは教えなくてもよいという論議もあるようですが、これを組合せだけの知
識で処理しようとすれば、私みたいに途方もない調査をするハメになってしまいます。私もあ
のHの記号が苦手でしたが、これからは仲良く付き合いたいと思います。

（追記）　平成２８年６月９日付け

　異なるｎ個のものから重複を許してｒ個とる重複組合せの数の標準的な求め方は、ｎ－１本
の仕切り棒｜とｒ個の○の、同じものを含む順列の数に等しいことから、

　（ｎ－１＋ｒ）！/（ｎ－１）！ｒ！＝_{ｎ＋ｒ－１}Ｃ_ｒ＝_ｎＨ_ｒ

である。

　分かってしまえば何でもないが、どれが○でどれが｜になるのかとか、なぜ仕切り棒なるも
のを考えるのか初学者にとって理解しづらい面があることも否めない。

　ｒ個の○のどこからどこまでが該当するのかを区分けするためのものなのだが．．．。

　この困難さを克服する方法があることを最近知ることができた。

　鹿野　和宏　著　「重複組合せの現代的解法」（数研通信　Ｎｏ．８５）

　１個並べることを、「↑」で表すことにすると、ｒ個並べるので、「↑」がｒ個

　並べるものの種類を変えることを「→」で表すことにすると、ｎ個あるものの種類を変える方
法の数は、「→」がｎ－１個となる。

　よって、最短経路問題と同様に考えて、求める場合の数は、（ｎ－１＋ｒ）！/（ｎ－１）！ｒ！
となる。

（コメント）　なるほど！「○」や「｜」に翻訳するよりも、「↑」や「→」に翻訳した方が馴染みが
　　　　　あって分かりやすいかもしれないですね．．．。

（追記）　平成３１年１月２６日付け

　重複組合せの計算というと、上記のように区別が付かないいくつかのものを仕切り棒を用
いて区別し、同じものを含む順列の計算に翻訳する方法が一般的である。

例　２つのＡ、Ｂから重複を許して３個取る組合せの数は、重複組合せの公式を用いて、

　₂Ｈ₃＝_2+3-1Ｃ₃＝₄Ｃ₃＝４（通り）

　実際に、　ＡＡＡ、ＡＡＢ、ＡＢＢ、ＢＢＢ　と並べてみても分かるだろう。

　これに対して、最近次のような考え方があることを知ることができた。これは驚くべき画期
的な方法である。是非、世間一般にも広めたいものだ。

　２・３・４/３！＝４（通り）

例　４つの文字Ａ、Ｂ、Ｃ、Ｄから重複を許して６個取る組合せの数は、

　４・５・６・７・８・９/６！＝８４（通り）

　Ｈを用いて計算すれば、　₄Ｈ₆＝_4+6-1Ｃ₆＝₉Ｃ₆＝₉Ｃ₃＝８４（通り）

　上記の例「２つのＡ、Ｂから重複を許して３個取る組合せの数」を元に計算の原理を確認し
てみよう。

（計算の原理）　２つの文字Ａ、Ｂを用いるので、Ａ、Ｂと名前のついた線分を用意し横に並べ
　　　　　　　　　る。

　　

　３個並べるので、番号を付けて、「１」、「２」、「３」とする。

　まず、番号「１」は、線分Ａ、Ｂの何れでもいいので、並べ方は、２通り

　次に、番号「２」の並べ方は、３通りある。

　例えば、最初の番号「１」が線分Ａ上に置かれた場合、

　

　

　

　同様にして、番号「３」の並べ方は、２つの番号の間にも並ぶものとして、４通りある。

　以上から、線分Ａ、Ｂ上で、番号「１」、「２」、「３」の並べ方は全部で、２×３×４＝２４（通り）
ある。

　ここで、番号による区別を取り払うと、３！個ずつ同じものが出来る。

　したがって、求める組合せの数は、　２×３×４/３！＝４（通り）　となる。

（コメント）　このような計算の原理を一般化することは容易だろう。

（追記）　当ＨＰの掲示板「出会いの泉」に、令和２年１２月１８日付けで、ＨＮ「ＧＡＩ」さんが
　　　　「変形組合せ」と題してご投稿されました。

　１０個の異なる {a1,a2,･･･,a10} から５個を取り出す組合せは、

　　₁₀Ｃ₅＝10*9*8*7*6/(5*4*3*2*1)＝252 (通り)

で算出できる。そこで、もし重複を許して5個取り出す組合せを出したいならその数は幾つで
しょう？

{a1,a1,a1,a1,a1}、{a1,a1,a1,a1,a2}、･･･、{a2,a4,a6,a8,a9}、･･･、{a10,a10,a10,a10,a10}

　一般に、異なるｎ個のものから、重複を認めｒ個取り出す組合せ数は？

　らすかるさんからのコメントです。（令和２年１２月１８日付け）

　１０個の異なる {a1,a2,･･･,a10} から重複を認め５個を取り出す組合せは、₁₀Ｈ₅＝2002

　一般に、異なるｎ個のものから、重複を認めｒ個取り出す組合せ数は？

　_nＨ_r＝_n+r-1Ｃ_r　　# こんな簡単な答えでいいのかな？

　ＧＡＩさんからのコメントです。（令和２年１２月１８日付け）

　あーそうか！別の考えでやっと右の式でいいんだと掴んだと思ったら、この記号がありまし
たね。ただ、この計算は、

　₁₀Ｈ₅＝(10*11*12*13*14)/(5*4*3*2*1)

　・・・　分母は減少、分子は増加と覚えて処理できる。

　では、次の和はどうなるでしょうか？

　a1～a5を自然数とし、

(1)　∑_{1≦a1≦a2≦a3≦a4≦a5≦10} a1*a2*a3*a4*a5

(2)　∑_{1≦a1<a2<a3<a4<a5≦10} a1*a2*a3*a4*a5

　一般に、a1、a2、･･･、ak∈Nで、

(A)　∑_{1≦a1≦a2≦･･･≦ak≦n} a1*a2*･･･*ak

(B)　∑_{1≦a1<a2<･･･<ak≦n} a1*a2*･･･*ak

　らすかるさんからのコメントです。（令和２年１２月１８日付け）

(1)　f(n,k)=∑_{1≦a1≦a2≦･･･≦ak≦n} a1*a2*･･･*ak　とおくと、

　f(n,0)=1、f(1,k)=1、f(n,k)=f(n-1,k)+nf(n,k-1)　(n＞1、k＞0)　なので、表を作ると(Excel使用)
n＼k 0 1 2 3 4 5 1 1 1 1 1 1 1 2 1 3 7 15 31 63 3 1 6 25 90 301 966 4 1 10 65 350 1701 7770 5 1 15 140 1050 6951 42525 6 1 21 266 2646 22827 179487 7 1 28 462 5880 63987 627396 8 1 36 750 11880 159027 1899612 9 1 45 1155 22275 359502 5135130 10 1 55 1705 39325 752752 12662650

となり、　∑_{1≦a1≦a2≦a3≦a4≦a5≦10} a1*a2*a3*a4*a5=12662650

(2)　f(n,k)=∑_{1≦a1<a2<･･･<ak≦n} a1*a2*･･･*ak　とおくと、

　f(n,0)=1、f(n,n)=n!、f(n,k)=0(n＜k)、f(n,k)=f(n-1,k)+nf(n-1,k-1)　(n＞k＞0)　なので、表を作

ると(Excel使用)

n＼k 0 1 2 3 4 5 1 1 1 0 0 0 0 2 1 3 2 0 0 0 3 1 6 11 6 0 0 4 1 10 35 50 24 0 5 1 15 85 225 274 120 6 1 21 175 735 1624 1764 7 1 28 322 1960 6769 13132 8 1 36 546 4536 22449 67284 9 1 45 870 9450 63273 269325 10 1 55 1320 18150 157773 902055

となり、　Σ[1≦a1＜a2＜…＜a5≦10]a1a2a3a4a5=902055

　(1)は「A008277」、(2)は「A130534」にありますが、これって、f(n,k)の一般式を初等関数の
範囲内で表せるんですかね？

　ＧＡＩさんからのコメントです。（令和２年１２月１８日付け）

　(A)は、　f(n,k)=∑[i=0,n](-1)^(n-i)/((n-i)!*i!)*i^(n+k)　で行けそうです。

　(B)は、

f(n,k)=∑[i=0,n]binomial(k-(n+1),i+k)*binomial(k+n+1),n+1+i)/i!*Σ[j=0,i]binomial(i,j)*(-1)^(i-j)*j^(k+i)))

で行けそうです。

　　　以下、工事中