ナンバーズ4の各桁の合計数がNで、順序を無視するときの場合の数

質問

http://oshiete1.goo.ne.jp/qa4407454.html
で次のように書いてありました。

各桁の合計値が N になるようなナンバーズ4の組み合わせ
のパターン数をf(N)とすると、f(N)は x の多項式
(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^4
の展開式の x^N の係数です。したがって、
f(N)=Σ[k=0,floor(N/10)]((-1)^k)*4*(3+N-10k)!/(k!*(4-k)!*(N-10k)!)
となります。
( floor(a)は a を超えない最大の整数を表します。)

これは、
(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)(1+y+y^2+y^3+y^4+y^5+y^6+y^7+y^8+y^9)(1+z+z^2+z^3+z^4+z^5+z^6+z^7+z^8+z^9)(1+w+w^2+w^3+w^4+w^5+w^6+w^7+w^8+w^9)

を考え、例えば項 x^2*y^5*z^3*1 を４桁の数2530に対応させたものと思います。

ここで、数字の並び方の順序を無視し、たとえば、1112と2111を同じとみなします。もしくは、
「千の位の数」≦「百の位の数」≦「十の位の数」≦「一の位の数」
といった制限を加えます。
さっきのが、順列なのに対し、今回のは組合せです。

このとき各桁の合計値が N になるような4種類の数の組み合わせは、どのように書けるのでしょうか？

回答No.4

20080715 · ベストアンサー

＞今回の質問は、それらをミックスしたようなものでしたが、
＞漸化式はあるのかなあと考えています。

q-2項係数を[n,k]というように書くことにします。
次の等式が成り立ちます。
[n,k]=[n-1,k]+q^(n-k)*[n-1,k-1] ------(1)
http://ocw.mit.edu/NR/rdonlyres/Mathematics/18-318Spring-2006/9E1C3273-156D-4145-BFAC-CA355E746873/0/young.pdf

0≦a[1]≦a[2]≦…≦a[k]≦j かつ a[1]+a[2]+…+a[k]=n
を満たす整数の組(a[1],a[2],…,a[k])の個数を p(j,k,n) とします。
Σp(j,k,n)*q^n = [j+k,j] ------(2)
が成り立ちます。

(1),(2)より、
n≧kのとき、
p(j,k,n)=p(j,k-1,n)+p(j-1,k,n-k)
が成り立ちます。

＞正の整数 n を k 個の正の整数の和として表す方法の総数p(n,k)とすると、
＞p(n,4)くらいまでは明示式があるようです。

任意の正整数kに対してp(n,k)を床関数を使って書き表すことができます。
たとえば、
p(n,5)=(1/120)*((1/24)*(n+6)*(n+7)*(n+8)*(n+9)+(-20)*(floor(n/2+1/2))^3/3+5*(2*n+3)*(floor(n/2+1/2))^2-5*(3*n^2+9*n+5)*floor(n/2+1/2)/3-5*(3*n^2+27*n+68)+(15/2)*(floor((n+9)/2)-1)*(floor((n+9)/2))+(-10)*(floor((n+8)/3))*(3*(floor((n+8)/3))-2*n-15)+(-20)*floor((1/2)*(floor((n+8)/3)+(1-(-1)^n)/2))+(-30)*floor((n+9)/4)+24*(floor(n/5)-floor((n-1)/5))),

p(n,6)=(1/720)*((1/120)*(n+10)*(n+11)*(n+12)*(n+13)*(n+14)+(5/2)*(floor((n+11)/2))*(2*(floor((n+11)/2))^3-4*(floor((n+11)/2))^2*(n+12)+(floor((n+11)/2))*(3*n^2+72*n+430)-n^3-2*(18*n^2+215*n+852))+(-45/6)*(floor((n+13)/2))(4*(floor((n+13)/2))^2-3*(n+14)*floor((n+13)/2)+3*n+38)+60*floor(n/3)^3-60*n*floor(n/3)^2+20*(n^2-1)*floor(n/3)+80*(n^2+12*n+47)+180*(floor((n+1)/4))^2-90*n*floor((n+1)/4)-270*(n + 6)+(-15/16)*(1-(-1)^n)*(n+11)*(n+13)+144*floor((n+14)/5)+45*(1-(-1)^n)*floor((n+13)/4)+40*(floor(n/3)-floor((n-1)/3))*floor((n+12)/3)+(-120)*(floor((n+15)/6)-floor((n+14)/6))+(-120)*(floor((-n-15)/6)-3*(floor((n+15)/6))^2+(n+13)*floor((n+15)/6)+1))

お礼

本当に感謝いたします。

0≦a[1]≦a[2]≦…≦a[k]≦j かつ a[1]+a[2]+…+a[k]=n
を満たす整数の組(a[1],a[2],…,a[k])の個数を p(j,k,n) すると、
Σp(j,k,n)*q^n = [j+k,j]

すごいですね。まだ理解するには至っていませんが、不定方程式の解の個数についていろいろ考えていました。例えば、

α[1]+α[2]+…+α[n]=k、かつ、α[i]=0または1
を満たす解の個数は二項係数、C(n,k)

α[1]+α[2]+…+α[k+1]=n+1、かつ、α[i]≧1
を満たす自然数解の個数は二項係数、C(n,k)

α[1]+α[2]+…+α[n]=k、かつ、α[i]≧0
を満たす整数解の個数は重複組合せ、H(n,k)

α[1]+α[2]+…=n、かつ、α[i]=1または2
を満たす整数解の個数をT[n]とすると、T[n]=T[n-1]+T[n-2]が成立し、フィボナッチ数列F[n]と比べると、T[n]=F[n+1]
さらに、Σ[n=0,∞]T[n]z^n=1/(1-z-z^2)となるので、それから少し考察することで、
T[n]=Σ[β[1]+2*β[2]=nの0以上の整数解] {C(β[1]+β[2],β[1])}
------(*)
が分かる。
例えばn=3のとき、
α[1]+α[2]+…=3、かつ、α[i]=1または2
の解は、3=1+1+1=1+2=2+1より３通りあるので、T[3]=3
このとき、
Σ[β[1]+2*β[2]=3の0以上の整数解] {C(β[1]+β[2],β[1])}
=Σ[(β[1],β[2])=(1,1),(3,0)] {C(β[1]+β[2],β[1])}
=C(2,1)+C(3,0)
=3
となり確かに成立している。

このことと比べて下記のことを悩んでおります。

f:{1,2,…,n}→{1,2,…,k}の全射の個数k!*S(n,k)を考えると、
Σ[n=0,∞] k!*S(n,k)x^n = k!*x^k/(1-x)(1-2x)…(1-kx)
つまり、
Σ[a[1]+a[2]+a[3]+…+a[k]=nの自然数の解]1^(a[1])*2^(a[2])*3^(a[3])*…*k^(a[k]) = k!*S(n,k)

これを、(*)の右辺に対応するものとすると、(*)の左辺に対応するものは何でしょうか？
全射の個数k!*S(n,k)を、不定方程式の解の個数「のみ」で書くことはできるのでしょうか？

回答No.3

20080715

漸化式を作って u(x,k) を求める方法は
次の本に書いてありました。
『 INTRODUCTION TO COMBINATORIAL ANALYSIS 』(Dover)
(この本の chapter6, problems 7 )

次のページも参考になると思います。
http://ja.wikipedia.org/wiki/Q%E4%BA%8C%E9%A0%85%E5%AE%9A%E7%90%86
(コーシーの二項定理)

正の整数 n を k 個の正の整数の和として表す方法の総数を
p(n,k)とすると、
p(n,4)=floor((2*n^3+6*n^2-9*(1-(-1)^n)*n+144)/288)
となるようです。
http://oshiete1.goo.ne.jp/qa1478775.html
このことから 1/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)) を級数展開したときの
x^k の係数は p(n+4,4).
これを使えば F(N) を床関数のみを用いて書くこともできるとは思います。

お礼

たびたびありがとうございます。
正の整数 n を k 個の正の整数の和として表す方法の総数p(n,k)とすると、p(n,4)くらいまでは明示式があるようです。
http://mathworld.wolfram.com/PartitionFunctionP.html
また、p(n,k)=p(n-1,k-1)+p(n-k,k)
という漸化式もあるようです。
母関数は、
Σ[n=0,∞]p(n,k)x^n=x^k/(1-x)(1-x^2)…(1-x^k)
なのですね。

また、正の整数 n を 正の整数 1,2,…,a のみを使った和として表す方法の総数をq(n,a)とすると、
母関数は、
Σ[n=0,∞]q(n,a)x^n=1/(1-x)(1-x^2)…(1-x^a)
漸化式は、
q(n,a)=q(n,a-1)-q(n-a,a)
となると思います。

今回の質問は、それらをミックスしたようなものでしたが、漸化式はあるのかなあと考えています。

回答No.2

20080715

後半部分は説明不足でした。補足しておきます。

0≦a≦b≦c≦d≦9 かつ a+b+c+d=N は変形すると、
1≦(a+1)＜(b+2)＜(c+3)＜(d+4)≦13 かつ (a+1)+(b+2)+(c+3)+(d+4)=N+10
となります。
よって F(N) は、x, y の多項式
(1+x*y)*(1+x^2*y)*(1+x^3*y)*……*(1+x^13*y)
の展開式の x^(N+10)*y^4 の係数に等しいです。
g(x,y)=(1+x*y)*(1+x^2*y)*(1+x^3*y)*……*(1+x^13*y)とおくと、
(1+x^14*y)*g(x,y)=(1+x*y)*g(x,x*y) ------(☆) が成り立ちます。
g(x,y)の展開式の y^k の係数を u(x,k) とします。
g(x,y)=Σu(x,k)*y^k, g(x,x*y)=Σx^k*u(x,k)*y^k です。
これらを(☆)に使って、両辺の y^k の係数を比べると、
u(x,k)+x^14*u(x,k-1)=x^k*u(x,k)+x^k*u(x,k-1).
よって、
u(x,k)=(x^k*(1-x^(14-k))/(1-x^k))*u(x,k-1).
この関係式を使って、
u(x,k)=x^(k*(k+1)/2)*(1-x^13)*(1-x^12)*……*(1-x^(13-k+1))/((1-x)*(1-x^2)*……*(1-x^k)).
特に、u(x,4)=x^10*(1-x^13)*(1-x^12)*(1-x^11)*(1-x^10)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)).

F(N)
=( u(x,4) の x^(N+10) の係数 )
=coef(N,(1-x^13)*(1-x^12)*(1-x^11)*(1-x^10)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4))).

お礼

ありがとうございます。
たいへんよく分かりました。
二変数にすることとか、漸化式にすることとかとても巧妙ですね。

僕も計数子のこととかを勉強したり、
クヌースのコンピューターの数学という本を借りて読んだりしていましたが、このようなことは知りませんでした。

回答No.1

20080715

0≦a≦b≦c≦d≦9 かつ a+b+c+d=N を満たすような
非負整数の組(a,b,c,d)が何組あるか、ということですね。

この条件を満たすような非負整数の組(a,b,c,d)の個数を
F(N)とすると、
F(N)=Σ[a=max(0,N-27),min(9,floor(N/4))]Σ[b=max(a,N-a-18),min(9,floor((N-a)/3))]Σ[c=max(b,N-a-b-9),min(9,floor((N-a-b)/2))]1.

あるいは、
x の多項式 G(x) の x^k の係数を coef(k,G(x)) というように書くことにすれば、
F(N)=coef(N,(1-x^13)*(1-x^12)*(1-x^11)*(1-x^10)/((1-x)*(1-x^2)*(1-x^3)*(1-x^4))).

補足

まことにありがとうございます。
前半は理解できました。
後半の係数のことがよくわかりません。
分母は、分割数p(n)での母関数と似ているのには気づきますが、
分子はどういう意味なのでしょうか?