A085478 - OEIS

A085478

Triangle read by rows: T(n, k) = binomial(n + k, 2*k).

%I #194 Jun 11 2024 09:38:51

%S 1,1,1,1,3,1,1,6,5,1,1,10,15,7,1,1,15,35,28,9,1,1,21,70,84,45,11,1,1,

%T 28,126,210,165,66,13,1,1,36,210,462,495,286,91,15,1,1,45,330,924,

%U 1287,1001,455,120,17,1,1,55,495,1716,3003,3003,1820,680,153,19,1

%N Triangle read by rows: T(n, k) = binomial(n + k, 2*k).

%C Coefficient array for Morgan-Voyce polynomial b(n,x). A053122 (unsigned) is the coefficient array for B(n,x). Reversal of A054142. - _Paul Barry_, Jan 19 2004

%C This triangle is formed from even-numbered rows of triangle A011973 read in reverse order. - _Philippe Deléham_, Feb 16 2004

%C T(n,k) is the number of nondecreasing Dyck paths of semilength n+1, having k+1 peaks. T(n,k) is the number of nondecreasing Dyck paths of semilength n+1, having k peaks at height >= 2. T(n,k) is the number of directed column-convex polyominoes of area n+1, having k+1 columns. - _Emeric Deutsch_, May 31 2004

%C Riordan array (1/(1-x), x/(1-x)^2). - _Paul Barry_, May 09 2005

%C The triangular matrix a(n,k) = (-1)^(n+k)*T(n,k) is the matrix inverse of A039599. - _Philippe Deléham_, May 26 2005

%C The n-th row gives absolute values of coefficients of reciprocal of g.f. of bottom-line of n-wave sequence. - Floor van Lamoen (fvlamoen(AT)planet.nl), Sep 24 2006

%C Unsigned version of A129818. - _Philippe Deléham_, Oct 25 2007

%C T(n, k) is also the number of idempotent order-preserving full transformations (of an n-chain) of height k >=1 (height(alpha) = |Im(alpha)|) and of waist n (waist(alpha) = max(Im(alpha))). - _Abdullahi Umar_, Oct 02 2008

%C A085478 is jointly generated with A078812 as a triangular array of coefficients of polynomials u(n,x): initially, u(1,x) = v(1,x) = 1; for n>1, u(n,x) = u(n-1,x)+x*v(n-1)x and v(n,x) = u(n-1,x)+(x+1)*v(n-1,x). See the Mathematica section. - _Clark Kimberling_, Feb 25 2012

%C Per Kimberling's recursion relations, see A102426. - _Tom Copeland_, Jan 19 2016

%C Subtriangle of the triangle given by (0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (1, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - _Philippe Deléham_, Mar 26 2012

%C T(n,k) is also the number of compositions (ordered partitions) of 2*n+1 into 2*k+1 parts which are all odd. Proof: The o.g.f. of column k, x^k/(1-x)^(2*k+1) for k >= 0, is the o.g.f. of the odd-indexed members of the sequence with o.g.f. (x/(1-x^2))^(2*k+1) (bisection, odd part). Thus T(n,k) is obtained from the sum of the multinomial numbers A048996 for the partitions of 2*n+1 into 2*k+1 parts, all of which are odd. E.g., T(3,1) = 3 + 3 from the numbers for the partitions [1,1,5] and [1,3,3], namely 3!/(2!*1!) and 3!/(1!*2!), respectively. The number triangle with the number of these partitions as entries is A152157. - _Wolfdieter Lang_, Jul 09 2012

%C The matrix elements of the inverse are T^(-1)(n,k) = (-1)^(n+k)*A039599(n,k). - _R. J. Mathar_, Mar 12 2013

%C T(n,k) = A258993(n+1,k) for k = 0..n-1. - _Reinhard Zumkeller_, Jun 22 2015

%C The n-th row polynomial in descending powers of x is the n-th Taylor polynomial of the algebraic function F(x)*G(x)^n about 0, where F(x) = (1 + sqrt(1 + 4*x))/(2*sqrt(1 + 4*x)) and G(x) = ((1 + sqrt(1 + 4*x))/2)^2. For example, for n = 4, (1 + sqrt(1 + 4*x))/(2*sqrt(1 + 4*x)) * ((1 + sqrt(1 + 4*x))/2)^8 = (x^4 + 10*x^3 + 15*x^2 + 7*x + 1) + O(x^5). - _Peter Bala_, Feb 23 2018

%C Row n also gives the coefficients of the characteristc polynomial of the tridiagonal n X n matrix M_n given in A332602: Phi(n, x) := Det(M_n - x*1_n) = Sum_{k=0..n} T(n, k)*(-x)^k, for n >= 0, with Phi(0, x) := 1. - _Wolfdieter Lang_, Mar 25 2020

%C It appears that the largest root of the n-th degree polynomial is equal to the sum of the distinct diagonals of a (2n+1)-gon including the edge, 1. The largest root of x^3 - 6x^2 + 5x - 1 is 5.048917... = the sum of (1 + 1.80193... + 2.24697...). Alternatively, the largest root of the n-th degree polynomial is equal to the square of sigma(2n+1). Check: 5.048917... is the square of sigma(7), 2.24697.... Given N = 2n+1, sigma(N) (N odd) can be defined as 1/(2*sin(Pi/(2*N)). Relating to the 9-gon, the largest root of x^4 - 10x^3 + 15x^2 - 7x + 1 is 8.290859..., = the sum of (1 + 1.879385... + 2.532088... + 2.879385...), and is the square of sigma(9), 2.879385... Refer to A231187 for a further clarification of sigma(7). - _Gary W. Adamson_, Jun 28 2022

%C For n >=1, the n-th row is given by the coefficients of the minimal polynomial of -4*sin(Pi/(4*n + 2))^2. - _Eric W. Weisstein_, Jul 12 2023

%C Denoting this lower triangular array by L, then L * diag(binomial(2*k,k)^2) * transpose(L) is the LDU factorization of A143007, the square array of crystal ball sequences for the A_n X A_n lattices. - _Peter Bala_, Feb 06 2024

%C T(n, k) is the number of occurrences of the periodic substring (01)^k in the periodic string (01)^n (see Proposition 4.7 at page 7 in Fang). - _Stefano Spezia_, Jun 09 2024

%H Reinhard Zumkeller, <a href="/A085478/b085478.txt">Rows n = 0..125 of triangle, flattened</a>

%H J.P. Allouche and M. Mendes France, <a href="http://arxiv.org/abs/1202.0211">Stern-Brocot polynomials and power series</a>, arXiv preprint arXiv:1202.0211 [math.NT], 2012. - _N. J. A. Sloane_, May 10 2012

%H Peter Bala, <a href="/A264772/a264772_1.pdf">A 4-parameter family of embedded Riordan arrays</a>

%H E. Barcucci, A. Del Lungo, S. Fezzi, and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170, 1997, 211-217.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, J. Integer Sequ., Vol. 8 (2005), Article 05.4.5.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry4/barry64.html">Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays</a>, JIS 12 (2009) 09.8.6.

%H Paul Barry and A. Hennessey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry1/barry83.html">Notes on a Family of Riordan Arrays and Associated Integer Hankel Transforms </a>, JIS 12 (2009) 09.5.3.

%H Paul Barry, <a href="https://arxiv.org/abs/2011.10827">Notes on the Hankel transform of linear combinations of consecutive pairs of Catalan numbers</a>, arXiv:2011.10827 [math.CO], 2020.

%H Paul Barry, <a href="https://arxiv.org/abs/2011.13985">The second production matrix of a Riordan array</a>, arXiv:2011.13985 [math.CO], 2020.

%H Eduardo H. M. Brietzke, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Brietzke/bri3.html">Recurrence Relations for Sums of Binomial Coefficients and Some Generalizations, Journal of Integer Sequences</a>, Vol. 27 (2024), Article 24.3.4.

%H E. Czabarka et al, <a href="https://doi.org/10.1016/j.disc.2018.06.032">Enumerations of peaks and valleys on non-decreasing Dyck paths</a>, Disc. Math. 341 (2018) 2789-2807, Theorem 3.

%H Emeric Deutsch and H. Prodinger, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00222-6">A bijection between directed column-convex polyominoes and ordered trees of height at most three</a>, Theoretical Comp. Science, 307, 2003, 319-325.

%H James East and Nicholas Ham, <a href="https://arxiv.org/abs/1811.05735">Lattice paths and submonoids of Z^2</a>, arXiv:1811.05735 [math.CO], 2018.

%H Wenjie Fang, <a href="http://www.arxiv.org/abs/2406.02971">Maximal number of subword occurrences in a word</a>, arXiv:2406.02971 [math.CO], 2024.

%H A. Laradji and A. Umar, <a href="http://dx.doi.org/10.1007/s00233-005-0553-6">Combinatorial results for semigroups of order-preserving full transformations</a>, Semigroup Forum 72 (2006), 51-62. - _Abdullahi Umar_, Oct 02 2008

%H Donatella Merlini and Renzo Sprugnoli, <a href="https://doi.org/10.1016/j.disc.2016.08.017">Arithmetic into geometric progressions through Riordan arrays</a>, Discrete Mathematics 340.2 (2017): 160-174.

%H Yidong Sun, <a href="https://www.fq.math.ca/Papers1/43-4/paper43-4-10b.pdf">Numerical Triangles and Several Classical Sequences</a>, Fib. Quart. 43, no. 4, (2005) 359-370.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Morgan-VoycePolynomials.html">Morgan-Voyce Polynomials</a>

%F T(n, k) = (n+k)!/((n-k)!*(2*k)!).

%F G.f.: (1-z)/((1-z)^2-tz). - _Emeric Deutsch_, May 31 2004

%F Row sums are A001519 (Fibonacci(2n+1)). Diagonal sums are A011782. Binomial transform of A026729 (product of lower triangular matrices). - _Paul Barry_, Jun 21 2004

%F T(n, 0) = 1, T(n, k) = 0 if n<k; T(n, k) = Sum_{j>=0} T(n-1-j, k-1)*(j+1). T(0, 0) = 1, T(0, k) = 0 if k>0; T(n, k) = T(n-1, k-1) + T(n-1, k) + Sum_{j>=0} (-1)^j*T(n-1, k+j)*A000108(j). For the column k, g.f.: Sum_{n>=0} T(n, k)*x^n = (x^k) / (1-x)^(2*k+1). - _Philippe Deléham_, Feb 15 2004

%F Sum_{k=0..n} T(n,k)*x^(2*k) = A000012(n), A001519(n+1), A001653(n), A078922(n+1), A007805(n), A097835(n), A097315(n), A097838(n), A078988(n), A097841(n), A097727(n), A097843(n), A097730(n), A098244(n), A097733(n), A098247(n), A097736(n), A098250(n), A097739(n), A098253(n), A097742(n), A098256(n), A097767(n), A098259(n), A097770(n), A098262(n), A097773(n), A098292(n), A097776(n) for x=0,1,2,...,27,28 respectively. - _Philippe Deléham_, Dec 31 2007

%F T(2*n,n) = A005809(n). - _Philippe Deléham_, Sep 17 2009

%F A183160(n) = Sum_{k=0..n} T(n,k)*T(n,n-k). - _Paul D. Hanna_, Dec 27 2010

%F T(n,k) = 2*T(n-1,k) + T(n-1,k-1) - T(n-2,k). - _Philippe Deléham_, Feb 06 2012

%F O.g.f. for column k: x^k/(1-x)^(2*k+1), k >= 0. [See the o.g.f. of the triangle above, and a comment on compositions. - _Wolfdieter Lang_, Jul 09 2012]

%F E.g.f.: (2/sqrt(x + 4))*sinh((1/2)*t*sqrt(x + 4))*cosh((1/2)*t*sqrt(x)) = t + (1 + x)*t^3/3! + (1 + 3*x + x^2)*t^5/5! + (1 + 6*x + 5*x^2 + x^3)*t^7/7! + .... Cf. A091042. - _Peter Bala_, Jul 29 2013

%F T(n, k) = A065941(n+3*k, 4*k) = A108299(n+3*k, 4*k) = A194005(n+3*k, 4*k). - _Johannes W. Meijer_, Sep 05 2013

%F Sum_{k=0..n} (-1)^k*T(n,k)*A000108(k) = A000007(n) for n >= 0. - _Werner Schulte_, Jul 12 2017

%F Sum_{k=0..floor(n/2)} T(n-k,k)*A000108(k) = A001006(n) for n >= 0. - _Werner Schulte_, Jul 12 2017

%e Triangle begins as:

%e 1;

%e 1 1;

%e 1 3 1;

%e 1 6 5 1;

%e 1 10 15 7 1;

%e 1 15 35 28 9 1;

%e 1 21 70 84 45 11 1;

%e 1 28 126 210 165 66 13 1;

%e 1 36 210 462 495 286 91 15 1;

%e 1 45 330 924 1287 1001 455 120 17 1;

%e 1 55 495 1716 3003 3003 1820 680 153 19 1;

%e ...

%e From _Philippe Deléham_, Mar 26 2012: (Start)

%e (0, 1, 0, 1, 0, 0, 0, ...) DELTA (1, 0, 1, -1, 0, 0, 0, ...) begins:

%e 1

%e 0, 1

%e 0, 1, 1

%e 0, 1, 3, 1

%e 0, 1, 6, 5, 1

%e 0, 1, 10, 15, 7, 1

%e 0, 1, 15, 35, 28, 9, 1

%e 0, 1, 21, 70, 84, 45, 11, 1

%e 0, 1, 28, 126, 210, 165, 66, 13, 1. (End)

%p T := (n,k) -> binomial(n+k,2*k): seq(seq(T(n,k), k=0..n), n=0..11);

%t (* First program *)

%t u[1, x_]:= 1; v[1, x_]:= 1; z = 13;

%t u[n_, x_]:= u[n-1, x] + x*v[n-1, x];

%t v[n_, x_]:= u[n-1, x] + (x+1)*v[n-1, x];

%t Table[Expand[u[n, x]], {n, 1, z/2}]

%t Table[Expand[v[n, x]], {n, 1, z/2}]

%t cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];

%t TableForm[cu]

%t Flatten[%] (* A085478 *)

%t Table[Expand[v[n, x]], {n, 1, z}]

%t cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];

%t TableForm[cv]

%t Flatten[%] (* A078812 *) (*_Clark Kimberling_, Feb 25 2012 *)

%t (* Second program *)

%t Table[Binomial[n + k, 2 k], {n, 0, 12}, {k, 0, n}] // Flatten (* _G. C. Greubel_, Aug 01 2019 *)

%t CoefficientList[Table[Fibonacci[2 n + 1, Sqrt[x]], {n, 0, 10}], x] // Flatten (* _Eric W. Weisstein_, Jul 03 2023 *)

%t Join[{{1}}, CoefficientList[Table[MinimalPolynomial[-4 Sin[Pi/(4 n + 2)]^2, x], {n, 20}], x]] (* _Eric W. Weisstein_, Jul 12 2023 *)

%o (PARI) T(n,k) = binomial(n+k,n-k)

%o (Haskell)

%o a085478 n k = a085478_tabl !! n !! k

%o a085478_row n = a085478_tabl !! n

%o a085478_tabl = zipWith (zipWith a007318) a051162_tabl a025581_tabl

%o -- _Reinhard Zumkeller_, Jun 22 2015

%o (Magma) [Binomial(n+k, 2*k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Aug 01 2019

%o (Sage) [[binomial(n+k,2*k) for k in (0..n)] for n in (0..12)] # _G. C. Greubel_, Aug 01 2019

%o (GAP) Flat(List([0..12], n-> List([0..n], k-> Binomial(n+k, 2*k) ))); # _G. C. Greubel_, Aug 01 2019

%Y Row sums: A001519. Signed versions: A123970, A129818.

%Y Cf. A000108, A001006, A007318, A098158, A183160, A078812, A091042.

%Y Cf. A258993, A025581, A051162, A054142, A332602.

%Y Cf. A231187, A143007.

%K nonn,tabl,easy

%O 0,5

%A _Philippe Deléham_, Aug 14 2003