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

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.

Eric Weisstein's MathWorld 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 fifth row, [ -1, 6,  3, -21,  14], stands for the row polynomial P(4) = -1*g[4] + 6*g[1]*g[3] + 3*g[2]^2 - 21*(g[1]^2)*g[2] + 14*g[1]^4 = (1/5!)*(differentiate 1/G(x)^5 four times and evaluate at x = 0). This gives the coefficient of y^5 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 19 05:13 EDT 2018. Contains 313844 sequences. (Running on oeis4.)