重複組合せ                                 戻る

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

     n+r−1 (通り)

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

 当HPの掲示板「出会いの泉」に、平成22年4月15日付けで、HN「H.I.」さんが、「長年
の悩みに決着を」と題して次のような書き込みをされた。

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

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

 具体的に言うと、

  n 種のものから r 個取り出す組合せ(並べ方)の総数を求めよ。

 ただし、同種のもの同士に区別はなく、それぞれ a1、a2、a3、・・・、a 個ずつ存在

 し、 n=a1+a2+a3+・・・+a≧r とする。


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


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

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

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

 4月16日付けで、GAIさんが次の書籍を紹介されている。

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

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

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

  G.ポリア、R.E.タージャン、D.R.ウッズ 著  今宮淳美 訳
    組合せ論入門  (近代科学社)


 4月16日付けで、at さんが

  求める場合の数は、

    

 の展開式における x の係数に等しい

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

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

 n=500 、r=1000 、aj=j ( j=1、2、・・・、n ) のときの求める場合の数は、

=67437688485159846865006105864543188233416431144570419716970023167492
754668340141452921577497235988038714364199582084267957349987726052909
174078840391375692844915973708233511193723261021381047652042172309628
558600375293549516060052492993528323385553789663008670297550191557409
356154541417380100551204881129712233947783683031299391260471601457521
58683103936526198611180521259061206710617857809451727609003289269893.

になるとのこと。


 当HPの掲示板「出会いの泉」に、平成22年4月29日付けで、HN「和哉ーk」さんが次の
ような書き込みをされた。

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


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

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


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

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

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

 a≦5 のとき、和が n+a となるのは、 通り

 a=6 のとき、和が n+6 となるのは、7以上の目を許せば、 6 通り

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

         よって、和が n+6 となるのは、 6−n 通り

 a=7 のとき、和が n+7 となるのは、7以上の目を許せば、 7 通り

        このうち、7以上の目が出来てしまう箇所は、n 通りで、そのうちの1通りに対

        して、8の目または7と2の目が出来る場合の数は、1 通り

         よって、和が n+7 となるのは、 7−n・1 通り

        (上記の、n・1=n2 通りの計算は次のように考えてもよい。
          8の目が出来てしまうものは、n 通り
          7の目と2の目が出来てしまうのは、n・(n−1) 通り
         よって、7以上の目が出来てしまうのは、 n+n・(n−1)=n2 通り)

  a=7における考え方を振り返ると、a=6の場合は、6−n・0 通りとも考えられる。

 同様にして、

 和が、n+8 となるのは、 8−n・2 通り

 和が、n+9 となるのは、 9−n・3 通り

 和が、n+10 となるのは、 10−n・4 通り

 和が、n+11 となるのは、 11−n・5 通り

 和が、n+12 となる場合、上記と同様に考えると、 12−n・6 通りである。

 しかし、n・6 通りの中には、2箇所で7になる場合も含まれているので、この場合は除

 外しなければならない。2箇所で7になる場合の数は、20 通りなので、

 求める場合の数は、 12−n・620 通り

  上記の考え方を振り返ると、 121620 通りとも考えられる。

 同様にして、

 和が、n+13 となるのは、 131721 通り

 和が、n+14 となるのは、 141822 通り

 和が、n+15 となるのは、 151923 通り

 和が、n+16 となるのは、 1611024 通り

 和が、n+17 となるのは、 1711125 通り

 和が、n+18 となるのは、 181122630 通り

 和が、n+19 となるのは、 191132731 通り

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

 以上から、一般に、和が、n+a となる場合の数は、

       

となる。(→ 参考:「個数定理」 包除原理」)

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

 この話題について、GAI さんからご教示頂きました。(平成22年5月2日付け)

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

    (x+x2+x3+x4+x5+x6

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

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

(コメント) この解法は、4月16日付けで、at さんが紹介した多項式の特別な場合になり
      ますね!


(平成26年10月11日付け)

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

問題  異なる3個のさいころを投げて,目の和が12となる場合の数を求めよ。

 問題を方程式で表せば、

  x+y+z=12 、 1≦x、y、z≦6

である。

 単に、x+y+z=12 、 1≦x、y、z を満たす整数解の組が何組あるかを問う問題だっ
たら、 (x−1)+(y−1)+(z−1)=9 として、 39119112=55(通り)である
が、「x、y、z≦6」が問題を難しくしている。

 そこで、x1=x−1、x2=y−1、x3=z−1 とおいて、

   x1+x2+x3=9 、 0≦x1、x2、x3≦5

を満たす組(x1,x2,x3)の総数を求めてみよう。

 E0={(x1,x2,x3)|x1+x2+x3=9、x1≧0、x2≧0、x3≧0}
 E1={(x1,x2,x3)|x1+x2+x3=9、x1≧6、x2≧0、x3≧0}
 E2={(x1,x2,x3)|x1+x2+x3=9、x1≧0、x2≧6、x3≧0}
 E3={(x1,x2,x3)|x1+x2+x3=9、x1≧0、x2≧0、x3≧6}

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

 n(E0)−n(E1)−n(E2)−n(E3)+n(E12)+n(E23)+n(E31)−n(E123

となる。ただし、E12=E1∩E2、・・・等。

 よって、 n(E0)=55、n(E1)=n(E2)=n(E3)=33=10、
      n(E12)=n(E23)=n(E31)=n(E123)=0

より、求める場合の数は、 55−10×3=25(通り) となる。

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

  (5,4,0)type ・・・ 6通り
  (5,3,1)type ・・・ 6通り
  (5,2,2)type ・・・ 3通り
  (4,4,1)type ・・・ 3通り
  (4,3,2)type ・・・ 6通り
  (3,3,3)type ・・・ 1通り

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

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

(解) x+y+z+w=17 、 1≦x、y、z、w≦6 より、

   a+b+c+d=13 、 0≦a、b、c、d≦5 を満たす組(a,b,c,d)の総数を求める。

 包除原理により、

  41341474241=560−4・120+6・4=104(通り)  (終)


(追記) 平成26年9月19日付け

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

例 題  区別のつかない10個のものを、A、B、C、Dの4人に分配する方法の数を求めよ。
     ただし、各人には少なくとも1個以上はもらえるものとする。

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

(解) あらかじめ4人に1個ずつ分け与え、残りの6個を、1個ももらわない場合もありとして
   4人に分ける方法の数は、
                    469693=84(通り)  (終)


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

(別解) 10個を横一列に並べたとき、その隙間は全部で9個ある。また、A、B、C、Dの4人
     を横一列に並べたとき、その隙間は全部で3個ある。

     このとき、10個のものを4人が1個以上もらうような分け方の総数は、9個の隙間か
    ら4人を識別する3つの隙間を選べばよいので、求める場合の数は、

      93=84(通り)  (終)

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

例 題  区別のつかない10個のものを、A、B、C、Dの4人に分配する方法の数を求めよ。
     ただし、1個ももらえない場合もありえるものとする。

 この場合は、 4101310133=286(通り) と求められるが、仕切り棒を考えても
できる。

 すなわち、○が10個と仕切り棒|が3個の同じものを含む順列と考えて、

    13!/(10!3!)=286(通り)

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

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

 A、B、C、Dの4人に1個ずつ計4個を分ける分を、10個のものに合算して、

 区別のつかない14個のものを、A、B、C、Dの4人に分配する方法の数を求めよ。ただし、
各人には少なくとも1個以上はもらえるものとする。

と問題を翻訳すれば、求める場合の数は、 133=286(通り) として求められる。

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

例 題  区別のつかない10個のものを、A、B、C、Dの4人に分配する方法の数を求めよ。
     ただし、1個ももらえない場合もありえるものとする。

 A→1、B→2、C→3、D→4 と考え、問題は、4個の数字 1、2、3、4 から重複を許して
10個取る組合せの数を求めよということである。例えば、(1、1、1、1、・・・、1)のように、10
個全部が1の場合は、Aが10個もらい、B、C、Dは1個ももらえないということである。

 このような組合せの数を求めるのは単純にはいかないが、(0、1、2、3、・・・、9)を加える
ことによって、全ての数字が相異なるようにできる。すなわち、求める場合の数は、

 相異なる4+9=13(個)から10個取る組合せの個数に等しいので、

    1310133=286(通り)

と求められる。


 GAIさんより、重複組合せに関する話題を頂きました。(平成26年10月11日付け)

問 題  10個のうち同じものをそれぞれ 4、3、2、1個ずつ含む
          a,a,a,a,b,b,b,c,c,d
     を、A、B、C、Dの4人に分配する方法の数を求めよ。


ただし、 (条件1):1個ももらえない場合もありえるものとする。

      
(条件2):各人には少なくとも1個以上はもらえるものとする。

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


 らすかるさんが考察されました。(平成26年10月11日付け)

(条件1)の場合

 a の分配方法は、4H4通り、bの分配方法は、4H3通り、cの分配方法は、4H2通り、
dの分配方法は、4H1通りだから、全部で、

   4H44H34H24H1=35・20・10・4=28000(通り)

(条件2)の場合

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

 特定の2人に全部分配する方法は、 2H42H32H22H1=5・4・3・2=120(通り)
このうち、2通りはどちらか1人だけがもらう場合なので、特定の2人が少なくとも1個はもら
うのは、
    120−2=118(通り)

 特定の3人に全部分配する方法は、 3H43H33H23H1=15・10・6・3=2700(通り)
このうち、3通りは誰か1人だけがもらう場合、 3C2・118=354(通り)は、ちょうど2人がも
らう場合なので、特定の3人が少なくとも1個はもらうのは、
    2700−3−354=2343(通り)

 特定の4人に全部分配する方法は、 4H44H34H24H1=28000(通り)
このうち、4通りは誰か1人だけがもらう場合、4C2・118=708(通り)はちょうど2人がもら
う場合、4C3・2343=9372(通り)はちょうど3人がもらう場合なので、特定の4人が少なく
とも1個はもらうのは、
    28000−4−708−9372=17916(通り)


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


 GAI さんからのコメントです。(平成26年10月12日付け)

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

(1) 特定の1人がもらう → {10}

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

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

(4) 4人が少なくとも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}}

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

 (1)は明らかに、4通り発生する。

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

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

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

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

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

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

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


(追記) 平成28年6月9日付け

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

 (n−1+r)!/(n−1)!r!=n+r−1

である。

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

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

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

 鹿野 和宏 著 「重複組合せの現代的解法」(数研通信 No.85)

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

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

 よって、最短経路問題と同様に考えて、求める場合の数は、(n−1+r)!/(n−1)!r!
となる。


(コメント) なるほど!「○」や「|」に翻訳するよりも、「↑」や「→」に翻訳した方が馴染みが
      あって分かりやすいかもしれないですね...。



   以下、工事中