『Multinomial Sums』解答

◆愛知県　Y.M.Ojisan さんからの解答。

【おまけ１】

問題１．ｘの解答では途中でＭＬ展開からＰ０ＹＺに右辺計算の容易さから宗旨替えしましたが、おまけ１解答では右辺は計算できるものとして、ＭＬ展開で独立な生成式を求めます。

生成式として　＜a^S＞Ｍ^ｐＬ^q　　S+２ｐ＋３ｑ≦Dmax　S≧ｒ　の系列を考えます。
Ａr,i等は同じ定義です。

まず　a³＝a²＋M a＋L　であるので　
S≧ｒ＋３の生成式はS=ｒ、ｒ＋１、ｒ＋２の生成式の線形結合で表されるので、独立ではありません。

【おまけ補題１】

＜a^ｒ＞＝ΣＫ_ｒpqＭ^pＬ^q　for ２ｐ＋３ｑ≦ｒ とするとき

(１)Ｋ_ｒpq≧１

(２)Ｋ_ｒ00＝1 for ｒ＞１

∵
(1)＜a^ｒ＞=＜a^ｒ-1＞+＜a^ｒ-2＞*M+＜a^ｒ-3＞*L　より明らか。

(2)Ｋ₁₀₀=1　であり、Ｍ＝Ｌ＝０とすれば帰納的に成立。

【おまけ補題２】

＜a^R＞と＜a^R＋１＞と＜a^R＋２＞　(Ｒ≧０)は連続３個は互いに素である。
ここで素でないとは、定数でないＭＬの多項式 G(M,L)をそれぞれ因数に持つことである。

∵
始めの方である　＜a⁰＞=3，＜a¹＞=1，
＜a²＞=1＋２Ｍ，＜a^３＞=1＋３Ｍ＋３Ｌ，
＜a⁴＞=1＋４Ｍ＋４Ｌ＋２Ｍ²はそもそも因数分解できないので互いに素である。

以下 R≧３ とする。

まず　L＝0の場合を考える。
f(R)=＜a^R＞｜_L=0とする。
漸化式は

f(Ｒ)=f(Ｒ−１)+Ｍ*f(Ｒ−２)

いま f(Ｒ−１), f(Ｒ−２), f(Ｒ−３)は互いに素であるとする。
一般に【おまけ補題１】の(２)より、ｆ(R)の定数項は１である。
よって、Mとｆ(任意Ｒ)は互いに素である。

ｆ(Ｒ)とｆ(Ｒ−１)で互除法を行うと
Ｍ*f(Ｒ−２)とｆ(Ｒ‐1)の問題になり、
Ｍおよびｆ(Ｒ−２)とｆ(Ｒ‐1)は互いに素であるので
ｆ(Ｒ)とｆ(Ｒ−１)は互いに素である。

同様にｆ(Ｒ)とｆ(Ｒ−２)で互除法を行うと
ｆ(Ｒ−２)　と　ｆ(Ｒ‐1)の問題になり、
ｆ(Ｒ)とｆ(Ｒ−２)は互いに素である。

よって数学的帰納法によりｆ(Ｒ)、ｆ(Ｒ−１)、ｆ(Ｒ−２)は互いに素である。

以上より　＜a^r＞と＜a^S＞　
(Ｓとｒは　ＲまたはＲ−１またはＲ−２　であってＳ≠ｒ)
が互いに素で無いとすると、少なくとも公約数は
Ｍの単独べき乗項を含まない{１＋Ｌ*Ｖ１}　である。

これを用いて、以下の様に書ける。　
ここでＶ１，Ｖ２，Ｖ３はＭ，Ｌの多項式である。

＜a^r＞＝　{１＋Ｌ*Ｖ１}*Ｖ２

＜a^S＞＝　{１＋Ｌ*Ｖ１}*Ｖ３

【おまけ補題１】の(1)より

＜ar＞のＭの

[

r 2

]乗の項の係数は１以上である。

Ｌ*Ｖ１*Ｖ２の項からＭの単独冪項は出てこない。

よって、Ｖ２のＭの[

r 2

]乗の項は０ではない。

このとき　右辺の　Ｌ*Ｖ１*Ｖ２の項から　ＬＭ^[r/2]　の項が登場し、

次数が　3+[

r 2

]*2≧r+2になり、左辺の次数ｒを超える。

従って、Ｖ１＝０でなければならない。

よって、＜a^r＞と＜a^S＞は互いに素である。

以上を　(r=R S=R-1) (r=R-1 S=R-2) (r=R S=R-2) の場合にそれぞれ適用することにより
＜a^R＞と＜a^R+1＞と＜a^R+2＞は互いに素であるといえる。

∵【おまけ補題３】

(1)＜a^S＞Ｍ^pＬ^q(S：一定、p、q：任意　)の集合において全要素は独立である。

(2)＜a^S＞Ｍ^pＬ^q(S：一定、p、q：任意　)の集合をベースに
＜a^S’＞Ｍ^p’Ｌ^q’ (Ｓ’：一定≠Ｓ、p’、q’：任意　)の集合から独立でないものを省くと　
＜a^S＞と＜a^S’＞が互いに素であるとき、

｛独立な＜a^S’＞Ｍ^ｐ’Ｌ^q’ の集合｝
＝＜a^S’＞｛｛＜a^S＞の展開項から１つ選んだもの｝を部分的にでも含まない項の集合｝　である。

∵
(1) ＜a^S＞Ｍ^ｐＬ^qは元々独立なＭ^pＬ^qの一様に＜a^S＞倍したものであるから互いに独立です。

(2) 　独立ではない＜a^S’＞Ｍ^p’Ｌ^q’　は　下記式であらわされる。

＜a^S’＞Ｍ^p’Ｌ^q’＝Ｖ１＜a^S＞＋Ｖ２＜a^S’＞　

ここで　Ｖ２、Ｖ１はＭＬの多項式で　Ｖ２はＭ^p’Ｌ^q’の項を含まない。

変形すると、　

｛Ｖ２’｝＜a^S’＞＝｛Ｖ１｝＜a^S＞

ここで　Ｖ２’はＭ^ｐ’Ｌ^q’の係数が１の任意のＭＬの多項式となる。

＜a^S＞と＜a^S’＞は互いに素であるので、最小次数の　Ｖ１，Ｖ２’は

Ｖ１＝＜a^S’＞　Ｖ２’＝＜a^S＞

である。

従って、＜a^S＞の項のうちの一つの項Ｍ^ｐ’Ｌ^q’を除く
その他の項×＜a^S’＞は独立である。

さらに　Y≧0 　Z≧0　に対して　
Ｍ^Ｙ＋ｐ’Ｌ^Ｚ＋ｑ’の項×＜a^S’＞は独立でない。

【例題１】

r＝３ の場合　

＜a³＞=1+３Ｍ+３Ｌ　であるので　Ｌを＜a⁴＞の系列から独立でない物として消すと、

＜a³＞｛1 M　M²　L｝ 　＜a⁴＞｛1 M ｝ は独立です。
ただしＤｍａｘ＝７。

＜a⁵＞のほうも　＜a⁵＞｛1 M ｝が残りますが、
さらに＜a⁴＞により省く必用があります。

しかし、＜a^４＞=1＋４Ｍ＋４Ｌ＋２Ｍ²であって、
省けるものは　使用済みのＬか候補が無いＭ²であり、
＜a⁵＞｛1 M ｝は独立です。

なお、Ｍを消してもＭ²が増えるので意味が無い。

従って　　Ne(７)＝8とこれらの数が一致します。
これは先の解答と同じ結果です。

【例題２】

r＝４ の場合

６次をベースとし　Ｄｍａｘ＝１０として　
＜a⁶＞＝１＋６M＋６L＋９M²＋１２ML＋２M³＋３L²であるので　
Ｌ²を独立でない物として＜a^５＞の系列から省くと

＜a⁶＞｛　1 M M² Ｌ｝
＜a⁵＞｛　1 M M²　L 　Ｍ　Ｌ ｝が独立で、

＜a⁴＞｛　1 M M² M³L　Ｍ　Ｌ　｝は候補です。

＜a⁵＞=1+５Ｍ+５Ｌ+５Ｍ²+５ＭＬ　より　ＭＬを＜a^４＞の集合から消去すると

＜a⁴＞｛　1 M M² M³　L｝が独立なものとして残ります。

Ne(１０)＝１４とこれらの数が一致します。
これは先の解答と同じ結果です。

【r＝一般 の場合】

＜a^r＞＜a^r+1＞と＜a^r+2＞は【おまけ補題３】により互いに素です。

従って【おまけ補題３】　が適用可能です。
しかし、一般の場合にはｒ＝３，４の例のようには一つ一つ省いて行けません。

特に問題は＜a^r＞と＜a^r+1＞で＜a^r+2＞を処理するときです。

従って、

V１＜a^r+1＞＝Ｖ２＜a^r＞

V３＜a^r+2＞＝Ｖ４＜a^r＞

V５＜a^r+2＞＝Ｖ６＜a^r+1＞

のままで処理します。ここでV＊はMLの多項式で【おまけ補題３】より

V１、V3は＜a^r＞の倍数　V2、V5は＜a^r+1＞の倍数　
V４、V６は＜a^ｒ+2＞の倍数です。

Dmaxを共通の最大次数とします。

たとえば、下図の黄色部分を＜a^r+2＞に対するMlL展開要素の候補とします。

従って、Dmax-(ｒ＋２)次以下のML展開の全項です。

この中から、Ｖ４＜a^ｒ＞またはＶ６＜a^r+1＞を見つけることが、独立でない関係を見つけることであり、
さらにそれは
＜a^r＞のML展開項に対応した下図中の赤枠(ｒ例＝３)、
＜a^ｒ＞のML展開項に対応した青枠(ｒ＋１例＝４)
を見つけることと等価であり、それがいくつ含まれるかが独立でない要素の数になります。

なお、下図のような三角領域のパターンを簡単のために　Δ(D)　で表します。

下図はΔ(１４)です。
【おまけ補題１】の(１)から＜a^D＞のML展開項は全て０でなく、Δ(D)と対応します。

まとめると、

(１)＜a^r＞の系列はDmax-(ｒ)次以下のML展開の全項を採用します。

(２)＜a^r+1＞の系列はDmax-(ｒ＋１)次以下のML展開の全項からのそのパターン
Δ(Dmax-(ｒ＋１))中に含まれるΔ(ｒ)の個数を間引いたものを採用します。

(３)＜a^r+2＞の系列はDmax-(ｒ＋２)次以下のML展開の全項からのそのパターン
Δ(Dmax-(ｒ＋２))中に含まれるΔ(ｒ)の個数＋Δ(ｒ＋１)の個数を間引いたものを採用します。

そうするとこれらは独立です。
以上より｜Q｜≠０であるQが作成でき、漸化式が得られます。

実際には下図のように省きます(赤紫、緑のセル)。
ｒが奇数のときなど若干複雑です。

【必用なＤｍａｘ値】

　Ｎｅ(Ｄ)は周期６の変動をするので、下記表にしました。

D mod 6	0	1	2	3	4	5
Ne(D)-( D2 12 + D 2 )	1	5 12	8 12	9 12	8 12	5 12

結局　Ne(D)=[

D2+6D+12 12

] でよいことが分かります。

　[　]：ガウス記号

Δ(D)中に含まれるΔ(R)の個数をNΔ(D,R)とすると、
必要なDmax値は下記方程式により得られます｡

NE(Dmax)
=NE(Dmax-r)+NE(Dmax-r-1)+NE(Dmax-r-2)-NΔ(Dmax-r-1,r)-NΔ(Dmax-r-2,r)-NΔ(Dmax-r-2,r+1)

０＝Dmax²−６ｒDmax＋９ｒ²

すなわち　Dmax≒３ｒ　が得られ　Dmax＝３ｒ−２の予測が正しいことがほぼ判ります。

　正確には方程式を場合分けして解く必要がありますが、これら関数は少なくとも周期６で変動を繰りかえすので、その部分を計算すれば良いのです。

前回解答でｒ＝２，３，４，５，６のとき　Dmax＝３ｒ−２を示しました。

従って、後ひとつ　ｒ＝１のとき場合を示せばよく、

＜a＞C(ｎ：ｎ１：ｎ２)＝３＊C(ｎ−１：ｎ１：ｎ２)ですから確かに成立しています。

なお、パソコンでｒ＝７，８，９，１０，１１まで求め、Dmax＝３ｒ−２であることを確認しました。

まとめるとＡ_r(n)はNE(３ｒ−２)×NE(３ｒ−２)の行列Ｑを求めることにより
係数がｎの多項式であるNE(２ｒ−２)次の漸化式で表せる｡
(注記　：　左辺A_r(n)にもｎの多項式がかかるとして。)

なお、最小の漸化式であるかどうかは不明です。

ｎ	１	２	３	４	５	６	７	８	９	１０	１１
Dmax	1	4	7	10	13	16	19	22	25	28	31
NE(Dmax)	1	4	8	14	21	30	40	52	65	80	96
漸化式次数	1	2	4	7	10	14	19	24	30	37	44

【感想】

【おまけ補題２】が難しく、ようやくできました。

　『Multinomial Sums』へ

　数学の部屋へもどる