|
| |
|
|
A115139
|
|
Array of coefficients of polynomials related to integer powers of the generating function of Catalan numbers A000108.
|
|
13
| |
|
|
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; 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(a(n,m)*x^m,m=0..ceil(n/2)-1) = (sqrt(x)^(n-1))*Sn(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 appear also 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 callled "Catalan polynomials", having arisen from computations in looking at the problem of 'fitting' iterated generating function schemes to the Catalan sequence. A neighbouring pair forms the basis of a first order linear recurrence which generates, through a succession of iterated generating functions (polynomials in Z[x]), a pre-determined 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). [From Peter J. Larcombe (P.J.Larcombe(AT)derby.ac.uk), Sep 16 2008]
In the Clapperton et al. 2008 Congressus Numerantium paper, a new class of non-linear 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\'{e} approximants to the Catalan sequence o.g.f. is also discussed. [From Peter J. Larcombe (P.J.Larcombe(AT)derby.ac.uk), 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, June 16, 2011].
|
|
|
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\'{e} approximation, Congressus Numerantium, 189 (2008), 77-95.
W. Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419.
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.
G. Kreweras, Sur les eventails de segments, Cahiers du Bureau Universitaire de Recherche Operationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.
|
|
|
LINKS
| W. Lang: First 16 rows.
|
|
|
FORMULA
| a(n, m)= ((-1)^(m))*binomial(n-1-m, m), n>=1, m=0..ceil(n/2)-1.
a(n,m)=[x^m]P(n,x), n>=1, m=0..ceil(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, June 16].
|
|
|
EXAMPLE
| Array begins:
[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/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.
|
|
|
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}]]
(* From Jean-François Alcover, Jun 20 2011 *)
|
|
|
CROSSREFS
| Sequence in context: A143318 A122610 A011973 * A198788 A112543 A099478
Adjacent sequences: A115136 A115137 A115138 * A115140 A115141 A115142
|
|
|
KEYWORD
| sign,easy,tabf
|
|
|
AUTHOR
| Wolfdieter Lang (wolfdieter.lang_AT_physik_DOT_uni-karlsruhe_DOT_de), Jan 13 2006
|
| |
|
|
