で飲むことに決めている。各銘柄の代金は、100、200、300、400(円)であるとする。
A氏のお小遣いが、1500(円)としたとき、お小遣いを使い切ったとき、少なくとも全部の銘柄
を飲み終えるためには、A氏のお金の使い方は何通り考えられるか？
(日によって支払う金額が異なれば違う方法とカウントして下さい。)
(コメント） 何となく計算してみた。
・１００×６＋２００×１＋３００×１＋４００×１＝１５００ の場合
それぞれの出方の総数は、 ９・８・７＝５０４（通り）
・１００×４＋２００×２＋３００×１＋４００×１＝１５００ の場合
それぞれの出方の総数は、 8Ｃ2・６・５＝８４０（通り）
・１００×３＋２００×１＋３００×２＋４００×１＝１５００ の場合
それぞれの出方の総数は、 7Ｃ2・５・４＝４２０（通り）
・１００×２＋２００×１＋３００×１＋４００×２＝１５００ の場合
それぞれの出方の総数は、 6Ｃ2・４・３＝１８０（通り）
・１００×２＋２００×３＋３００×１＋４００×１＝１５００ の場合
それぞれの出方の総数は、 7Ｃ3・４・３＝４２０（通り）
・１００×１＋２００×２＋３００×２＋４００×１＝１５００ の場合
それぞれの出方の総数は、 6Ｃ2・4Ｃ2・２＝１８０（通り）
以上から、求める場合の数は、
５０４＋８４０＋４２０＋１８０＋４２０＋１８０＝２５４４（通り）
ＧＡＩ さんからのコメントです。（令和６年８月２６日付け）
正解です。
kuiperbelt さんからのコメントです。（令和６年８月２６日付け）
X、Y、Z、W の銘柄を1回ずつ飲むと、100+200+300+400=1000円 で、残りの500円を分配
する方法は、
XW、YZ、XXZ、XYY、XXXY、XXXXX の６つの場合があり、
XYZWとXWの場合、6!/(2!*1!*1!*2!)=180（通り）
XYZWとYZの場合、6!/(1!*2!*2!*1!)=180（通り）
XYZWとXXZの場合、7!/(3!*1!*2!*1!)=420（通り）
XYZWとXYYの場合、7!/(2!*3!*1!*1!)=420（通り）
XYZWとXXXYの場合、8!/(4!*2!*1!*1!)=840（通り）
XYZWとXXXXXの場合、9!/(6!*1!*1!*1!)=504（通り）
より、合計 180+180+420+420+840+504=2544（通り）
ＧＡＩ さんからのコメントです。（令和６年８月２７日付け）
これを一般化して、n(円)の資金をもって、毎日単価が 1、2、3、･･･、k (円) （ただし、k＜n）
の各ビールの銘柄をどれか一つずつ毎日飲んでいき、資金を使い果たしたとき、少なくとも
全銘柄のビールは飲んだことが起こるお金の使い方の方法は総計どれだけ？これを明示式
で示せるか？または、これを読み取れる母関数は作れるのか？
ちなみに、k=2 のとき、gf=1+1/(1-x-x^2)-1/(1-x)-1/(1-x^2)
k=3 のとき、
gf= x^6/(1-x-x^2-x^3)*(1/((1-x)*(1-x-x^2))+1/((1-x^2)*(1-x-x^2))+1/((1-x)*(1-x-x^3))
+1/((1-x^3)*(1-x-x^3))+1/((1-x^2)*(1-x^2-x^3))+1/((1-x^3)*(1-x^2-x^3)))
k=4 のときの母関数は如何に？どなたかヒントを
ａｔ さんからのコメントです。（令和６年８月２８日付け）
お金の使い方の総数をa(n)とすると、a(n)は次の式で計算できます。
a(n)=[x^n](∫_[z=0,∞]exp(-z)*Π[j=1〜k](exp(x^j*z)-1)dz)．
例えば、k=4 の場合：
exp(-z)*Π[j=1〜4](exp(x^j*z)-1)を展開すると、次のようになります。
exp(-z)*Π[j=1〜4](exp(x^j*z)-1)
=exp(-z)*(exp(x*z)-1)*(exp(x^2*z)-1)*(exp(x^3*z)-1)*(exp(x^4*z)-1)
=exp((-1+x+x^2+x^3+x^4)*z)
-exp((-1+x+x^2+x^3)*z)-exp(-1+x+x^2+x^4)-exp(-1+x+x^3+x^4)-exp(-1x^2+x^3+x^4)
+exp((-1+x+x^2)*z)+exp((-1+x+x^3)*z)+exp((-1+x+x^4)*z)+exp((-1+x^2+x^3)*z)
+exp((-1+x^2+x^4)*z)+exp((-1+x^3+x^4)*z)-exp((-1+x)*z)-exp((-1+x^2)*z)-exp((-1+x^3)*z)
-exp((-1+4)*z)+exp((-1)*z).
この展開式を z=0〜∞ の範囲で積分すれば、x の有理関数が得られます。その有理関数
をマクローリン展開したときのx^nの係数がa(n)です。
a(n)
=[x^n](-1/(-1+x+x^2+x^3+x^4)
+1/(-1+x+x^2+x^3)+1/(-1+x+x^2+x^4)+1/(-1+x+x^3+x^4)+1/(-1+x^2+x^3+x^4)
-1/(-1+x+x^2)-1/(-1+x+x^3)-1/(-1+x+x^4)-1/(-1+x^2+x^3)-1/(-1+x^2+x^4)-1/(-1+x^3+x^4)
+1/(-1+x)+1/(-1+x^2)+1/(-1+x^3)+1/(-1+x^4)
-1/(-1)).
ＧＡＩ さんからのコメントです。（令和６年８月２８日付け）
at さん凄いです。
仕方なく n=10 から 20 までの数値をひとつずつ算出して（御蔭で結果的に１ヵ所計算ミスを
起こしていることを発見)、k=3での母関数を真似して色々試していたんですが、そのすべてが
弾かれてしまい、途方に暮れていました。
最初の項だけが一致しているが後は無駄な努力でした。
積分の力で解決されるとは思ってもない道筋でした。最終型は、集合の要素の個数を求め
る式に類似していますね。（結構覚え易い)
ということは、k=3 での母関数gfはよりスッキリした
1/(1-x-x^2-x^3)-1/(1-x-x^2)-1/(1-x-x^3)-1/(1-x^2-x^3)+1/(1-x)+1/(1-x^2)+1/(1-x^3)-1
でも可能というわけですね。
世の中には物事の本質を見事に掴んでしまう人がいることに感激です。目から鱗でこんな
一般式まで分かってしまうことが驚異でうれしいです。大変ありがとうございました。
母関数の形にしなくても、コンピュータで数値だけ求めたいなら直接積分型から
gp > F(k)=intnum(z=0,[oo,1],exp(-z)*prod(j=1,k,exp(x^j*z)-1))
で定義しておけば、k=9 での値は、
gp > for(n=45,60,print(n";"round(polcoeff(F(9),n))))
45;362880
46;1814400
47;8467200
48;31752000
49;110255040
50;352416960
51;1073580480
52;3125969280
53;8808347520
54;24105906720
55;64431521280
56;168662148480
57;433730626560
58;1097903933280
59;2740858737120
60;6757827995520
等で、一発で求まっていくのですね。（あのめんどくさい作業が夢のようです。)
kuiperbelt さんからのコメントです。（令和６年８月２９日付け）
毎日単価が1円か2円の各ビールの銘柄をどれか一つずつ毎日飲むときの場合の数の生
成関数については、
1+(x+x^2)+(x+x^2)^2+…=1/(1-x-x^2)
で表され、少なくとも両銘柄のビールを飲んだときの場合の数の生成関数については、
(1+(x+x^2)+(x+x^2)^2+…)-(1+x+x^2+…)-(1+x^2+x^4+…)+1
=1/(1-x-x^2)-1/(1-x)-1/(1-x^2)+1
で表されます。
(x+x^2)^m=C(m,0)x^m+C(m,1)x^(m+1)+...+C(m,j)x^(m+j)+...+C(m,m)x^(2m)
なので、n(円)の資金をもって毎日単価が1円か2円の各ビールの銘柄をどれか一つずつ毎
日飲んでいき、資金を使い果たしたときのお金の使い方の方法の数は、
Σ_{k=0〜floor(n/2)}C(n-k,k)
で表され、少なくとも両銘柄のビールを飲んだときの場合の数については、
n=2q+1のとき、Σ_{k=0〜floor(n/2)}C(n-k,k) - C(n,0)
n=2qのとき、Σ_{k=0〜floor(n/2)}C(n-k,k) - C(n,0) -C(q,q)
となります。F(n)=Σ_{k=0〜floor(n/2)}C(n-k,k)とすると、F(1)=1、F(2)=2、F(n)=F(n-1)+F(n-2)
となって、F(n)はフィボナッチ数列となります。
少なくとも両銘柄のビールを飲んだときの場合の数については、
n=2q+1のときF(n)-1、n=2qのときF(n)-2となります。
毎日単価が1円、2円、3円の各ビールの銘柄をどれか一つずつ毎日飲むときの場合の数
の生成関数については、
1+(x+x^2+x^3)+(x+x^2+x^3)^2+…=1/(1-x-x^2-x^3)
で表され、少なくとも全銘柄のビールを飲んだときの場合の数の生成関数については、
(1+(x+x^2+x^3)+(x+x^2+x^3)^2+…)
-(1+(x+x^2)+(x+x^2)^2+…)-(1+(x+x^3)+(x+x^3)^2+…)-(1+(x^2+x^3)+(x^2+x^3)^2+…)
+(1+x+x^2+…)+(1+x^2+x^4+…)+(1+x^3+x^6+…)-1
=1/(1-x-x^2-x^3)-1/(1-x-x^2)-1/(1-x-x^3)-1/(1-x^2-x^3)+1/(1-x)+1/(1-x^2)+1/(1-x^3)-1
で表されます。
２項係数C(n,k)に倣って3項係数C(n,k1,k2)=n!/(k1!k2!(n-k1-k2)!)を用いると、
(x+x^2+x^3)^m=Σ_{k1≧0,k2≧0,k1+k2≦m}C(m,k1,k2)[x^(m-k1-k2)*x^(2*k1)*x^(3*k2)]
なので、n(円)の資金をもって毎日単価が1円、2円、3円の各ビールの銘柄をどれか一つず
つ毎日飲んでいき、資金を使い果たしたときのお金の使い方の方法の数は、
T(n)=Σ_{i=0〜floor(n/2),j=0〜floor(n/3),i+j≦n}C(n-i-j,i,j)
で表され、T(1)=1、T(2)=2、T(3)=4、T(n)=T(n-1)+T(n-2)+T(n-3) というトリボナッチ数列とな
ります。
n(円)の資金をもって毎日単価が1円か3円の各ビールの銘柄をどれか一つずつ毎日飲ん
でいき、資金を使い果たしたときのお金の使い方の方法の数については、
(x+x^3)^m=C(m,0)x^m+C(m,1)x^(m+2)+...+C(m,j)x^(m+2*j)+...+C(m,m)x^(3m)
より、
n=1 のとき、C(1,0)
n=2 のとき、C(2,0)
n=3 のとき、C(3,0)+C(1,1)
n=4 のとき、C(4,0)+C(2,1)
n=5 のとき、C(5,0)+C(3,1)
n=6 のとき、C(6,0)+C(4,1)+C(2,2)
n=7 のとき、C(7,0)+C(5,1)+C(3,2)
n=8 のとき、C(8,0)+C(6,1)+C(4,2)
となって、一般には、
Σ_{k=0〜floor(n/3)}C(n-2*k,k)
で表され、Σ_{k=0〜floor(n/3)}C(n-2*k,k)=G(n+1) とすると、
G(1)=1、G(2)=1、G(3)=2、G(n)=G(n-1)+G(n-3) となって、これはナラヤナ数列(Narayana sequence)
といいます。
n(円)の資金をもって毎日単価が2円か3円の各ビールの銘柄をどれか一つずつ毎日飲ん
でいき、資金を使い果たしたときのお金の使い方の方法の数については、
(x^2+x^3)^m=C(m,0)x^2m+C(m,1)x^(2m+1)+...+C(m,j)x^(1m+j)+...+C(m,m)x^(3m)
より、
n=2 のとき、C(1,0)
n=3 のとき、C(1,1)
n=4 のとき、C(2,0)
n=5 のとき、C(2,1)
n=6 のとき、C(3,0)+C(2,2)
n=7 のとき、C(3,1)
n=8 のとき、C(4,0)+C(3,2)
n=9 のとき、C(4,1)+C(3,3)
n=10 のとき、C(5,0)+C(4,2)
n=11 のとき、C(5,1)+C(4,3)
n=12 のとき、C(6,0)+C(5,2)+C(4,4)
となって、一般には、
Σ_{ceil(n/3)≦k≦floor(n/2)}C(k,n-2*k)
で表され、これをH(n)とすると、H(2)=1、H(3)=1、H(4)=1、H(n)=H(n-2)+H(n-3) となって、これ
はパドヴァン数列(Padovan sequence)といいます。
n(円)の資金をもって毎日単価が1円、2円、3円の各ビールの銘柄をどれか一つずつ毎日
飲んでいき、資金を使い果たしたとき、少なくとも全銘柄のビールを飲んだときのお金の使
い方の方法の数については、
T(n)-F(n)-G(n)-H(n)+r(n)
r(n)=3(n mod 6=0)、1(n mod 6=1,5)、2(n mod 6=2,3,4)
となります。n=1〜10で、
T(n) 1,2,4,7,13,24,44,81,149,274
F(n) 1,2,3,5, 8,13,21,34, 55, 89
G(n) 1,1,2,3, 4, 6, 9,13, 19, 28
H(n) 0,1,1,1, 2, 2, 3, 4, 5, 7
となりますが、T(n)-F(n)-G(n)-H(n)+r(n)は、n=1〜10で、0,0,0,0,0,6,12,32,72,152となります。
毎日単価が1円、2円、3円、4円の各ビールの銘柄をどれか一つずつ毎日飲むときの場合
の数の生成関数については、
1+(x+x^2+x^3+x^4)+(x+x^2+x^3+x^4)^2+…=1/(1-x-x^2-x^3-x^4)
で表され、少なくとも全銘柄のビールを飲んだときの場合の数の生成関数については、
(1+(x+x^2+x^3+x^4)+(x+x^2+x^3+x^4)^2+…)
-(1+(x+x^2+x^3)+(x+x^2+x^3)^2+…)-(1+(x+x^2+x^4)+(x+x^2+x^4)^2+…)
-(1+(x+x^3+x^4)+(x+x^3+x^4)^2+…)-(1+(x^2+x^3+x^4)+(x^2+x^3+x^4)^2+…)
+(1+(x+x^2)+(x+x^2)^2+…)+(1+(x+x^3)+(x+x^3)^2+…)+(1+(x^2+x^3)+(x^2+x^3)^2+…)
+(1+(x+x^4)+(x+x^4)^2+…)+(1+(x^2+x^4)+(x^2+x^4)^2+…)+(1+(x^3+x^4)+(x^3+x^4)^2+…)
-(1+x+x^2+…)-(1+x^2+x^4+…)-(1+x^3+x^6+…)-(1+x^4+x^8+…)+1
=1/(1-x-x^2-x^3-x^4)
-1/(1-x-x^2-x^3)-1/(1-x-x^2-x^4)-1/(1-x-x^3-x^4)-1/(1-x^2-x^3-x^4)
+1/(1-x-x^2)+1/(1-x-x^3)+1/(1-x^2-x^3)+1/(1-x-x^4)+1/(1-x^2-x^4)+1/(1-x^3-x^4)
-1/(1-x)-1/(1-x^2)-1/(1-x^3)-1/(1-x^4)
+1
で表されます。
以下、工事中！
