◆宮城県 アンパンマン さんからの解答。
n=4のときの解答です。
商品がn種類の場合、一番少ない福袋のときは
nCn-1＋nCn＝n＋１福袋が必要です。
n−１の商品を入れる袋 n袋と全ての商品いれる袋１つです。
(１通りです。)
一番多い福袋のときは
nC1+nC2=n+1C2 福袋が必要です。
商品１ついれる袋n袋と商品２つ入れる袋nC2 袋です。
(１通りです。)
例えばn=5の場合は(商品＝A,B,C,D,Eとします):
一番少ないとき
[B+C+D+E]
[A+C+D+E]
[A+B+D+E]
[A+B+C+E]
[A+B+C+D]
[A+B+C+D+E]
(6袋で1通りです。)
一番多いとき
[A]
[B]
[C]
[D]
[E]
[A+B]
[A+C]
[A+D]
[A+E]
[B+C]
[B+D]
[B+E]
[C+D]
[C+E]
[D+E]
(15袋で1通りです。)
商品がn種類の場合、m袋に入れる通り数をN(n,m)と定義すると
N(n,n+1)=1
| N(n, | n(n+1) 2 |
)=1がわかります。 |
n+1の袋の組合せからN(n,n+2)を求めます。
n+1の袋の組合せからn−１の商品を入れる袋 n袋をRグループ、全ての商品を入れる袋１つをSグループとします。
RグループまたはSグループから一つの袋を取り出して、中身の一部を新しい袋に入れます。
そうするとn+2袋になります。
1)Rグループから取り出す場合：
| n 2! |
( | n-2 Σ i=1 | n-1Ci | ) | =n(2n-2-1)通りです。 |
2)Sグループから取り出す場合：
| 1 2! |
( | n-2 Σ i=2 | n-1Ci | ) | =2n-1-n-1通りです。 |
つまり、N(n,n+2)＝(n+2)2n-2-2n-1 です。
次は N(n,n+3)を求めます。
1)Rグループから一つ取り出して３つに分ける場合：
| n 3! |
( | Σ i≧1,j≧1,n-i-j≧2 | (n-1)! i!j!(n-1-i-j)! | ) |
| = | n 3! | ( | 3n-1-3C1 *2n-1+3C2*1n-1) 通り |
3n-1-3C1*2n-1+3C2*1n-1は
「同順を許す並び方の数は？」問題のJ(n-1,3)です。
J(n,k)
| = | k Σ i=0 | (-1)i kCi (k-i)n |
| = | Σ i1,i2,...,ik≧1 i1+i2+...+ik=n | n！ (i1)！(i2)！...(ik)！ |
つまり
J(n,n)
| = | Σ i1,i2,...,in≧1 i1+i2+...+in=n | n！ (i1)！(i2)！...(in)！ |
| = | n！ 1！1！...1！ |
| =n！, |
さらに
J(n+1,n)
| = | Σ i1,i2,...,in≧1 i1+i2+...+in=n+1 | (n+1)！ (i1)！(i2)！...(in)！ |
| =nC1 |
(n+1)！ 2！1！...1！ |
| = |
n(n+1) 2 | n！ |
これらを使って
| k Σ i=0 | (-1)i kCi (k-i-x)n の場合も計算可能です。 |
ちなみに、「同順を許す並び方の数は？」問題は「生徒のグループ分け」問題との関連性があります。
(J(n,k)＝k！ P(k,n))
2)Rグループから２つの袋を取り出して各袋から２つに分ける場合：
(袋の中身が他の袋と重複にならないことを注意しながら)
| nC2 | (( | 2n-1-2 2 | )2 | - | 2n-1-2 2 |
) |
3)Sグループから一つ取り出して３つに分ける場合：
| 1 3！ |
( | Σ i≧1,j≧1,n-i-j≧1 | n！ i！j！(n-i-j)！ | ) |
| = | 3n-3C1*2n+3C2*1n 3！ |
| = | J(n,3) 3！ | 通り |
4)各グループ(RとS)から１つの袋を取り出して各袋から２つに分ける場合：
(ケース３と同じ場合がありますので、その場合を除きます)
| nC1 | [ | 2n-1-2 2 |
2n-2n-2 2 |
-2 | 2n-1-2 2 | +n-1 | ] |
| ＝n[(2n-2-1)(2n-1-n-1)-2n-1+n+1] 通り |
ケース１から４まで合計すると
N(n,n+3)
| ＝ | nJ(n-1,3) 3！ |
+ | J(n,3) 3！ |
+nC2 (22(n-2)-3*2n-2+2)+n[(2n-2-1)(2n-1-n-1)-2n-1+n+1] |
| 次はN(n, | n(n+1) 2 |
-1)を求めます。 |
| 一番多いとき | n(n+1) 2 |
袋から二つの袋を取り出して一つの袋にすると |
| n(n+1) 2 |
-1袋になります。 |
| 一番多いとき | n(n+1) 2 |
袋、 |
| N(n, | n(n+1) 2 |
-1)は次のように求められます。 |
1)Tグループから袋２つ取り出して１つにする場合：
Uのグループと重複になりますので＝０通り
2)Uグループから袋２つ取り出して１つにする場合：
| nC2* | n-2C2 2！ |
=3 nC4 通り |
3)各グループ(TとU)から袋１つ取り出して１つにする場合：
nC2*n-2C1=3 nC3
ケース１から３まで合計すると
| N(n, | n(n+1) 2 |
-1)＝3(nC3+nC4)=3 n+1C4 |
| 次はN(n, | n(n+1) 2 |
-2)を求めます。 |
2)Uグループから袋3つ取り出して１つにする場合：
nC2 n-2C2 n-4C2 = 90 nC6 通り
3)Tグループから袋2つ,Uグループから袋1つ取り出して１つにする場合：
nC2 n-2C2 = 6 nC4通りあります。
4)Uグループから袋2つ,Tグループから袋1つ取り出して１つにする場合：
| nC2 n-2C2 n-4C1 2！ | = 15 nC5 通り |
5)Tグループから袋2つ取り出して１つにして、Uグループから袋2つ取り出して１つにする場合：
ケース３と同じになりますので＝０通り
6)Uグループから袋2つ取り出して１つにして、UとTグループからそれぞれ袋１つ取り出して１つにする場合：
| nC2 n-2C2 2！ | (nC2-2) n-2C1 = 3 nC4 (nC2-2)(n-2)通り |
7)Tグループから袋2つ取り出して１つにして、UとTグループからそれぞれ袋１つ取り出して１つにする場合：
ケース1と同じになりますので＝０通り
8)UとTグループからそれぞれ袋１つ取り出して１つにすることを2回する場合：
(この場合は１回目は[AB][C]->[ABC]で、
２回目[CD][E]->[CDE]または[DE][F]->[DEF]、
つまりUグループの２回目とTグループの１回目の中身はすべてちがう商品かどうか２つのケースに分けられます)
| nC2 n-2C1 [nC2-n-1C1-1][n-2C1-1]+nC2 n-2C1 n-1C1 n-2C1 2！ |
| =3 nC3 | n(n-3)2+2(n-1)(n-2) 4 |
通り |
合計すると
| N(n, | n(n+1) 2 |
-2) |
| =90 nC6+15 nC5+6 nC4+nC3+3 nC4(nC2-2)(n-2)+3 nC3 | [n(n-3)2+2(n-1)(n-2)] 4 |
n=4の場合,
N(4,5),N(4,6),N(4,7),N(4,8),N(4,9),N(4,10)があります。
| N(n,n+1),N(n,n+2),N(n,n+3),N(n, | n(n+1) 2 |
),N(n, | n(n+1) 2 |
-1),と |
| N(n, | n(n+1) 2 |
-2)の式を使って計算すると |
N(4,5)=1,N(4,6)=15,N(4,7)=70,
N(4,8)=82 ,N(4,9)=15,N(4,10)=1
合計＝1+15+70+82+15+1=184通りです。
◆出題者のコメント。
解答ありがとうございます。
福袋の数が最少の時から、順々に商品を新しい福袋に移していく発想は面白いですね。
ただ、Ｎ＝４の時ですが、１８４通りより多くなります。
以下、Ｎ＝４の時をシラミ潰しで確認した方法を示します。
各福袋は同じ商品を複数入れられないので、最大４個までしか商品は入れられません。
しかも、同じ福袋は許されないので、
４個入り,３個入り,２個入り,１個入りの福袋は、
それぞれ
１個(4Ｃ4)まで,
４個(4Ｃ3)まで,
６個(4Ｃ2)まで,
４個(4Ｃ1)までしか作ることはできません。
これは４個,３個,２個,１個の商品で作成可能な福袋の種類の数です。
一方、すべての福袋における全商品の数は１６個(４2)です。
そこで各福袋を、中にある商品の数で表すと、４を１回まで、３を４回まで、２を６回まで、１を４回まで使用することを許して、
１６を４,３,２,１の４種類以下の数字の和で表す方法になります。
以下、＋を省略しています。
４３３３３ ４３３３ ２ １ ・・・ １２通り ４３３３ １１１ ４３３ ２２２ ・・・ １２通り ４３３ ２２ １１ ・・・ ４２通り ４３３ ２ １１１１ ４３ ２２２２ １ ・・・ ２４通り ４３ ２２２ １１１ ４ ２２２２２２ ４ ２２２２２ １１ ４ ２２２２ １１１１ ・・・ ３通り ３３３３２２ ・・・ ３通り ３３３３２ １１ ３３３３ １１１１ ３３３ ２２２ １ ３３３ ２２ １１１ ・・・ ２４通り ３３ ２２２２２ ３３ ２２２２ １１ ・・・ ４２通り ３３ ２２２ １１１１ ・・・ １２通り ３ ２２２２２２１ ３ ２２２２２ １１１ ・・・ １２通り ２２２２２２１１１１ところが、ここで３,２,１で示した福袋は実際には４種類,６種類,４種類ありますから、各行をさらに場合分けする必要があります。
求めた結果の１部を右側に示しましたが、
示した分だけでも既に１８６通りになります。
（面白いことにそれぞれの場合の数は上下対称になります）
◆宮城県 アンパンマン さんからの解答。
ｎ＝４の時、シラミ潰しで求めた結果です。
４３３３３ １通り ４３３３ ２ １ ・・・ １２通り ４３３３ １１１ ４通り ４３３ ２２２ ・・・ １２通り ４３３ ２２ １１ ・・・ ４２通り ４３３ ２ １１１１ ６通り ４３ ２２２２ １ ・・・ ２４通り ４３ ２２２ １１１ ２８通り ４ ２２２２２２ １通り ４ ２２２２２ １１ ６通り ４ ２２２２ １１１１ ・・・ ３通り ３３３３２２ ・・・ ３通り ３３３３２ １１ ６通り ３３３３ １１１１ １通り ３３３ ２２２ １ ２８通り ３３３ ２２ １１１ ・・・ ２４通り ３３ ２２２２２ ６通り ３３ ２２２２ １１ ・・・ ４２通り ３３ ２２２ １１１１ ・・・ １２通り ３ ２２２２２２１ ４通り ３ ２２２２２ １１１ ・・・ １２通り ２２２２２２１１１１ １通りN(４、５)＝N(４、１０)＝１、
合計＝１＋２７＋１１１＋１１１＋２７＋１＝２７８通りです。
ちなみに、
| N(n, | n(n+1) 2 |
-1) |
| ＝3(nC3+nC4)＋ | nC6 6! (2!3) 3! |
･ | 6C3 2! |
＋ | 3 nC3 n-3C2 4C2 2! |
＋nC4 4C2 2C1 |
| ＝3 nC3+15 nC4+90 nC5+150 nC6 |
| (これは前回の解答から求めた | N(n, | n(n+1) 2 |
-1) | の値にケース４の数を加える) |