login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A111785 Array used for power series inversion (sometimes called reversion). 10
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

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

Table of n, a(n) for n=0..69.

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].

A. M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, p. 16, 3.6.25.

Wolfdieter Lang, First 10 rows and a formula.

Jin Wang, Nonlinear Inverse Relations for Bell Polynomials via the Lagrange Inversion Formula, J. Int. Seq., Vol. 22 (2019), Article 19.3.8.

Eric Weisstein's World of Mathematics, Series Reversion

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).

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}])

Array[T, 9] // Flatten (* Bradley Klee and Michael Somos, Apr 14 2017 *)

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]

A111785_list(8) # Peter Luschny, Apr 14 2017

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.

Sequence in context: A145882 A209765 A209759 * A304462 A021468 A209830

Adjacent sequences:  A111782 A111783 A111784 * A111786 A111787 A111788

KEYWORD

sign,tabf

AUTHOR

Wolfdieter Lang, Aug 23 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 03:06 EST 2019. Contains 329216 sequences. (Running on oeis4.)