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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A115139 Array of coefficients of polynomials related to integer powers of the generating function of Catalan numbers A000108. 21
1, 1, 1, -1, 1, -2, 1, -3, 1, 1, -4, 3, 1, -5, 6, -1, 1, -6, 10, -4, 1, -7, 15, -10, 1, 1, -8, 21, -20, 5, 1, -9, 28, -35, 15, -1, 1, -10, 36, -56, 35, -6, 1, -11, 45, -84, 70, -21, 1, 1, -12, 55, -120, 126, -56, 7, 1, -13, 66, -165, 210, -126, 28, -1, 1, -14, 78, -220, 330, -252, 84, -8, 1, -15, 91, -286, 495, -462, 210, -36, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

This is a signed version of A011973 (Fibonacci polynomials) with different offset.

The sequence of row lengths is [1,1,2,2,3,3,4,4,5,5,6,6,...] = A008619(n-1), n>=1.

The row sums give the period 6 sequence [1,1,0,-1,-1,0,...] = A010892(n-1), n>=1.

The o.g.f. for the column m sequence (with leading zeros) is ((-1)^m)*x^(2*m+1)/(1-x)^(m+1).

The unsigned row sums give the Fibonacci numbers A000045(n-1), n>=1.

The row polynomial are P(n,x):= Sum_{m=0..ceiling(n/2)-1}a(n,m)*x^m = (sqrt(x)^(n-1))*S(n-1,1/sqrt(x))), n>=1, with Chebyshev's S(n,x) polynomials A049310.

These polynomials appear in the formula 1/c(x)^n = P(n+1,x) - x*P(n,x)*c(x), n>=1, with the o.g.f. c(x):=(1-sqrt(1-4*x))/(2*x) of A000108 (Catalan numbers). See the W. Lang reference, eqs. (1) and (2), p. 408, with P(n,x):=p(-n,x).

These polynomials also appear in the formula c(x)^n = (-P(n-1,x) + P(n,x)*c(x))/x^(n-1), n>=1, with the above given o.g.f. c(x) of A000108 (Catalan numbers). See the W. Lang reference, eq. (1), with P(n,x):=p(-n,x).

With offset n>=0 this array a(n,m) coincides with the row reversed coefficient table of Chebyshev's S-polynomials without interspersed zeros. See A049310 for the S(n,x) coefficient table with increasing powers of x.

The polynomials with this sequence as coefficients form the set of so-called "Catalan polynomials", having arisen from computations in looking at the problem of 'fitting' iterated generating function schemes to the Catalan sequence. A neighboring pair forms the basis of a first-order linear recurrence that generates, through a succession of iterated generating functions (polynomials in Z[x]), a predetermined number of Catalan numbers before 'failing' - see the Clapperton et al. 2008 reference in Utilitas Mathematica, where some of the essential mathematical properties of the Catalan polynomials are also listed (based mainly on existing results for Dickson and Chebyshev polynomials, to which they are related). - Peter J Larcombe, Sep 16 2008

In the Clapperton et al. 2008 Congressus Numerantium paper, a new class of nonlinear identities satisfied by Catalan polynomials are presented. They arise from the algebraic implementation of particular cases of a general root finding formulation due to Householder, of which the classic O(2) Newton-Raphson and O(3) Halley algorithms are special cases. The role of Catalan polynomials in forming Padé approximants to the Catalan sequence o.g.f. is also discussed. - Peter J Larcombe, Nov 02 2008

These polynomials appear in the following statements: (i) P(k+1,x)/P(k+2,x) is the g.f. of all ordered trees (Dyck paths) of height at most k; (ii) x^k/(P(k+1,x)*P(k+2,x)) is the g.f. of all ordered trees (Dyck paths) of height k. See the de Bruijn et al., the Kreweras, the Sedgewick and Flajolet (p. 258), and the Flajolet and Sedgewick (p. 326) references. - Emeric Deutsch, Jun 16 2011

For a mirrored, shifted version showing the relation of these coefficients to the Pascal triangle, Fibonacci, and other number triangles, see A030528. See also A053122 for a relation to Cartan matrices. (Cf. A011973, A169803, A115139, A092865, A098925, and A102426.) - Tom Copeland, Nov 04 2014

M. Sinan Kul, Dec 09 2015, observed that (in a rewritten form) Chebyshev's S polynomials A049310

  are given by S(n, x) = Sum_{m=0..floor(n/2)} a(n+1, m)*x^(n-2*m), n >= 0. This formula is well known and can be proved from the S recurrence by induction using the recurrence for the binomial coefficients. - Wolfdieter Lang, Feb 01 2016

REFERENCES

J. A. Clapperton, P. J. Larcombe and E. J. Fennessey, On iterated generating functions for integer sequences and Catalan polynomials, Utilitas Mathematica, 77 (2008), 3-33.

J. A. Clapperton, P. J. Larcombe, E. J. Fennessey and P. Levrie, A class of auto-identities for Catalan polynomials and Padé approximation, Congressus Numerantium, 189 (2008), 77-95.

N. G. de Bruijn, D. E. Knuth and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

LINKS

Alois P. Heinz, Rows n = 1..200, flattened

Wolfdieter Lang, First 16 rows.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009

G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.

Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419.

FORMULA

a(n, m) = ((-1)^(m))*binomial(n-1-m, m), n>=1, m=0..ceiling(n/2)-1.

a(n,m) = [x^m]P(n,x), n>=1, m=0..ceiling(n/2)-1, with P(n,x) given above in terms of Chebyshev's S-polynomials.

P(n,x) = (u^(2*n) - v^(2*n))/(u^2 - v^2), where u and v are defined by u^2 + v^2 =1 and u*v = sqrt(x). Example: P(3,x) = (u^6 - v^6)/(u^2 - v^2) = u^4 + u^2*v^2 + v^4 = 1 - x. - Emeric Deutsch, Jun 16 2011

G.f.: 1/(1- x + y*x^2) = R(0)/2, where R(k) = 1 + 1/(1 - (2*k+1- x*y)*x/((2*k+2- x*y)*x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013

T(n, k) = GegenbauerC(k, (n+1)/2-k, -1)) assuming the triangle (0,0) based. - Peter Luschny, May 10 2016

EXAMPLE

The irregular triangle a(n, m) begins:

n\m  0   1   2    3    4     5    6    7   8   9

1:   1

2:   1

3:   1  -1

4:   1  -2

5:   1  -3   1

6:   1  -4   3

7:   1  -5   6   -1

8:   1  -6  10   -4

9:   1  -7  15  -10    1

10:  1  -8  21  -20    5

11:  1  -9  28  -35   15    -1

12:  1 -10  36  -56   35    -6

13:  1 -11  45  -84   70   -21    1

14:  1 -12  55 -120  126   -56    7

15:  1 -13  66 -165  210  -126   28   -1

16:  1 -14  78 -220  330  -252   84   -8

17:  1 -15  91 -286  495  -462  210  -36   1

18:  1 -16 105 -364  715  -792  462 -120   9

19:  1 -17 120 -455 1001 -1287  924 -330  45  -1

20:  1 -18 136 -560 1365 -2002 1716 -792 165 -10

... Reformatted and extended. - Wolfdieter Lang, Jan 27 2016

1/c(x) = P(2,x) - x*P(1,x)*c(x) = 1 - x*c(x), with the o.g.f. of A000108 (Catalan).

1/c(x)^2 = P(3,x) - x*P(2,x)*c(x) = (1-x) - x*c(x).

c(x)^2 = (-P(1,x) + P(2,x)*c(x))/x^1 = (-1 + 1*c(x))/x.

c(x)^3 = (-P(2,x) + P(3,x)*c(x))/x^2 = (-1 + (1-x)*c(x))/x^2.

P(3,x) = 1-x = x*S(2,1/sqrt(x))) with Chebyshev's S(2,y) = U(2,y/2) = y^2 - 1.

MAPLE

seq(seq((-1)^k*binomial(n-k, k), k=0..floor(n/2)), n=0..16); # Peter Luschny, May 10 2016

MATHEMATICA

p[x_, n_] := p[x, n] = p[x, n - 1] + x*p[x, n - 2];

p[x_, -1] = p[x_, 0] = 1; p[x_, 1] = 1 + x;

Flatten[ Table[ CoefficientList[p[-x, n - 1], x], {n, 0, 16}]]

(* Jean-François Alcover, Jun 20 2011 *)

CROSSREFS

Cf. A011973, A030528, A053122, A092865, A098925, A102426, A115139, A169803.

Sequence in context: A143318 A122610 A011973 * A198788 A112543 A099478

Adjacent sequences:  A115136 A115137 A115138 * A115140 A115141 A115142

KEYWORD

sign,easy,tabf

AUTHOR

Wolfdieter Lang, Jan 13 2006

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 November 13 19:25 EST 2018. Contains 317149 sequences. (Running on oeis4.)