cp's OEIS Frontend

A115139 Array of coefficients of polynomials related to integer powers of the generating function of Catalan numbers A000108.

%I A115139 #153 Apr 18 2025 09:53:49
%S A115139 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,
%T A115139 21,-20,5,1,-9,28,-35,15,-1,1,-10,36,-56,35,-6,1,-11,45,-84,70,-21,1,
%U A115139 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
%N A115139 Array of coefficients of polynomials related to integer powers of the generating function of Catalan numbers A000108.
%C A115139 This is a signed version of A011973 (Fibonacci polynomials) with different offset.
%C A115139 The sequence of row lengths is [1,1,2,2,3,3,4,4,5,5,6,6,...] = A008619(n-1), n>=1.
%C A115139 The row sums give the period 6 sequence [1,1,0,-1,-1,0,...] = A010892(n-1), n>=1.
%C A115139 The o.g.f. for the column m sequence (with leading zeros) is ((-1)^m)*x^(2*m+1)/(1-x)^(m+1).
%C A115139 The unsigned row sums give the Fibonacci numbers A000045(n-1), n>=1.
%C A115139 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.
%C A115139 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).
%C A115139 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).
%C A115139 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.
%C A115139 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
%C A115139 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
%C A115139 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
%C A115139 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
%C A115139 _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
%C A115139 These are the coefficients of generalized Fibonacci polynomials (see link bellow). - _Rigoberto Florez_, Aug 28 2022
%D A115139 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.
%D A115139 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.
%D A115139 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.
%D A115139 R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.
%H A115139 Alois P. Heinz, <a href="/A115139/b115139.txt">Rows n = 1..200, flattened</a>
%H A115139 Hong Duc Bui, <a href="https://arxiv.org/abs/2504.09615">Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials</a>, arXiv:2504.09615 [cs.CG], 2025. See p. 3.
%H A115139 Giulio Cerbai, Anders Claesson, and Luca Ferrari, <a href="https://arxiv.org/abs/1907.08142">Stack sorting with restricted stacks</a>, arXiv:1907.08142 [cs.DS], 2019.
%H A115139 Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge Univ. Press, 2009.
%H A115139 R. Florez and J. C. Saunders, <a href="http://math.colgate.edu/~integers/w69/w69.pdf">Irreducibility of generalized Fibonacci polynomials </a>, Integers 22 (2022).
%H A115139 Atsushi Komaba, Hisashi Johno, and Kazunori Nakamoto, <a href="https://arxiv.org/abs/2206.03166">A novel statistical approach for two-sample testing based on the overlap coefficient</a>, arXiv:2206.03166 [math.ST], 2022.
%H A115139 G. Kreweras, <a href="http://www.numdam.org/item?id=BURO_1970__15__3_0">Sur les éventails de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
%H A115139 Wolfdieter Lang, <a href="/A115139/a115139.pdf">First 16 rows</a>
%H A115139 Wolfdieter Lang, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/38-5/lang.pdf">On polynomials related to powers of the generating function of Catalan's numbers</a>, Fib. Quart. 38,5 (2000) 408-419.
%H A115139 Peter J. Larcombe and Eric J. Fennessey, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/52-1/LarcombeFennessey.pdf">A Non-Linear Identity for A Particular Class of Polynomial Families</a>, Fibonacci Quart. 52 (2014), no. 1, 75-79. Mentions this sequence.
%F A115139 a(n, m) = ((-1)^(m))*binomial(n-1-m, m), n>=1, m=0..ceiling(n/2)-1.
%F A115139 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.
%F A115139 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
%F A115139 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
%F A115139 T(n, k) = GegenbauerC(k, (n+1)/2-k, -1) assuming the triangle (0,0) based. - _Peter Luschny_, May 10 2016
%e A115139 The irregular triangle a(n, m) begins:
%e A115139   n\m  0   1   2    3   4    5   6   7  8
%e A115139   1:   1
%e A115139   2:   1
%e A115139   3:   1  -1
%e A115139   4:   1  -2
%e A115139   5:   1  -3   1
%e A115139   6:   1  -4   3
%e A115139   7:   1  -5   6   -1
%e A115139   8:   1  -6  10   -4
%e A115139   9:   1  -7  15  -10   1
%e A115139   10:  1  -8  21  -20   5
%e A115139   11:  1  -9  28  -35  15   -1
%e A115139   12:  1 -10  36  -56  35   -6
%e A115139   13:  1 -11  45  -84  70  -21   1
%e A115139   14:  1 -12  55 -120 126  -56   7
%e A115139   15:  1 -13  66 -165 210 -126  28  -1
%e A115139   16:  1 -14  78 -220 330 -252  84  -8
%e A115139   17:  1 -15  91 -286 495 -462 210 -36  1
%e A115139   ... Reformatted and extended. - _Wolfdieter Lang_, Jan 27 2016
%e A115139 1/c(x) = P(2,x) - x*P(1,x)*c(x) = 1 - x*c(x), with the o.g.f. of A000108 (Catalan).
%e A115139 1/c(x)^2 = P(3,x) - x*P(2,x)*c(x) = (1-x) - x*c(x).
%e A115139 c(x)^2 = (-P(1,x) + P(2,x)*c(x))/x^1 = (-1 + 1*c(x))/x.
%e A115139 c(x)^3 = (-P(2,x) + P(3,x)*c(x))/x^2 = (-1 + (1-x)*c(x))/x^2.
%e A115139 P(3,x) = 1-x = x*S(2,1/sqrt(x)) with Chebyshev's S(2,y) = U(2,y/2) = y^2 - 1.
%p A115139 seq(seq((-1)^k*binomial(n-k,k),k=0..floor(n/2)),n=0..16); # _Peter Luschny_, May 10 2016
%t A115139 p[x_, n_] := p[x, n] = p[x, n - 1] + x*p[x, n - 2];
%t A115139 p[x_, -1] = p[x_, 0] = 1; p[x_, 1] = 1 + x;
%t A115139 Flatten[ Table[ CoefficientList[p[-x, n - 1], x], {n, 0, 16}]]
%t A115139 (* _Jean-François Alcover_, Jun 20 2011 *)
%t A115139 Flatten[Map[CoefficientList[#,x]&, Table[Sum[Binomial[t - i, i] x^(i) (-1)^i, {i, 0, t}], {t, 1,15}]]] (* _Rigoberto Florez_, Aug 28 2022 *)
%o A115139 (Python)
%o A115139 import math
%o A115139 L1 = [math.comb(t - i, i)*(-1)**i for t in range(16) for i in range(t)]
%o A115139 L1 = list(filter((0).__ne__, L1))
%o A115139 print(L1) # _Rigoberto Florez_, Sep 03 2022
%Y A115139 Cf. A011973, A030528, A053122, A092865, A098925, A102426, A115139, A169803.
%K A115139 sign,easy,tabf
%O A115139 1,6
%A A115139 _Wolfdieter Lang_, Jan 13 2006