食玩問題とネールント多項式

はじめに

食玩問題、別名クーポンコレクター問題(Coupon collector's problem)と言われる問題について、少し前に執筆した。
https://zenn.dev/firedial/articles/04b5c2103a44cf

その執筆当時から少し進展があったので、そのことについて記事を執筆していく。

ネールント多項式

今回キーワードとなるネールント多項式について説明する。以下2つの記事を参考にした。

https://mathlog.info/articles/jBqGm3cV1VhBjet5Q5Kx
https://www.sciencedirect.com/science/article/pii/S0898122106001064

定義

ネールント多項式 $B_m^{(n)}$ は、

$$\Big( \frac{x}{e^x - 1} \Big)^n = \sum_{m=0}^{\infty} B_m^{(n)} \frac{x^m}{m!}$$

を満たす多項式として定義される(便宜上、元記事と変数の文字を変えている)。2つ目の記事の PDF に $m=1,...,4$ までの例が載ってあり、

$$B_1^{(n)} = -\frac{1}{2}n$$

$$B_2^{(n)} = -\frac{1}{12}n + \frac{1}{4}n^2$$

$$B_3^{(n)} = \frac{1}{8}n^2 - \frac{1}{8}n^3$$

$$B_4^{(n)} = \frac{1}{120}n + \frac{1}{48}n^2 - \frac{1}{8}n^3 + \frac{1}{16}n^4$$

となっている。

食玩問題とネールント多項式

以前書いた記事では $t_m(n)$ を、

$$t_m(n) = \frac{1}{m!} \lim_{x \to 0} \frac{d^m}{dx^m} \Big( \frac{e^x - 1}{x} \Big)^n$$

のように定義した。右辺の式は、 $((e^x-1)/x)^n$ を多項式で表した時の $m$ 次の係数になっているので、

$$t_m(n) = \frac{1}{m!} B_m^{(-n)}$$

という関係式が成り立つ。それを踏まえて、改めて確率 $p_n(n+m)$ を表すと、

$$p_n(n+m) = \frac{(n+m)!}{n^{n+m}} t_m(n) = \frac{(n+m)!}{n^{n+m} \,\, m!} B_m^{(-n)}$$

と表すことができる。

ネールント多項式の導出

$m$ が 1 から 4 の場合は例示されていたが、もっと大きい $m$ に対しても求めてみた。食玩問題として求めたいのは $B_m^{(-n)}$ なので、今回はそちらで求めていく。

求め方

1つ目の参考文献より $B_m^{(-n)}$ は $m$ 次の多項式になる。そして $m \gt 0$ の時は定数項が 0 になる。また、

$$p_n(n+m) = \frac{1}{n^{(n+m)}} \sum_{k=0}^n (-1)^{n-k} \,\, {}_{n}\mathrm{C}_{k} \,\, k^{(n+m)}$$

という関係式もあるので、 $n=0,...,m-1$ までの代入することで、 $B_m^{(-n)}$ の $m$ 個の係数を変数とする $m$ 個の連立方程式を作ることができる。その連立方程式を解くことで係数が求められる。

以下は sagemath で雑に書いたコードになる。

b.sage

def getB(dim):
    k = var('k', domain='integer')
    n = var('n', domain='integer')
    m = var('m', domain='integer')

    p(n, m) = (1/n^(n+m)) * sum((-1)^(n-k) * binomial(n, k) * k^(n+m), k, 0, n)

    b(n, m) = factorial(m)/factorial(n+m) * sum((-1)^(n-k) * binomial(n, k) * k^(n+m), k, 0, n)

    A = Matrix(
        [[(i+1)^(j+1) for j in range(dim)] for i in range(dim)]
    )
    v = vector([b(i + 1, dim).unhold() for i in range(dim)])

    a = list(A.solve_right(v))
    a.reverse()

    return a

結果

$m=1,...,30$ までの、次数が高い方からの係数のリストになる。

1 [1/2]
2 [1/4, 1/12]
3 [1/8, 1/8, 0]
4 [1/16, 1/8, 1/48, -1/120]
5 [1/32, 5/48, 5/96, -1/48, 0]
6 [1/64, 5/64, 5/64, -13/576, -1/96, 1/252]
7 [1/128, 7/128, 35/384, -7/1152, -7/192, 1/72, 0]
8 [1/256, 7/192, 35/384, 7/288, -469/6912, 1/64, 101/8640, -1/240]
9 [1/512, 3/128, 21/256, 7/120, -133/1536, -5/384, 101/1920, -3/160, 0]
10 [1/1024, 15/1024, 35/512, 133/1536, -245/3072, -745/9216, 67/576, -47/2304, -13/576, 1/132]
11 [1/2048, 55/6144, 55/1024, 319/3072, -847/18432, -3179/18432, 121/768, 275/4608, -143/1152, 1/24, 0]
12 [1/4096, 11/2048, 165/4096, 671/6144, 77/12288, -1573/6144, 12661/110592, 5291/18432, -8723/27648, 311/7680, 7999/120960, -691/32760]
13 [1/8192, 13/4096, 715/24576, 429/4096, 1573/24576, -77363/258048, -55627/1105920, 118547/184320, -24167/55296, -4277/15360, 103987/241920, -691/5040, 0]
14 [1/16384, 91/49152, 1001/49152, 23023/245760, 17017/147456, -42185/147456, -713713/2211840, 6565559/6635520, -11011/73728, -2197741/1658880, 112957/92160, -22271/207360, -2357/8640, 1/12]
15 [1/32768, 35/32768, 455/32768, 23387/294912, 5005/32768, -63635/294912, -566137/884736, 986843/884736, 389389/442368, -700609/221184, 184717/110592, 44065/27648, -2357/1152, 5/8, 0]
16 [1/65536, 5/8192, 455/49152, 1183/18432, 17017/98304, -429/4096, -405691/442368, 46475/55296, 14343329/5308416, -3321955/663552, -372983/663552, 654715/82944, -10662539/1658880, 68653/207360, 52037/34560, -3617/8160]
17 [1/131072, 17/49152, 595/98304, 3689/73728, 314041/1769472, 221/9216, -318461/294912, 70499/663552, 52234897/10616832, -34002839/6635520, -56642963/6635520, 16664879/829440, -27398203/3317760, -4708099/414720, 884629/69120, -3617/960, 0]
18 [1/262144, 51/262144, 255/65536, 7429/196608, 66521/393216, 58123/393216, -3206489/2949120, -2919631/2949120, 5321459/786432, -500676163/318504960, -52102739/2211840, 425693651/13271040, 9025997/737280, -394116457/6635520, 805205/18432, -7132679/8709120, -1295681/120960, 43867/14364]
19 [1/524288, 57/524288, 323/131072, 54587/1966080, 119833/786432, 589475/2359296, -5538481/5898240, -13147069/5898240, 104525707/14155776, 4279960919/637009920, -27339689/645120, 4942532111/185794560, 386239847/4423680, -424557983/2654208, 3087557/61440, 1734844267/17418240, -24617939/241920, 43867/1512, 0]
20 [1/1048576, 95/1572864, 1615/1048576, 31331/1572864, 618545/4718592, 5298815/16515072, -3153449/4718592, -23678161/7077888, 174548231/28311552, 2424422819/127401984, -301489295939/5350883328, -674054165/33030144, 7540699537/31850496, -447280387/1769472, -2750847911/15925248, 769892281657/1393459200, -9752905181/26127360, -24989087/5806080, 152388293/1596672, -174611/6600]
21 [1/2097152, 35/1048576, 1995/2097152, 44023/3145728, 341411/3145728, 564281/1572864, -9267839/28311552, -19388075/4718592, 169509431/56623104, 91656750367/2802843648, -27364870403/509607936, -10718291495/84934656, 45222571403/106168320, -6794209069/53084160, -54108083701/53084160, 622543004491/398131200, -890447141/2488320, -586486687/552960, 152388293/152064, -1222277/4400, 0]
22 [1/4194304, 77/4194304, 7315/12582912, 121429/12582912, 273581/3145728, 6924797/18874368, 1602403/56623104, -82688969/18874368, -193670477/113246208, 223439442863/5096079360, -124651224269/5096079360, -4345353851377/15288238080, 4092425047601/7644119040, 355161713687/637009920, -443872562903/159252480, 422704183913/176947200, 663328656089/265420800, -372407150753/59719680, 116927697319/29859840, 162146033/1036800, -269839961/259200, 77683/276]
23 [1/8388608, 253/25165824, 8855/25165824, 54901/8388608, 639331/9437184, 13272127/37748736, 199149203/566231040, -7024646959/1698693120, -1613705093/226492416, 495348492149/10192158720, 1053110085989/30576476160, -13891955119571/30576476160, 5748660424639/15288238080, 2669531161957/1274019840, -6636972023/1327104, -26600683373/3185049600, 65898711762103/4777574400, -2200819693963/119439360, 165786906257/59719680, 28018447303/2073600, -6206319103/518400, 77683/24, 0]
24 [1/16777216, 23/4194304, 1771/8388608, 412643/94371840, 2590973/50331648, 12089605/37748736, 172999123/283115520, -243767777/70778880, -5559261851/452984832, 226249325807/5096079360, 1185022292441/10192158720, -1447104589987/2548039680, -8660399429605/36691771392, 13467035337811/3057647616, -260894809405021/45864714240, -71688697835953/6370099200, 733100733872287/19110297600, -42122797520749/1592524800, -2866903027138663/71663616000, 100370658423731/1194393600, -62044033166177/1254113280, -576654122683/174182400, 19311547193251/1415232000, -236364091/65520]
25 [1/33554432, 25/8388608, 6325/50331648, 54395/18874368, 1283975/33554432, 21131825/75497472, 89578445/113246208, -138417565/56623104, -44230817345/2717908992, 62670783985/2038431744, 836591613545/4076863488, -10906821160525/19874709504, -100563289259245/73383542784, 41249729434795/6115295232, -24485030450705/18345885696, -655026305766811/17836277760, 728249426436169/10701766656, 56490173367727/2675441664, -1240072050375463/5733089280, 123118719182719/477757440, -9933622351333/501645312, -2831822685883/13934592, 19311547193251/113218560, -1181820455/26208, 0]
26 [1/67108864, 325/201326592, 7475/100663296, 566605/301989888, 50535485/1811939328, 142693265/603979776, 403379405/452984832, -882685375/679477248, -100747677745/5435817984, 152351666155/16307453952, 48025240272815/171228266496, -58489942810825/171228266496, -424279898878381/146767085568, 3389241749938343/440301256704, 2012948906111/169869312, -288593877773518603/3852635996160, 230972950292513/3567255552, 14750727198963613/64210599936, -1757413939635601/2866544640, 2304902118987013/6879707136, 4833393355274159/6688604160, -4013813879660689/3009871872, 44244310430927/59719680, 3592733471221/52254720, -76796879507/362880, 657931/12]
27 [1/134217728, 117/134217728, 2925/67108864, 81055/67108864, 2680535/134217728, 181832365/939524096, 92470235/100663296, -8074495/50331648, -2526823585/134217728, -178866358853/10871635968, 4086478922513/12683575296, 804109514543/12683575296, -144630772253653/32614907904, 180440059226303/32614907904, 144419257955609/4076863488, -31293934702233619/285380444160, -137197562768123/2972712960, 3371821955331973/4756340736, -9469496046633389/8918138880, -1758907062727087/2548039680, 17436223298287183/4459069440, -941060290643161/222953472, 725417924473/30965760, 1971951743203/552960, -76796879507/26880, 5921379/8, 0]
28 [1/268435456, 63/134217728, 6825/268435456, 103285/134217728, 3777865/268435456, 62190505/402653184, 238955717/268435456, 114263149/134217728, -41733676985/2415919104, -462312093607/10871635968, 2296096638329/7247757312, 6739291483991/10871635968, -357777750735607/65229815808, -35364814055461/32614907904, 12913917329531855/195689447424, -52401192718983797/489223618560, -86002769126448031/244611809280, 34707909079624495/24461180928, -14572411472400847/20384317440, -51611966743151633/10192158720, 172545666694991447/15288238080, -180346029752628311/38220595200, -141287522805736481/9555148800, 11764464599450449/477757440, -516632265043043/39813120, -12683204101333/8294400, 662401834631/172800, -3392780147/3480]
29 [1/536870912, 203/805306368, 7917/536870912, 651833/1342177280, 15741635/1610612736, 96992675/805306368, 1323792899/1610612736, 4008768049/2415919104, -68926602745/4831838208, -1412383803649/21743271936, 33986618341429/130459631616, 26813970757903/21743271936, -720195712497967/130459631616, -2412529854559565/195689447424, 36732801247661491/391378894848, -2505613410067393/108716359680, -433972411555241507/489223618560, 477236143511008999/244611809280, 452126801598847297/203843174400, -186620280195688339/12230590464, 114847822549815407/6115295232, 501825629683067287/25480396800, -1546990939363832797/19110297600, 76480429249629677/955514880, 411445217170889/79626240, -1198662923393057/16588800, 19209653204299/345600, -3392780147/240, 0]
30 [1/1073741824, 145/1073741824, 9135/1073741824, 326221/1073741824, 7191275/1073741824, 98783425/1073741824, 7051300555/9663676416, 2394019745/1073741824, -99806201495/9663676416, -7026553304225/86973087744, 13897873900885/86973087744, 17230507031375/9663676416, -1092273013558325/260919263232, -6975594047253295/260919263232, 27224761515905635/260919263232, 2089848657020357789/11741366845440, -607385688350967331/391378894848, 816944739757449511/587068342272, 1622185743126704119/163074539520, -22008110267463988759/733835427840, 121368169189892755/24461180928, 22567007988209738053/183458856960, -7259242053644156419/30576476160, 1624405456139594651/22932357120, 217933807194557969/637009920, -5253421198046781847/10032906240, 54933826476137761/209018880, 1023113310480149/27371520, -320100719013851/3991680, 1723168255201/85932]

式での表現

$$\begin{aligned} B_{0}^{(-n)} &= 1 & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ B_{1}^{(-n)} &= \frac{1}{2}n & & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ B_{2}^{(-n)} &= \frac{1}{4}n^{2} &+ \frac{1}{12}n & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ B_{3}^{(-n)} &= \frac{1}{8}n^{3} &+ \frac{1}{8}n^{2} & & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ B_{4}^{(-n)} &= \frac{1}{16}n^{4} &+ \frac{1}{8}n^{3} &+ \frac{1}{48}n^{2} &- \frac{1}{120}n & & & & & & & & & & & & & & & & & & & & & & & & & & \\ B_{5}^{(-n)} &= \frac{1}{32}n^{5} &+ \frac{5}{48}n^{4} &+ \frac{5}{96}n^{3} &- \frac{1}{48}n^{2} & & & & & & & & & & & & & & & & & & & & & & & & & & \\ B_{6}^{(-n)} &= \frac{1}{64}n^{6} &+ \frac{5}{64}n^{5} &+ \frac{5}{64}n^{4} &- \frac{13}{576}n^{3} &- \frac{1}{96}n^{2} &+ \frac{1}{252}n & & & & & & & & & & & & & & & & & & & & & & & & \\ B_{7}^{(-n)} &= \frac{1}{128}n^{7} &+ \frac{7}{128}n^{6} &+ \frac{35}{384}n^{5} &- \frac{7}{1152}n^{4} &- \frac{7}{192}n^{3} &+ \frac{1}{72}n^{2} & & & & & & & & & & & & & & & & & & & & & & & & \\ B_{8}^{(-n)} &= \frac{1}{256}n^{8} &+ \frac{7}{192}n^{7} &+ \frac{35}{384}n^{6} &+ \frac{7}{288}n^{5} &- \frac{469}{6912}n^{4} &+ \frac{1}{64}n^{3} &+ \frac{101}{8640}n^{2} &- \frac{1}{240}n & & & & & & & & & & & & & & & & & & & & & & \\ B_{9}^{(-n)} &= \frac{1}{512}n^{9} &+ \frac{3}{128}n^{8} &+ \frac{21}{256}n^{7} &+ \frac{7}{120}n^{6} &- \frac{133}{1536}n^{5} &- \frac{5}{384}n^{4} &+ \frac{101}{1920}n^{3} &- \frac{3}{160}n^{2} & & & & & & & & & & & & & & & & & & & & & & \\ B_{10}^{(-n)} &= \frac{1}{1024}n^{10} &+ \frac{15}{1024}n^{9} &+ \frac{35}{512}n^{8} &+ \frac{133}{1536}n^{7} &- \frac{245}{3072}n^{6} &- \frac{745}{9216}n^{5} &+ \frac{67}{576}n^{4} &- \frac{47}{2304}n^{3} &- \frac{13}{576}n^{2} &+ \frac{1}{132}n & & & & & & & & & & & & & & & & & & & & \\ B_{11}^{(-n)} &= \frac{1}{2048}n^{11} &+ \frac{55}{6144}n^{10} &+ \frac{55}{1024}n^{9} &+ \frac{319}{3072}n^{8} &- \frac{847}{18432}n^{7} &- \frac{3179}{18432}n^{6} &+ \frac{121}{768}n^{5} &+ \frac{275}{4608}n^{4} &- \frac{143}{1152}n^{3} &+ \frac{1}{24}n^{2} & & & & & & & & & & & & & & & & & & & & \\ B_{12}^{(-n)} &= \frac{1}{4096}n^{12} &+ \frac{11}{2048}n^{11} &+ \frac{165}{4096}n^{10} &+ \frac{671}{6144}n^{9} &+ \frac{77}{12288}n^{8} &- \frac{1573}{6144}n^{7} &+ \frac{12661}{110592}n^{6} &+ \frac{5291}{18432}n^{5} &- \frac{8723}{27648}n^{4} &+ \frac{311}{7680}n^{3} &+ \frac{7999}{120960}n^{2} &- \frac{691}{32760}n & & & & & & & & & & & & & & & & & & \\ B_{13}^{(-n)} &= \frac{1}{8192}n^{13} &+ \frac{13}{4096}n^{12} &+ \frac{715}{24576}n^{11} &+ \frac{429}{4096}n^{10} &+ \frac{1573}{24576}n^{9} &- \frac{77363}{258048}n^{8} &- \frac{55627}{1105920}n^{7} &+ \frac{118547}{184320}n^{6} &- \frac{24167}{55296}n^{5} &- \frac{4277}{15360}n^{4} &+ \frac{103987}{241920}n^{3} &- \frac{691}{5040}n^{2} & & & & & & & & & & & & & & & & & & \\ B_{14}^{(-n)} &= \frac{1}{16384}n^{14} &+ \frac{91}{49152}n^{13} &+ \frac{1001}{49152}n^{12} &+ \frac{23023}{245760}n^{11} &+ \frac{17017}{147456}n^{10} &- \frac{42185}{147456}n^{9} &- \frac{713713}{2211840}n^{8} &+ \frac{6565559}{6635520}n^{7} &- \frac{11011}{73728}n^{6} &- \frac{2197741}{1658880}n^{5} &+ \frac{112957}{92160}n^{4} &- \frac{22271}{207360}n^{3} &- \frac{2357}{8640}n^{2} &+ \frac{1}{12}n & & & & & & & & & & & & & & & & \\ B_{15}^{(-n)} &= \frac{1}{32768}n^{15} &+ \frac{35}{32768}n^{14} &+ \frac{455}{32768}n^{13} &+ \frac{23387}{294912}n^{12} &+ \frac{5005}{32768}n^{11} &- \frac{63635}{294912}n^{10} &- \frac{566137}{884736}n^{9} &+ \frac{986843}{884736}n^{8} &+ \frac{389389}{442368}n^{7} &- \frac{700609}{221184}n^{6} &+ \frac{184717}{110592}n^{5} &+ \frac{44065}{27648}n^{4} &- \frac{2357}{1152}n^{3} &+ \frac{5}{8}n^{2} & & & & & & & & & & & & & & & & \\ B_{16}^{(-n)} &= \frac{1}{65536}n^{16} &+ \frac{5}{8192}n^{15} &+ \frac{455}{49152}n^{14} &+ \frac{1183}{18432}n^{13} &+ \frac{17017}{98304}n^{12} &- \frac{429}{4096}n^{11} &- \frac{405691}{442368}n^{10} &+ \frac{46475}{55296}n^{9} &+ \frac{14343329}{5308416}n^{8} &- \frac{3321955}{663552}n^{7} &- \frac{372983}{663552}n^{6} &+ \frac{654715}{82944}n^{5} &- \frac{10662539}{1658880}n^{4} &+ \frac{68653}{207360}n^{3} &+ \frac{52037}{34560}n^{2} &- \frac{3617}{8160}n & & & & & & & & & & & & & & \\ B_{17}^{(-n)} &= \frac{1}{131072}n^{17} &+ \frac{17}{49152}n^{16} &+ \frac{595}{98304}n^{15} &+ \frac{3689}{73728}n^{14} &+ \frac{314041}{1769472}n^{13} &+ \frac{221}{9216}n^{12} &- \frac{318461}{294912}n^{11} &+ \frac{70499}{663552}n^{10} &+ \frac{52234897}{10616832}n^{9} &- \frac{34002839}{6635520}n^{8} &- \frac{56642963}{6635520}n^{7} &+ \frac{16664879}{829440}n^{6} &- \frac{27398203}{3317760}n^{5} &- \frac{4708099}{414720}n^{4} &+ \frac{884629}{69120}n^{3} &- \frac{3617}{960}n^{2} & & & & & & & & & & & & & & \\ B_{18}^{(-n)} &= \frac{1}{262144}n^{18} &+ \frac{51}{262144}n^{17} &+ \frac{255}{65536}n^{16} &+ \frac{7429}{196608}n^{15} &+ \frac{66521}{393216}n^{14} &+ \frac{58123}{393216}n^{13} &- \frac{3206489}{2949120}n^{12} &- \frac{2919631}{2949120}n^{11} &+ \frac{5321459}{786432}n^{10} &- \frac{500676163}{318504960}n^{9} &- \frac{52102739}{2211840}n^{8} &+ \frac{425693651}{13271040}n^{7} &+ \frac{9025997}{737280}n^{6} &- \frac{394116457}{6635520}n^{5} &+ \frac{805205}{18432}n^{4} &- \frac{7132679}{8709120}n^{3} &- \frac{1295681}{120960}n^{2} &+ \frac{43867}{14364}n & & & & & & & & & & & & \\ B_{19}^{(-n)} &= \frac{1}{524288}n^{19} &+ \frac{57}{524288}n^{18} &+ \frac{323}{131072}n^{17} &+ \frac{54587}{1966080}n^{16} &+ \frac{119833}{786432}n^{15} &+ \frac{589475}{2359296}n^{14} &- \frac{5538481}{5898240}n^{13} &- \frac{13147069}{5898240}n^{12} &+ \frac{104525707}{14155776}n^{11} &+ \frac{4279960919}{637009920}n^{10} &- \frac{27339689}{645120}n^{9} &+ \frac{4942532111}{185794560}n^{8} &+ \frac{386239847}{4423680}n^{7} &- \frac{424557983}{2654208}n^{6} &+ \frac{3087557}{61440}n^{5} &+ \frac{1734844267}{17418240}n^{4} &- \frac{24617939}{241920}n^{3} &+ \frac{43867}{1512}n^{2} & & & & & & & & & & & & \\ B_{20}^{(-n)} &= \frac{1}{1048576}n^{20} &+ \frac{95}{1572864}n^{19} &+ \frac{1615}{1048576}n^{18} &+ \frac{31331}{1572864}n^{17} &+ \frac{618545}{4718592}n^{16} &+ \frac{5298815}{16515072}n^{15} &- \frac{3153449}{4718592}n^{14} &- \frac{23678161}{7077888}n^{13} &+ \frac{174548231}{28311552}n^{12} &+ \frac{2424422819}{127401984}n^{11} &- \frac{301489295939}{5350883328}n^{10} &- \frac{674054165}{33030144}n^{9} &+ \frac{7540699537}{31850496}n^{8} &- \frac{447280387}{1769472}n^{7} &- \frac{2750847911}{15925248}n^{6} &+ \frac{769892281657}{1393459200}n^{5} &- \frac{9752905181}{26127360}n^{4} &- \frac{24989087}{5806080}n^{3} &+ \frac{152388293}{1596672}n^{2} &- \frac{174611}{6600}n & & & & & & & & & & \\ B_{21}^{(-n)} &= \frac{1}{2097152}n^{21} &+ \frac{35}{1048576}n^{20} &+ \frac{1995}{2097152}n^{19} &+ \frac{44023}{3145728}n^{18} &+ \frac{341411}{3145728}n^{17} &+ \frac{564281}{1572864}n^{16} &- \frac{9267839}{28311552}n^{15} &- \frac{19388075}{4718592}n^{14} &+ \frac{169509431}{56623104}n^{13} &+ \frac{91656750367}{2802843648}n^{12} &- \frac{27364870403}{509607936}n^{11} &- \frac{10718291495}{84934656}n^{10} &+ \frac{45222571403}{106168320}n^{9} &- \frac{6794209069}{53084160}n^{8} &- \frac{54108083701}{53084160}n^{7} &+ \frac{622543004491}{398131200}n^{6} &- \frac{890447141}{2488320}n^{5} &- \frac{586486687}{552960}n^{4} &+ \frac{152388293}{152064}n^{3} &- \frac{1222277}{4400}n^{2} & & & & & & & & & & \\ B_{22}^{(-n)} &= \frac{1}{4194304}n^{22} &+ \frac{77}{4194304}n^{21} &+ \frac{7315}{12582912}n^{20} &+ \frac{121429}{12582912}n^{19} &+ \frac{273581}{3145728}n^{18} &+ \frac{6924797}{18874368}n^{17} &+ \frac{1602403}{56623104}n^{16} &- \frac{82688969}{18874368}n^{15} &- \frac{193670477}{113246208}n^{14} &+ \frac{223439442863}{5096079360}n^{13} &- \frac{124651224269}{5096079360}n^{12} &- \frac{4345353851377}{15288238080}n^{11} &+ \frac{4092425047601}{7644119040}n^{10} &+ \frac{355161713687}{637009920}n^{9} &- \frac{443872562903}{159252480}n^{8} &+ \frac{422704183913}{176947200}n^{7} &+ \frac{663328656089}{265420800}n^{6} &- \frac{372407150753}{59719680}n^{5} &+ \frac{116927697319}{29859840}n^{4} &+ \frac{162146033}{1036800}n^{3} &- \frac{269839961}{259200}n^{2} &+ \frac{77683}{276}n & & & & & & & & \\ B_{23}^{(-n)} &= \frac{1}{8388608}n^{23} &+ \frac{253}{25165824}n^{22} &+ \frac{8855}{25165824}n^{21} &+ \frac{54901}{8388608}n^{20} &+ \frac{639331}{9437184}n^{19} &+ \frac{13272127}{37748736}n^{18} &+ \frac{199149203}{566231040}n^{17} &- \frac{7024646959}{1698693120}n^{16} &- \frac{1613705093}{226492416}n^{15} &+ \frac{495348492149}{10192158720}n^{14} &+ \frac{1053110085989}{30576476160}n^{13} &- \frac{13891955119571}{30576476160}n^{12} &+ \frac{5748660424639}{15288238080}n^{11} &+ \frac{2669531161957}{1274019840}n^{10} &- \frac{6636972023}{1327104}n^{9} &- \frac{26600683373}{3185049600}n^{8} &+ \frac{65898711762103}{4777574400}n^{7} &- \frac{2200819693963}{119439360}n^{6} &+ \frac{165786906257}{59719680}n^{5} &+ \frac{28018447303}{2073600}n^{4} &- \frac{6206319103}{518400}n^{3} &+ \frac{77683}{24}n^{2} & & & & & & & & \\ B_{24}^{(-n)} &= \frac{1}{16777216}n^{24} &+ \frac{23}{4194304}n^{23} &+ \frac{1771}{8388608}n^{22} &+ \frac{412643}{94371840}n^{21} &+ \frac{2590973}{50331648}n^{20} &+ \frac{12089605}{37748736}n^{19} &+ \frac{172999123}{283115520}n^{18} &- \frac{243767777}{70778880}n^{17} &- \frac{5559261851}{452984832}n^{16} &+ \frac{226249325807}{5096079360}n^{15} &+ \frac{1185022292441}{10192158720}n^{14} &- \frac{1447104589987}{2548039680}n^{13} &- \frac{8660399429605}{36691771392}n^{12} &+ \frac{13467035337811}{3057647616}n^{11} &- \frac{260894809405021}{45864714240}n^{10} &- \frac{71688697835953}{6370099200}n^{9} &+ \frac{733100733872287}{19110297600}n^{8} &- \frac{42122797520749}{1592524800}n^{7} &- \frac{2866903027138663}{71663616000}n^{6} &+ \frac{100370658423731}{1194393600}n^{5} &- \frac{62044033166177}{1254113280}n^{4} &- \frac{576654122683}{174182400}n^{3} &+ \frac{19311547193251}{1415232000}n^{2} &- \frac{236364091}{65520}n & & & & & & \\ B_{25}^{(-n)} &= \frac{1}{33554432}n^{25} &+ \frac{25}{8388608}n^{24} &+ \frac{6325}{50331648}n^{23} &+ \frac{54395}{18874368}n^{22} &+ \frac{1283975}{33554432}n^{21} &+ \frac{21131825}{75497472}n^{20} &+ \frac{89578445}{113246208}n^{19} &- \frac{138417565}{56623104}n^{18} &- \frac{44230817345}{2717908992}n^{17} &+ \frac{62670783985}{2038431744}n^{16} &+ \frac{836591613545}{4076863488}n^{15} &- \frac{10906821160525}{19874709504}n^{14} &- \frac{100563289259245}{73383542784}n^{13} &+ \frac{41249729434795}{6115295232}n^{12} &- \frac{24485030450705}{18345885696}n^{11} &- \frac{655026305766811}{17836277760}n^{10} &+ \frac{728249426436169}{10701766656}n^{9} &+ \frac{56490173367727}{2675441664}n^{8} &- \frac{1240072050375463}{5733089280}n^{7} &+ \frac{123118719182719}{477757440}n^{6} &- \frac{9933622351333}{501645312}n^{5} &- \frac{2831822685883}{13934592}n^{4} &+ \frac{19311547193251}{113218560}n^{3} &- \frac{1181820455}{26208}n^{2} & & & & & & \\ B_{26}^{(-n)} &= \frac{1}{67108864}n^{26} &+ \frac{325}{201326592}n^{25} &+ \frac{7475}{100663296}n^{24} &+ \frac{566605}{301989888}n^{23} &+ \frac{50535485}{1811939328}n^{22} &+ \frac{142693265}{603979776}n^{21} &+ \frac{403379405}{452984832}n^{20} &- \frac{882685375}{679477248}n^{19} &- \frac{100747677745}{5435817984}n^{18} &+ \frac{152351666155}{16307453952}n^{17} &+ \frac{48025240272815}{171228266496}n^{16} &- \frac{58489942810825}{171228266496}n^{15} &- \frac{424279898878381}{146767085568}n^{14} &+ \frac{3389241749938343}{440301256704}n^{13} &+ \frac{2012948906111}{169869312}n^{12} &- \frac{288593877773518603}{3852635996160}n^{11} &+ \frac{230972950292513}{3567255552}n^{10} &+ \frac{14750727198963613}{64210599936}n^{9} &- \frac{1757413939635601}{2866544640}n^{8} &+ \frac{2304902118987013}{6879707136}n^{7} &+ \frac{4833393355274159}{6688604160}n^{6} &- \frac{4013813879660689}{3009871872}n^{5} &+ \frac{44244310430927}{59719680}n^{4} &+ \frac{3592733471221}{52254720}n^{3} &- \frac{76796879507}{362880}n^{2} &+ \frac{657931}{12}n & & & & \\ B_{27}^{(-n)} &= \frac{1}{134217728}n^{27} &+ \frac{117}{134217728}n^{26} &+ \frac{2925}{67108864}n^{25} &+ \frac{81055}{67108864}n^{24} &+ \frac{2680535}{134217728}n^{23} &+ \frac{181832365}{939524096}n^{22} &+ \frac{92470235}{100663296}n^{21} &- \frac{8074495}{50331648}n^{20} &- \frac{2526823585}{134217728}n^{19} &- \frac{178866358853}{10871635968}n^{18} &+ \frac{4086478922513}{12683575296}n^{17} &+ \frac{804109514543}{12683575296}n^{16} &- \frac{144630772253653}{32614907904}n^{15} &+ \frac{180440059226303}{32614907904}n^{14} &+ \frac{144419257955609}{4076863488}n^{13} &- \frac{31293934702233619}{285380444160}n^{12} &- \frac{137197562768123}{2972712960}n^{11} &+ \frac{3371821955331973}{4756340736}n^{10} &- \frac{9469496046633389}{8918138880}n^{9} &- \frac{1758907062727087}{2548039680}n^{8} &+ \frac{17436223298287183}{4459069440}n^{7} &- \frac{941060290643161}{222953472}n^{6} &+ \frac{725417924473}{30965760}n^{5} &+ \frac{1971951743203}{552960}n^{4} &- \frac{76796879507}{26880}n^{3} &+ \frac{5921379}{8}n^{2} & & & & \\ B_{28}^{(-n)} &= \frac{1}{268435456}n^{28} &+ \frac{63}{134217728}n^{27} &+ \frac{6825}{268435456}n^{26} &+ \frac{103285}{134217728}n^{25} &+ \frac{3777865}{268435456}n^{24} &+ \frac{62190505}{402653184}n^{23} &+ \frac{238955717}{268435456}n^{22} &+ \frac{114263149}{134217728}n^{21} &- \frac{41733676985}{2415919104}n^{20} &- \frac{462312093607}{10871635968}n^{19} &+ \frac{2296096638329}{7247757312}n^{18} &+ \frac{6739291483991}{10871635968}n^{17} &- \frac{357777750735607}{65229815808}n^{16} &- \frac{35364814055461}{32614907904}n^{15} &+ \frac{12913917329531855}{195689447424}n^{14} &- \frac{52401192718983797}{489223618560}n^{13} &- \frac{86002769126448031}{244611809280}n^{12} &+ \frac{34707909079624495}{24461180928}n^{11} &- \frac{14572411472400847}{20384317440}n^{10} &- \frac{51611966743151633}{10192158720}n^{9} &+ \frac{172545666694991447}{15288238080}n^{8} &- \frac{180346029752628311}{38220595200}n^{7} &- \frac{141287522805736481}{9555148800}n^{6} &+ \frac{11764464599450449}{477757440}n^{5} &- \frac{516632265043043}{39813120}n^{4} &- \frac{12683204101333}{8294400}n^{3} &+ \frac{662401834631}{172800}n^{2} &- \frac{3392780147}{3480}n & & \\ B_{29}^{(-n)} &= \frac{1}{536870912}n^{29} &+ \frac{203}{805306368}n^{28} &+ \frac{7917}{536870912}n^{27} &+ \frac{651833}{1342177280}n^{26} &+ \frac{15741635}{1610612736}n^{25} &+ \frac{96992675}{805306368}n^{24} &+ \frac{1323792899}{1610612736}n^{23} &+ \frac{4008768049}{2415919104}n^{22} &- \frac{68926602745}{4831838208}n^{21} &- \frac{1412383803649}{21743271936}n^{20} &+ \frac{33986618341429}{130459631616}n^{19} &+ \frac{26813970757903}{21743271936}n^{18} &- \frac{720195712497967}{130459631616}n^{17} &- \frac{2412529854559565}{195689447424}n^{16} &+ \frac{36732801247661491}{391378894848}n^{15} &- \frac{2505613410067393}{108716359680}n^{14} &- \frac{433972411555241507}{489223618560}n^{13} &+ \frac{477236143511008999}{244611809280}n^{12} &+ \frac{452126801598847297}{203843174400}n^{11} &- \frac{186620280195688339}{12230590464}n^{10} &+ \frac{114847822549815407}{6115295232}n^{9} &+ \frac{501825629683067287}{25480396800}n^{8} &- \frac{1546990939363832797}{19110297600}n^{7} &+ \frac{76480429249629677}{955514880}n^{6} &+ \frac{411445217170889}{79626240}n^{5} &- \frac{1198662923393057}{16588800}n^{4} &+ \frac{19209653204299}{345600}n^{3} &- \frac{3392780147}{240}n^{2} & & \\ B_{30}^{(-n)} &= \frac{1}{1073741824}n^{30} &+ \frac{145}{1073741824}n^{29} &+ \frac{9135}{1073741824}n^{28} &+ \frac{326221}{1073741824}n^{27} &+ \frac{7191275}{1073741824}n^{26} &+ \frac{98783425}{1073741824}n^{25} &+ \frac{7051300555}{9663676416}n^{24} &+ \frac{2394019745}{1073741824}n^{23} &- \frac{99806201495}{9663676416}n^{22} &- \frac{7026553304225}{86973087744}n^{21} &+ \frac{13897873900885}{86973087744}n^{20} &+ \frac{17230507031375}{9663676416}n^{19} &- \frac{1092273013558325}{260919263232}n^{18} &- \frac{6975594047253295}{260919263232}n^{17} &+ \frac{27224761515905635}{260919263232}n^{16} &+ \frac{2089848657020357789}{11741366845440}n^{15} &- \frac{607385688350967331}{391378894848}n^{14} &+ \frac{816944739757449511}{587068342272}n^{13} &+ \frac{1622185743126704119}{163074539520}n^{12} &- \frac{22008110267463988759}{733835427840}n^{11} &+ \frac{121368169189892755}{24461180928}n^{10} &+ \frac{22567007988209738053}{183458856960}n^{9} &- \frac{7259242053644156419}{30576476160}n^{8} &+ \frac{1624405456139594651}{22932357120}n^{7} &+ \frac{217933807194557969}{637009920}n^{6} &- \frac{5253421198046781847}{10032906240}n^{5} &+ \frac{54933826476137761}{209018880}n^{4} &+ \frac{1023113310480149}{27371520}n^{3} &- \frac{320100719013851}{3991680}n^{2} &+ \frac{1723168255201}{85932}n \end{aligned}$$

くるくるストン多項式

上記のリストで、ネールント多項式 $B_m^{(-n)}$ の最高次数の係数に着目すると、 $1/2^m$ という関係式が成り立っていそうである。そして、次に大きい次数の係数に着目したとき、ぱっと見では推測が難しいが、実は $m*(m-1)/(6*2^m)$ という関係式が成り立ちそうである。

それを順々に推測していくと、

$$\frac{1}{2^m}$$

$$\frac{1}{2^m} * \frac{m(m-1)}{6}$$

$$\frac{1}{2^m} * \frac{m(m-1)(m-2)(m-3)}{72}$$

$$\frac{1}{2^m} * \Big( \frac{m(m-1)(m-2)(m-3)(m-4)(m-5)}{1296} - \frac{m(m-1)(m-2)(m-3)}{180} \Big)$$

という推測ができる。最高次数を 0 番目として、 $i$ 番目の式を予想すると、

$$\frac{1}{2^m} * \Big( \sum_{j=0}^{\lceil i/2 \rceil - 1} c_{i, j} \,\, {}_m \mathrm{P}_{(2i-2j)} \Big)$$

と式を立てることができる( $i=0$ の時の和は 1 とする)。その和を、

$$\phi_i(m) = \sum_{j=0}^{\lceil i/2 \rceil - 1} c_{i, j} \,\, {}_m \mathrm{P}_{(2i-2j)}$$

と置いてやると、 $\phi_i(m)$ は $m$ の多項式となる。その多項式を くるくるストン多項式 と定義する。

求め方

$\lceil i/2 \rceil - 1$ 個の変数があるので、その分だけの連立方程式を立てればいい。以下、雑に書いたコードである(各 $i$ に対して、毎回 $B_m^{(-n)}$ を求めていたりするので、まだまだ効率化はできる)。

def getP(i):
    if i == 0:
        return 1

    startM = i + 2
    term = i // 2 + (i % 2)

    A = Matrix(
        [[mp(k)(m=m) for k in range(i * 2, i * 2 - term * 2, -2)] for m in range(i + 2, i + 2 + 2 * term, 2)]
    )
    v = vector([getB(m)[i] * 2^m for m in range(i + 2, i + 2 + 2 * term, 2)])
    a = list(A.solve_right(v))

    return a

結果

$$\begin{aligned} \phi_{1}(m) &= \frac{(m - 1)m}{6} \\ \phi_{2}(m) &= \frac{(m - 1)(m - 2)(m - 3)m}{72} \\ \phi_{3}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)m}{1296} - \frac{(m - 1)(m - 2)(m - 3)m}{180} \\ \phi_{4}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)m}{31104} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)m}{1080} \\ \phi_{5}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)m}{933120} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)m}{12960} + \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)m}{2835} \\ \phi_{6}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)m}{33592320} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)m}{233280} + \frac{101(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)m}{1360800} \\ \phi_{7}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)m}{1410877440} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)m}{5598720} + \frac{61(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)m}{8164800} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)m}{37800} \\ \phi_{8}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)m}{67722117120} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)m}{167961600} + \frac{143(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)m}{293932800} - \frac{13(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)m}{2041200} \\ \phi_{9}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)m}{3656994324480} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)m}{6046617600} + \frac{41(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)m}{1763596800} - \frac{59(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)m}{81648000} + \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)m}{467775} \\ \phi_{10}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)(m - 18)(m - 19)m}{219419659468800} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)m}{253957939200} + \frac{37(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)m}{42326323200} - \frac{11(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)m}{209952000} + \frac{7999(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)m}{14145516000} \\ \phi_{11}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)(m - 18)(m - 19)(m - 20)(m - 21)m}{14481697524940800} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)(m - 18)(m - 19)m}{12189981081600} + \frac{103(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)m}{3809369088000} - \frac{73(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)m}{26453952000} + \frac{5941(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)m}{84873096000} - \frac{691(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)m}{3831077250} \\ \phi_{12}(m) &= \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)(m - 18)(m - 19)(m - 20)(m - 21)(m - 22)(m - 23)m}{1042682221795737600} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)(m - 18)(m - 19)(m - 20)(m - 21)m}{658258978406400} + \frac{227(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)(m - 18)(m - 19)m}{319987003392000} - \frac{(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)(m - 16)(m - 17)m}{8817984000} + \frac{224137(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)(m - 14)(m - 15)m}{40739086080000} - \frac{2357(m - 1)(m - 2)(m - 3)(m - 4)(m - 5)(m - 6)(m - 7)(m - 8)(m - 9)(m - 10)(m - 11)(m - 12)(m - 13)m}{45972927000} \end{aligned}$$

式変形

くるくるストン多項式を使うことでネールント多項式は、

$$B_m^{(-n)} = \frac{1}{2^m} \sum_{i=0}^m \phi_i(m) n^{m-i}$$

というふうに置くことができる。

検算

ネールント多項式は、

$$(n + m) B_m^{(-n)} = n B_m^{(-(n-1))} + nm B_{m-1}^{(-n)}$$

という関係式が成り立つ(第2種スターリング数などの関係式を使って証明できる)。その関係式を使って検算してみる。

※前述したように同じ計算を複数回計算してしまうので、 import functools をインポートして関数の前に @functools.cache を入れてキャッシュさせておくと実行時間が早くなる。

def getBByKurukuruSuton(vm):
    if vm == 0:
        return 1

    f = 0
    for i in range(vm):
        f += getP(i) * n ^ (vm - i)

    return (f / 2^m)(m=vm)

for vm in range(1, 31):
    diff = (n + vm) * getB(vm) - n * getB(vm)(n=n-1) - n * vm * getB(vm - 1)
    print(vm, diff)

実行結果

1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
22 0
23 0
24 0
25 0
26 0
27 0
28 0
29 0
30 0

$m$ が 30 までの範囲ではあるが、くるくるストン多項式は正しそうである。

まとめ

以上の結果をまとめると、

$$p_n(n+m) = \frac{(n+m)!}{n^{n+m} \,\, m!} B_m^{(-n)} = \frac{(n+m)!}{n^{n+m} \,\, m!} \sum_{i=0}^m \phi_i(m) n^{m-i} \\ \phi_i(m) = \sum_{j=0}^{\lceil i/2 \rceil - 1} c_{i, j} \,\, {}_m \mathrm{P}_{(2i-2j)}$$

とすることができる。なので食玩問題の本質は、くるくるストン多項式 $\phi_i(m)$ に帰着させることができた。

おわりに

記事中に少し触れたが、ネールント多項式は第2種スターリング数との関係式があり、

$$S(n+m, n) = \frac{(n+m)!}{n!m!} B_m^{(-n)} = {}_{n+m} C_{n} B_m^{(-n)}$$

という関係式がある。 $n$ に $k$ を、 $m$ に $n-k$ を入れることで、

$$S(n, k) = \frac{n!}{k!(n-k)!} B_{n-k}^{(-k)} = {}_{n} C_{k} B_{n-k}^{(-k)}$$

という式に変形できる。ここでベル数 $B_n$ と第2種スターリング数には、

$$B_n = \sum_{k=0}^n S(n, k)$$

という関係式があるので、

$$B_n = \sum_{k=0}^n {}_{n} C_{k} B_{n-k}^{(-k)}$$

というふうに、ベル数は第2種スターリング数を使って表すことができる。つまり、くるくるストン多項式でも表すことができる。

いま、くるくるストン多項式の各係数に着目して研究中である。例えば最初の項の係数を各 $i$ に対して見ると、

$$\frac{1}{6}, \frac{1}{72}, \frac{1}{1296}, \frac{1}{31104}, ...$$

となっており、初項から $1/6, 1/12, 1/18,...$ となっていることがうかがえる。2番目の項も類似のことが言えそうであるが、3番目の項は急に $101/1360800$ と出てきて言えなくなる。くるくるストン多項式の係数の一般項が分かれば、ベル数をはじめ一般項が分かることになるので、研究を続けていきたい。