|
| |
|
|
A111785
|
|
T(n,k) are coefficients used for power series inversion (sometimes called reversion), n >= 0, k = 1..A000041(n), read by rows.
|
|
13
|
|
|
|
1, -1, -1, 2, -1, 5, -5, -1, 6, 3, -21, 14, -1, 7, 7, -28, -28, 84, -42, -1, 8, 8, 4, -36, -72, -12, 120, 180, -330, 132, -1, 9, 9, 9, -45, -90, -45, -45, 165, 495, 165, -495, -990, 1287, -429, -1, 10, 10, 10, 5, -55, -110, -110, -55, -55, 220, 660, 330, 660, 55, -715, -2860, -1430, 2002, 5005, -5005, 1430, -1, 11, 11
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Coefficients are listed in Abramowitz and Stegun order (A036036).
The formula for the inversion of the power series y = F(x) = x*G(x) = x*(1 + Sum_{k>=1} g[k]*(x^k)) is obtained as a corollary of Lagrange's inversion theorem. The result is F^{(-1)}(y)= Sum_{n>=1} P(n-1)*y^n, where P(n):=sum over partitions of n of a(n,k)* G[k], with G[k]:=g[1]^e(k,1)*g[2]^e(k,2)*...*g[n]^e(k,n) if the k-th partition of n, in Abramowitz-Stegun order(see the given ref, pp. 831-2), is [1^e(k,1),2^e(k,2),...,n^e(k,n)], for k=1..p(n):= A000041(n) (partition numbers).
The sequence of row lengths is A000041(n) (partition numbers).
The signs are given by (-1)^m(n,k), with the number of parts m(n,k) = Sum_{j=1..n} e(k,j) of the k-th partition of n. For m(n,k) see A036043.
The proof that the unsigned row sums give Schroeder's little numbers A001003(n) results from their formula ((d^(n-1)/dx^(n-1)) ((1-x)/(1-2*x))^n)/n!|_{x=0}, n >= 1. This formula for A001003 can be proved starting with the compositional inverse of the g.f. of A001003 (which is given there in a comment) and using Lagrange's inversion theorem to recover the original sequence A001003.
For alternate formulations and relation to the geometry of associahedra or Stasheff polytopes (and other combinatorial objects) see A133437. [Tom Copeland, Sep 29 2008]
The coefficients of the row polynomials P(n) with monomials in lexicographically descending order e.g. P(6) = -1*g[6] + 8*g[5]*g[1] + 8*g[4]*g[2] - 36*g[4]*g[1]^2 + 4*g[3]^2 - 72*g[3]*g[2]*g[1] - 12*g[2]^3 + 120*g[3]*g[1]^3 + 180*g[2]^2*g[1]^2 - 330*g[2]*g[1]^4 + 132*g[1]^6 are given in A304462. [Herbert Eberle, Aug 16 2018]
|
|
|
REFERENCES
|
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 150, Table 4.1 (unsigned).
|
|
|
LINKS
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
|
|
|
FORMULA
|
For row n >= 1 the row polynomial in the variables g[1], ..., g[n] is P(n) = (1/(n+1)!)*(d^n/dx^n)(1/G(x)^(n+1))|_{x=0}. P(0):=1. (d^k/dx^k)G(x)|_{x=0} = k!*g[k], k>=1; G(0)=1.
a(n, k) is the coefficient in P(n) of g[1]^e(k, 1)*g[2]^e(k, 2)*..*g[n]^e(k, n) with the k-th partition of n written as [1^e(k, 1), 2^e(k, 2), ..., n^e(k, n)] in Abramowitz-Stegun order (e(k, j) >= 0; if e(k, j)=0 then j^0 is not recorded).
T(n,k) = (-1)^j*(n+j)!/((n+1)!*Product_{i>=1} s_i!), where (1*s_1 + 2*s_2 + ... = n) is the k-th partition of n and j = s_1 + s_2 ... is the number of parts. - Andrew Howroyd, Feb 01 2022
|
|
|
EXAMPLE
|
[ +1];
[ -1];
[ -1, 2];
[ -1, 5, -5];
[ -1, 6, 3, -21, 14];
[ -1, 7, 7, -28, -28, 84, -42];
[ -1, 8, 8, 4, -36, -72, -12, 120, 180, -330, 132]; ...
The seventh row, [ -1, 8, 8, 4, -36, -72, -12, 120, 180, -330, 132], stands for the row polynomial P(6) with monomials in lexicographically ascending order P(6) = -1*g[0]^5*g[6] + 8*g[0]^4*g[1]*g[5] + 8*g[0]^4*g[2]*g[4] + 4*g[0]^4*g[3]^2 - 36*g[0]^3*g[1]^2*g[4] - 72*g[0]^3*g[1]*g[2]*g[3] - 12*g[0]^3*g[2]^3 + 120*g[0]^2*g[1]^3*g[3] + 180*g[0]^2*g[1]^2*g[2]^2 - 330*g[0]*g[1]^4*g[2] + 132*g[1]^6 = (1/7!)*(differentiate 1/G(x)^7 six times and evaluate at x = 0). This gives the coefficient of y^7 of F^{(-1)}(y).
|
|
|
MATHEMATICA
|
(* Graded Colex Ordering: by length, then reverse lexicographic by digit *)
ClearAll[P, L, T, c, g]
P[0] := 1
P[n_] := -Total[
Multinomial @@ # c[Total@# - 1] Times @@
Power[g[#] & /@ Range[0, n - 1], #] & /@
Table[ Count[p, i], {p, Drop[IntegerPartitions[n + 1], 1]}, {i,
n}]]
L[n_] := Join @@ GatherBy[IntegerPartitions[n], Length]
T[1] := {1}
T[n_] := Coefficient[ Do[g[i] = P[i], {i, 0, n - 1}];
P[n - 1], #] & /@ (Times @@@ Map[c, L[n - 1], {2}])
|
|
|
PROG
|
(Sage)
def A111785_list(dim): # returns the first dim rows
C = [[0 for k in range(m+1)] for m in range(dim+1)]
C[0][0] = 1; F = [1]; i = 1
X = lambda n: 1 if n == 1 else var('x'+str(n))
while i <= dim: F.append(F[i-1]*X(i)); i += 1
for m in (1..dim):
C[m][m] = -C[m-1][m-1]/F[1]
for k in range(m-1, 0, -1):
C[m][k] = -(C[m-1][k-1]+sum(F[i]*C[m][k+i-1] for i in (2..m-k+1)))/F[1]
P = [expand((-1)^m*C[m][1]) for m in (1..dim)]
R = PolynomialRing(ZZ, [X(i) for i in (2..dim)], order='lex')
return [R(p).coefficients()[::-1] for p in P]
(PARI)
sv(n)={eval(Str("'s", n))}
Trm(q, v)={my(S=Set(v)); for(i=1, #S, my(x=S[i], c=#select(y->y==x, v)); q=polcoef(q, c, sv(x))); q}
Q(n)={polcoef(serreverse(x + x*sum(k=1, n, x^k*sv(k), O(x*x^n)))/x, n)}
row(n)={my(q=Q(n)); [Trm(q, Vec(v)) | v<-partitions(n)]} \\ Andrew Howroyd, Feb 01 2022
(PARI)
C(v)={my(n=vecsum(v), S=Set(v)); (-1)^#v*(n+#v)!/(n+1)!/prod(i=1, #S, my(x=S[i], c=#select(y->y==x, v)); c!)}
row(n)=[C(Vec(p)) | p<-partitions(n)]
|
|
|
CROSSREFS
|
Row sums give (-1)^n. Unsigned row sums are A001003(n) (little Schroeder numbers). Inversion triangle with leading quadratic term: A276738. Conjectured simplification: A283298.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
