File a126671.txt Notes on Carlo Wood's Polynomials N. J. A. Sloane and others Tue, 13 Feb 2007 Part 1. Carlo Wood (carlo(AT)alinoe.com) wrote to me today about a family of polynomials that he had constructed, and asked if there was a simpler description than the one he had. The following is a simple recursive construction of a family of polynomials that are equivalent to Wood's version (which is given at the end of this file). For each n = 1, 2, 3, ... there is an n X n array A[n] of coefficients. So the arrays A[1], A[2], A[3], ... form an infinite square pyramid of numbers. I work with positive numbers, since the minus signs in the original version are fully predictable. Also it seems best to use generating functions for the columns of A[n] rather than the rows Here are the first few arrays of coefficients: A[1]: s=0 i 0 1 A[2]: s=0 1 i 0 3 1 1 1 1 A[3]: s=0 1 2 i 0 11 6 1 1 7 9 2 2 2 3 1 A[4]: s=0 1 2 3 i 0 50 35 10 1 1 46 69 26 3 2 26 45 22 3 3 6 11 6 1 A[5]: s=0 1 2 3 4 i 0 274 225 85 15 1 1 326 545 270 55 4 2 274 525 320 75 6 3 126 255 170 45 4 4 24 50 35 10 1 (The first 10 rows are given below.) Let us define f[n,s](x) := Sum_{i=0..n-1} A[n][i,s] x^(n-1-i) (the generating function for column k of A[n]). For example, f[4,2] = 6+22*x+26*x^2+10*x^3. Then the following recurrence defines these arrays: f[1,0] = 1 f[n,n-1] = (1+x)^(n-1), n > 1, f[n,s] = n*x*f[n-1,s] + abs(stirling1(n,s+1))*(1+x)^(n-1), for n > 1, s < n-1, where stirling1 is a Stirling number of the first kind. Here is Maple code to do this: with(combinat); f[1,0]:=1; for n from 2 to 10 do f[n,n-1]:=sort(expand((1+x)^(n-1))); for s from 0 to n-2 do f[n,s]:=sort(expand( n*x*f[n-1,s]+abs(stirling1(n,s+1))*(1+x)^(n-1))); od; od; for n from 1 to 10 do lprint("n=",n); for s from 0 to n-1 do lprint(f[n,s]); od: od: which gives "n=", 1 1 "n=", 2 3*x+1 x+1 "n=", 3 11*x^2+7*x+2 6*x^2+9*x+3 x^2+2*x+1 "n=", 4 50*x^3+46*x^2+26*x+6 35*x^3+69*x^2+45*x+11 10*x^3+26*x^2+22*x+6 x^3+3*x^2+3*x+1 "n=", 5 274*x^4+326*x^3+274*x^2+126*x+24 225*x^4+545*x^3+525*x^2+255*x+50 85*x^4+270*x^3+320*x^2+170*x+35 15*x^4+55*x^3+75*x^2+45*x+10 x^4+4*x^3+6*x^2+4*x+1 etc. The left hand columns of the arrays A[1], A[2], A[3], ... (in other words, the first polynomial in each set) are the source for entries A126671 - A126674 in the OEIS ----------------------------------------------------------- Part 2. Comment from Vladeta Jovovic, Feb 13 2007: Sum_{ n >= k } f[n,s]*y^n/n! = (-ln(1-(1+x)*y))^(s+1)/((1-x*y)*(1+x)*(s+1)!) For example: 3 ln(1 - (1 + x) y) -1/6 ------------------ (1 - x y) (1 + x) expands to give (x^2 + 2*x + 1)*y^3 + (10*x^3 + 26*x^2 + 22*x + 6)*y^4 + ... --- --- 6 24 which is correct. ---------------------------------------------------------- Part 3. The original version of these polynomials was as follows: P_0,1(k) = k P_0,2(k) = k/2 (-k + 3) P_1,2(k) = k/2 (k - 1) P_0,3(k) = k/6 (k^2 - 6k + 11) P_1,3(k) = k/6 (-2k^2 + 9k - 7) P_2,3(k) = k/6 (k^2 - 3k + 2) P_0,4(k) = k/24 (-k^3 + 10k^2 - 35k + 50) P_1,4(k) = k/24 (3k^3 - 26k^2 + 69k - 46) P_2,4(k) = k/24 (-3k^3 + 22k^2 - 45k + 26) P_3,4(k) = k/24 (k^3 - 6k^2 + 11k - 6) P_0,5(k) = k/120 (k^4 - 15k^3 + 85k^2 - 225k + 274) P_1,5(k) = k/120 (-4k^4 + 55k^3 - 270k^2 + 545k - 326) P_2,5(k) = k/120 (6k^4 - 75k^3 + 320k^2 - 525k + 274) P_3,5(k) = k/120 (-4k^4 + 45k^3 - 170k^2 + 255k - 126) P_4,5(k) = k/120 (k^4 - 10k^3 + 35k^2 - 50k + 24) and so on. --------------------------------------------------- Part 4. The first 12 arrays A[1] through A[12] (see A126682): n=1 s=0 i 0 1 n=2 s=1 0 i 0 1 3 1 1 1 n=3 s=2 1 0 i 0 1 6 11 1 2 9 7 2 1 3 2 n=4 s=3 2 1 0 i 0 1 10 35 50 1 3 26 69 46 2 3 22 45 26 3 1 6 11 6 n=5 s=4 3 2 1 0 i 0 1 15 85 225 274 1 4 55 270 545 326 2 6 75 320 525 274 3 4 45 170 255 126 4 1 10 35 50 24 n=6 s=5 4 3 2 1 0 i 0 1 21 175 735 1624 1764 1 5 99 755 2745 4640 2556 2 10 186 1300 4170 5890 2844 3 10 174 1120 3270 4270 1956 4 5 81 485 1335 1670 744 5 1 15 85 225 274 120 n=7 s=6 5 4 3 2 1 0 i 0 1 28 322 1960 6769 13132 13068 1 6 161 1743 9695 28959 43064 22212 2 15 385 3927 20125 53550 67690 30708 3 20 490 4718 22540 55370 65170 28092 4 15 350 3192 14420 33705 38150 16008 5 6 133 1155 5005 11319 12502 5160 6 1 21 175 735 1624 1764 720 n=8 s=7 6 5 4 3 2 1 0 i 0 1 36 546 4536 22449 67284 118124 109584 1 7 244 3542 27664 124943 323596 435988 212976 2 21 708 9842 72576 303149 704172 815948 351504 3 35 1140 15190 106344 417235 902580 978740 401136 4 35 1100 14070 94136 352275 729260 762580 304464 5 21 636 7826 50400 182189 366324 374444 147120 6 7 204 2422 15120 53263 104916 105588 41040 7 1 28 322 1960 6769 13132 13068 5040 n=9 s=8 7 6 5 4 3 2 1 0 i 0 1 45 870 9450 63273 269325 723680 1172700 1026576 1 8 351 6564 68166 428568 1662759 3857356 4800564 2239344 2 28 1197 21660 215586 1281756 4612293 9645020 10411884 4292496 3 56 2331 40836 390726 2214240 7523019 14738164 14945364 5868144 4 70 2835 48120 444150 2418654 7880355 14832020 14534100 5562576 5 56 2205 36300 324450 1710744 5407605 9911860 9506700 3582000 6 28 1071 17124 148806 764652 2363319 4251716 4018644 1498320 7 8 297 4620 39186 197232 599193 1063180 994284 367920 8 1 36 546 4536 22449 67284 118124 109584 40320 n=10 s=9 8 7 6 5 4 3 2 1 0 i 0 1 55 1320 18150 157773 902055 3416930 8409500 12753576 10628640 1 9 485 11340 150690 1251117 6709605 23140710 49127860 57244824 25659360 2 36 1900 43290 556800 4433688 22513260 72175410 138667400 141075576 55988640 3 84 4340 96390 1202160 9222192 44765700 136019310 245888440 235686024 89163360 4 126 6370 137970 1671900 12413898 58121490 169987230 296080400 274689576 101348640 5 126 6230 131670 1553700 11216898 51042390 145259730 246878800 224415576 81542880 6 84 4060 83790 965040 6802992 30269820 84422310 141023960 126418824 45465120 7 36 1700 34290 386400 2669688 11668020 32044410 52849000 46899576 16742880 8 9 415 8190 90510 614817 2648415 7185960 11735540 10335024 3669120 9 1 45 870 9450 63273 269325 723680 1172700 1026576 362880 n=11 s=10 9 8 7 6 5 4 3 2 1 0 i 0 1 66 1925 32670 357423 2637558 13339535 45995730 105258076 150917976 120543840 1 10 649 18535 306240 3235320 22782837 107974955 338642810 667942220 735979464 318540960 2 45 2871 80300 1292940 13224585 89363043 401407710 1172357010 2099252320 2030120136 779171040 3 120 7524 206140 3238290 32156520 209690712 902454300 2505352410 4235201960 3867983064 1416252960 4 210 12936 347270 5329170 51523230 325984428 1356891690 3635854530 5935135360 5253599736 1876883040 5 252 15246 401170 6022170 56849496 350703738 1422532650 3717051030 5929567952 5146988616 1811429280 6 210 12474 321860 4733190 43747770 264264462 1050523320 2694640410 4229514520 3622621464 1262164320 7 120 6996 177100 2555190 23183160 137613168 538379820 1361628510 2111768120 1791332136 619627680 8 45 2574 63965 906840 8095395 47355462 182894415 457473060 703001860 591974064 203656320 9 10 561 13695 191070 1681680 9716553 37131875 92055480 140435460 117578736 40279680 10 1 55 1320 18150 157773 902055 3416930 8409500 12753576 10628640 3628800 n=12 s=11 10 9 8 7 6 5 4 3 2 1 0 i 0 1 78 2717 55770 749463 6926634 44990231 206070150 657206836 1414014888 1931559552 1486442880 1 11 846 28963 581790 7606533 67836978 420128929 1801652490 5221552556 9675404376 10157735808 4261576320 2 55 4170 140327 2760450 35173545 303760710 1806030941 7346657670 19857478300 33491516520 30991352832 11545476480 3 165 12330 407913 7864230 97834275 821075310 4717311819 18418747050 47431811460 75723889560 66305530368 23581307520 4 330 24300 790482 14948340 181899630 1488672900 8313859686 31461291180 78365419440 121024556400 102822664032 35695140480 5 462 33516 1072302 19907580 237395466 1900745748 10371310026 38320419060 93233843472 140878920336 117455117472 40178712960 6 462 33012 1039038 18955860 221927706 1743525036 9334038714 33856307100 80964916032 120478279152 99162711648 33587533440 7 330 23220 719202 12906300 148611870 1148592060 6053404566 21639148740 51074707200 75144149520 61275452832 20608076160 8 165 11430 348513 6158130 69856875 532341810 2769288819 9784028430 22857259260 33337488360 26993422368 9030147840 9 55 3750 112607 1961190 21951105 165245850 850273061 2975347650 6893859940 9985714200 8040856032 2678780160 10 11 738 21835 375210 4149453 30906414 157559545 546956190 1258752836 1813140648 1453525920 482630400 11 1 66 1925 32670 357423 2637558 13339535 45995730 105258076 150917976 120543840 39916800 ---------------------------------------------------------------- Part 5. Further comments from Carlo Wood Date: Wed, 14 Feb 2007 23:05:24 +0100 The Pink polynomials (though I won't object if you keep calling them Wood's polynomials), are defined by: The P_{i,n}(k) are polynomials in the variable k of degree n, defined for 0 <= i < n, such that P_{i,n}(k) = 0 if 0 <= k <= i 1 if i < k <= n They can therefore be written as P_{i,n}(k) = k/n! \sum_{s=0}^{n-1} c(s,i,n) k^s Then the coefficients c(s,i,n) are given by: Mathematica: c[s_, i_, n_] := n! (-1)^(s+i) Sum[(-1)^(n-r-s-1) StirlingS1[n-r, s+1] Binomial[n-1-r, i]/(n-r)!, {r, 0, n-1-s}]; LaTeX: c(s,i,n) = (-1)^{s+i} \sum_{r=0}^{n-1-s} {\frac{n!}{(n-r)!} \left|s(n-r,s+1)\right| \binom{n-1-r}{i}} where s() are the Stirling numbers of the first kind. Ascii Art: n-1-s -----, _ _ (s+i) \ n! || n-r || / n-1-r \ c(s,i,n) = (-1) ) ------ || || | | / (n-r)! ||_ s+1 _|| \ i / -----` r=0 C++ code: // Returns the "coefficients" of the Pink polynomials // (an additional factor of k/n! is needed). mpz_class c(int s, int i, int n) { mpz_class sum(0); for (int r = 0; r <= n - 1 - s; ++r) sum += product(n - r, n) * abs_stirling1(n - r, s + 1) * binomial(n - 1 - r, i); if ((s + i) & 1 == 1) sum = -sum; return sum; } These coefficients can be represented as an infinite square pyramid. Keeping i or s constant, we can look at a slice of it in the form of a triangle. Since both s and i are in the range [0,n), this will give rise to 2m slices when we consider n in the range [1,m]. For the sake of helping people finding the Pink polynomials when they are trying to find large numbers with Google, I'll include all 24 slices here for values of n up to 12. s=0 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 -1 3 11 -7 2 4 50 -46 26 -6 5 274 -326 274 -126 24 6 1764 -2556 2844 -1956 744 -120 7 13068 -22212 30708 -28092 16008 -5160 720 8 109584 -212976 351504 -401136 304464 -147120 41040 -5040 9 1026576 -2239344 4292496 -5868144 5562576 -3582000 1498320 -367920 40320 10 10628640 -25659360 55988640 -89163360 101348640 -81542880 45465120 -16742880 3669120 -362880 11 120543840 -318540960 779171040 -1416252960 1876883040 -1811429280 1262164320 -619627680 203656320 -40279680 3628800 12 1486442880 -4261576320 11545476480 -23581307520 35695140480 -40178712960 33587533440 -20608076160 9030147840 -2678780160 482630400 -39916800 s=1 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 2 -1 1 3 -6 9 -3 4 -35 69 -45 11 5 -225 545 -525 255 -50 6 -1624 4640 -5890 4270 -1670 274 7 -13132 43064 -67690 65170 -38150 12502 -1764 8 -118124 435988 -815948 978740 -762580 374444 -105588 13068 9 -1172700 4800564 -10411884 14945364 -14534100 9506700 -4018644 994284 -109584 10 -12753576 57244824 -141075576 235686024 -274689576 224415576 -126418824 46899576 -10335024 1026576 11 -150917976 735979464 -2030120136 3867983064 -5253599736 5146988616 -3622621464 1791332136 -591974064 117578736 -10628640 12 -1931559552 10157735808 -30991352832 66305530368 -102822664032 117455117472 -99162711648 61275452832 -26993422368 8040856032 -1453525920 120543840 s=2 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 3 1 -2 1 4 10 -26 22 -6 5 85 -270 320 -170 35 6 735 -2745 4170 -3270 1335 -225 7 6769 -28959 53550 -55370 33705 -11319 1624 8 67284 -323596 704172 -902580 729260 -366324 104916 -13132 9 723680 -3857356 9645020 -14738164 14832020 -9911860 4251716 -1063180 118124 10 8409500 -49127860 138667400 -245888440 296080400 -246878800 141023960 -52849000 11735540 -1172700 11 105258076 -667942220 2099252320 -4235201960 5935135360 -5929567952 4229514520 -2111768120 703001860 -140435460 12753576 12 1414014888 -9675404376 33491516520 -75723889560 121024556400 -140878920336 120478279152 -75144149520 33337488360 -9985714200 1813140648 -150917976 s=3 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 4 -1 3 -3 1 5 -15 55 -75 45 -10 6 -175 755 -1300 1120 -485 85 7 -1960 9695 -20125 22540 -14420 5005 -735 8 -22449 124943 -303149 417235 -352275 182189 -53263 6769 9 -269325 1662759 -4612293 7523019 -7880355 5407605 -2363319 599193 -67284 10 -3416930 23140710 -72175410 136019310 -169987230 145259730 -84422310 32044410 -7185960 723680 11 -45995730 338642810 -1172357010 2505352410 -3635854530 3717051030 -2694640410 1361628510 -457473060 92055480 -8409500 12 -657206836 5221552556 -19857478300 47431811460 -78365419440 93233843472 -80964916032 51074707200 -22857259260 6893859940 -1258752836 105258076 s=4 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 5 1 -4 6 -4 1 6 21 -99 186 -174 81 -15 7 322 -1743 3927 -4718 3192 -1155 175 8 4536 -27664 72576 -106344 94136 -50400 15120 -1960 9 63273 -428568 1281756 -2214240 2418654 -1710744 764652 -197232 22449 10 902055 -6709605 22513260 -44765700 58121490 -51042390 30269820 -11668020 2648415 -269325 11 13339535 -107974955 401407710 -902454300 1356891690 -1422532650 1050523320 -538379820 182894415 -37131875 3416930 12 206070150 -1801652490 7346657670 -18418747050 31461291180 -38320419060 33856307100 -21639148740 9784028430 -2975347650 546956190 -45995730 s=5 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 6 -1 5 -10 10 -5 1 7 -28 161 -385 490 -350 133 -21 8 -546 3542 -9842 15190 -14070 7826 -2422 322 9 -9450 68166 -215586 390726 -444150 324450 -148806 39186 -4536 10 -157773 1251117 -4433688 9222192 -12413898 11216898 -6802992 2669688 -614817 63273 11 -2637558 22782837 -89363043 209690712 -325984428 350703738 -264264462 137613168 -47355462 9716553 -902055 12 -44990231 420128929 -1806030941 4717311819 -8313859686 10371310026 -9334038714 6053404566 -2769288819 850273061 -157559545 13339535 s=6 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 7 1 -6 15 -20 15 -6 1 8 36 -244 708 -1140 1100 -636 204 -28 9 870 -6564 21660 -40836 48120 -36300 17124 -4620 546 10 18150 -150690 556800 -1202160 1671900 -1553700 965040 -386400 90510 -9450 11 357423 -3235320 13224585 -32156520 51523230 -56849496 43747770 -23183160 8095395 -1681680 157773 12 6926634 -67836978 303760710 -821075310 1488672900 -1900745748 1743525036 -1148592060 532341810 -165245850 30906414 -2637558 s=7 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 8 -1 7 -21 35 -35 21 -7 1 9 -45 351 -1197 2331 -2835 2205 -1071 297 -36 10 -1320 11340 -43290 96390 -137970 131670 -83790 34290 -8190 870 11 -32670 306240 -1292940 3238290 -5329170 6022170 -4733190 2555190 -906840 191070 -18150 12 -749463 7606533 -35173545 97834275 -181899630 237395466 -221927706 148611870 -69856875 21951105 -4149453 357423 s=8 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 9 1 -8 28 -56 70 -56 28 -8 1 10 55 -485 1900 -4340 6370 -6230 4060 -1700 415 -45 11 1925 -18535 80300 -206140 347270 -401170 321860 -177100 63965 -13695 1320 12 55770 -581790 2760450 -7864230 14948340 -19907580 18955860 -12906300 6158130 -1961190 375210 -32670 s=9 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 10 -1 9 -36 84 -126 126 -84 36 -9 1 11 -66 649 -2871 7524 -12936 15246 -12474 6996 -2574 561 -55 12 -2717 28963 -140327 407913 -790482 1072302 -1039038 719202 -348513 112607 -21835 1925 s=10 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 11 1 -10 45 -120 210 -252 210 -120 45 -10 1 12 78 -846 4170 -12330 24300 -33516 33012 -23220 11430 -3750 738 -66 s=11 n/i= 0 1 2 3 4 5 6 7 8 9 10 11 12 -1 11 -55 165 -330 462 -462 330 -165 55 -11 1 i=0 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 -1 3 11 -6 1 4 50 -35 10 -1 5 274 -225 85 -15 1 6 1764 -1624 735 -175 21 -1 7 13068 -13132 6769 -1960 322 -28 1 8 109584 -118124 67284 -22449 4536 -546 36 -1 9 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1 10 10628640 -12753576 8409500 -3416930 902055 -157773 18150 -1320 55 -1 11 120543840 -150917976 105258076 -45995730 13339535 -2637558 357423 -32670 1925 -66 1 12 1486442880 -1931559552 1414014888 -657206836 206070150 -44990231 6926634 -749463 55770 -2717 78 -1 i=1 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 2 -1 1 3 -7 9 -2 4 -46 69 -26 3 5 -326 545 -270 55 -4 6 -2556 4640 -2745 755 -99 5 7 -22212 43064 -28959 9695 -1743 161 -6 8 -212976 435988 -323596 124943 -27664 3542 -244 7 9 -2239344 4800564 -3857356 1662759 -428568 68166 -6564 351 -8 10 -25659360 57244824 -49127860 23140710 -6709605 1251117 -150690 11340 -485 9 11 -318540960 735979464 -667942220 338642810 -107974955 22782837 -3235320 306240 -18535 649 -10 12 -4261576320 10157735808 -9675404376 5221552556 -1801652490 420128929 -67836978 7606533 -581790 28963 -846 11 i=2 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 3 2 -3 1 4 26 -45 22 -3 5 274 -525 320 -75 6 6 2844 -5890 4170 -1300 186 -10 7 30708 -67690 53550 -20125 3927 -385 15 8 351504 -815948 704172 -303149 72576 -9842 708 -21 9 4292496 -10411884 9645020 -4612293 1281756 -215586 21660 -1197 28 10 55988640 -141075576 138667400 -72175410 22513260 -4433688 556800 -43290 1900 -36 11 779171040 -2030120136 2099252320 -1172357010 401407710 -89363043 13224585 -1292940 80300 -2871 45 12 11545476480 -30991352832 33491516520 -19857478300 7346657670 -1806030941 303760710 -35173545 2760450 -140327 4170 -55 i=3 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 4 -6 11 -6 1 5 -126 255 -170 45 -4 6 -1956 4270 -3270 1120 -174 10 7 -28092 65170 -55370 22540 -4718 490 -20 8 -401136 978740 -902580 417235 -106344 15190 -1140 35 9 -5868144 14945364 -14738164 7523019 -2214240 390726 -40836 2331 -56 10 -89163360 235686024 -245888440 136019310 -44765700 9222192 -1202160 96390 -4340 84 11 -1416252960 3867983064 -4235201960 2505352410 -902454300 209690712 -32156520 3238290 -206140 7524 -120 12 -23581307520 66305530368 -75723889560 47431811460 -18418747050 4717311819 -821075310 97834275 -7864230 407913 -12330 165 i=4 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 5 24 -50 35 -10 1 6 744 -1670 1335 -485 81 -5 7 16008 -38150 33705 -14420 3192 -350 15 8 304464 -762580 729260 -352275 94136 -14070 1100 -35 9 5562576 -14534100 14832020 -7880355 2418654 -444150 48120 -2835 70 10 101348640 -274689576 296080400 -169987230 58121490 -12413898 1671900 -137970 6370 -126 11 1876883040 -5253599736 5935135360 -3635854530 1356891690 -325984428 51523230 -5329170 347270 -12936 210 12 35695140480 -102822664032 121024556400 -78365419440 31461291180 -8313859686 1488672900 -181899630 14948340 -790482 24300 -330 i=5 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 6 -120 274 -225 85 -15 1 7 -5160 12502 -11319 5005 -1155 133 -6 8 -147120 374444 -366324 182189 -50400 7826 -636 21 9 -3582000 9506700 -9911860 5407605 -1710744 324450 -36300 2205 -56 10 -81542880 224415576 -246878800 145259730 -51042390 11216898 -1553700 131670 -6230 126 11 -1811429280 5146988616 -5929567952 3717051030 -1422532650 350703738 -56849496 6022170 -401170 15246 -252 12 -40178712960 117455117472 -140878920336 93233843472 -38320419060 10371310026 -1900745748 237395466 -19907580 1072302 -33516 462 i=6 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 7 720 -1764 1624 -735 175 -21 1 8 41040 -105588 104916 -53263 15120 -2422 204 -7 9 1498320 -4018644 4251716 -2363319 764652 -148806 17124 -1071 28 10 45465120 -126418824 141023960 -84422310 30269820 -6802992 965040 -83790 4060 -84 11 1262164320 -3622621464 4229514520 -2694640410 1050523320 -264264462 43747770 -4733190 321860 -12474 210 12 33587533440 -99162711648 120478279152 -80964916032 33856307100 -9334038714 1743525036 -221927706 18955860 -1039038 33012 -462 i=7 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 8 -5040 13068 -13132 6769 -1960 322 -28 1 9 -367920 994284 -1063180 599193 -197232 39186 -4620 297 -8 10 -16742880 46899576 -52849000 32044410 -11668020 2669688 -386400 34290 -1700 36 11 -619627680 1791332136 -2111768120 1361628510 -538379820 137613168 -23183160 2555190 -177100 6996 -120 12 -20608076160 61275452832 -75144149520 51074707200 -21639148740 6053404566 -1148592060 148611870 -12906300 719202 -23220 330 i=8 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 9 40320 -109584 118124 -67284 22449 -4536 546 -36 1 10 3669120 -10335024 11735540 -7185960 2648415 -614817 90510 -8190 415 -9 11 203656320 -591974064 703001860 -457473060 182894415 -47355462 8095395 -906840 63965 -2574 45 12 9030147840 -26993422368 33337488360 -22857259260 9784028430 -2769288819 532341810 -69856875 6158130 -348513 11430 -165 i=9 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 10 -362880 1026576 -1172700 723680 -269325 63273 -9450 870 -45 1 11 -40279680 117578736 -140435460 92055480 -37131875 9716553 -1681680 191070 -13695 561 -10 12 -2678780160 8040856032 -9985714200 6893859940 -2975347650 850273061 -165245850 21951105 -1961190 112607 -3750 55 i=10 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 11 3628800 -10628640 12753576 -8409500 3416930 -902055 157773 -18150 1320 -55 1 12 482630400 -1453525920 1813140648 -1258752836 546956190 -157559545 30906414 -4149453 375210 -21835 738 -11 i=11 n/s= 0 1 2 3 4 5 6 7 8 9 10 11 12 -39916800 120543840 -150917976 105258076 -45995730 13339535 -2637558 357423 -32670 1925 -66 1 ------------------------------------------------------ Part 6: Postscript from Carlo Wood, Feb 17 2007: Here is a simpler version of the recursion: Let us define f[n,s](x) := Sum_{i=0..n-1} A[n][i,s] x^i Then the following recurrence defines these arrays: f[n,n-1] = (1+x)^(n-1), n > 1, f[n,s] = n*f[n-1,s] + abs(stirling1(n,s+1))*(1+x)^(n-1), Thus x^(n-1-i) ==> x^i, f[1,0]=1 is not needed, and the factor of *x can be removed. The Maple program then becomes: with(combinat); for n from 1 to 10 do f[n,n-1]:=sort(expand((1+x)^(n-1))); for s from 0 to n-2 do f[n,s]:=sort(expand( n*f[n-1,s]+abs(stirling1(n,s+1))*(1+x)^(n-1))); od; od; for n from 1 to 10 do lprint("n=",n); for s from 0 to n-1 do lprint(f[n,s]); od: od: which gives "n=", 1 1 "n=", 2 x+3 x+1 "n=", 3 2*x^2+7*x+11 3*x^2+9*x+6 x^2+2*x+1 "n=", 4 6*x^3+26*x^2+46*x+50 11*x^3+45*x^2+69*x+35 6*x^3+22*x^2+26*x+10 x^3+3*x^2+3*x+1 "n=", 5 24*x^4+126*x^3+274*x^2+326*x+274 50*x^4+255*x^3+525*x^2+545*x+225 35*x^4+170*x^3+320*x^2+270*x+85 10*x^4+45*x^3+75*x^2+55*x+15 x^4+4*x^3+6*x^2+4*x+1 etc. If we want to take the minus signs into account, the f[] becomes: g[n,n-1] = (x-1)^(n-1) g[n,s] = n * g[n-1,s] + StirlingS1[n,s+1](x-1)^(n-1) then g[n,s] = \sum_{i=0}^{n-1} c(s,i,n) x^i where c(s,i,n) as defined.