上限のある重複組合わせ(?)
以下の42個の数字から、n個 抜き取った組合わせは何通りかという問題がありまして(自作)。
1, 5, 6, 6, 8, 8,10,13,13,14, 14,15,17,18,18,19,21,21,22,25,
26,27,28,28,30,30,30,30,30,31, 31,34,35,35,36,39,40,40,41,41,
41,42
総当りで出力し、カウントをするプログラムはできまして(n=0個から)
1 26 337 2902 18667 95612 405931 1468386 4616880 12809820 31736232 70875642 143789049 ・・・
という感じで答えはわかっているのですが、時間もかかるし(3sぐらい)実際の組合わせは知る必要はないので
もっと数学的に計算でできないのか、考えているんですけど解りません。
問題を簡単にして、↓のように考えたのですが、やっぱり無駄に計算量が多いような気がします。
1,1,1,1,2,2,2,3,3,4 の10個の内 7個
4種類の数字の重複組合わせをベースとし
4 H 7 -> 4+7-1 C 7 -> 10 C 7 -> 120
・4 は、1つしかないので、2つ以上を含むパターンを除外する
4-4 確定 あと 5つを 4 H 5 -> 56
・3 は、2つしかないので、3つ以上含むパターンを除外する。
3-3-3 確定 あと4つを 4 H 4 -> 35
・2 は、 3つしかないので、4つ以上含むパターンを除外する。
2-2-2-2 確定 あと3つを 4 H 3 -> 20
・1 は、 4つしかないので、5つ以上含むパターンを除外する。
1-1-1-1-1 確定 あと2つを 4 H 2 -> 10
120-56-35-20-10 = -1
ただし、以下は重複しているので加算する。
4-4-3-3-3-*-* 10
4-4-2-2-2-2-* 4
3-3-3-2-2-2-2 1
4-4-1-1-1-1-1 1
-1 +10+4+1+1 -> 15
プログラムはすこしわかるのですが、数学はわかりません。
すぱっと数式ででるやりかたがあれば教えてください。
お礼
こんばんは。回答ありがとうございます。 え~と。 つまり、32パターンですよ。という事ですよね。 ということは、地道に書き出してみた。。。 16 16+1 16+2 16+2+1 16+4 16+4+1 16+4+2 16+4+2+1 16+8 16+8+1 16+8+2 16+8+2+1 16+8+4 16+8+4+1 16+8+4+2 16+8+4+2+1 32+16 32+16+1 32+16+2 32+16+2+1 32+16+4 32+16+4+1 32+16+4+2 32+16+4+2+1 32+16+8 32+16+8+1 32+16+8+2 32+16+8+2+1 32+16+8+4 32+16+8+4+1 32+16+8+4+2 32+16+8+4+2+1 このパターンで全て!って事になりそうですね@w@; ありがとうございます。 ちょっと確証が持てないので、何回か計算してからしめたいと思います。 ありがとうございますた。お手数かけます。。。