cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 14 results. Next

A097894 Partial sums of A014531.

Original entry on oeis.org

1, 4, 14, 44, 134, 400, 1184, 3488, 10253, 30108, 88386, 259492, 762085, 2239120, 6582280, 19360432, 56976859, 167774428, 494301778, 1457104948, 4297477252, 12680944960, 37436553544, 110569987344, 326713395019, 965775778420
Offset: 1

Views

Author

Emeric Deutsch, Sep 03 2004

Keywords

Comments

a(n) = number of peaks at even height in all Motzkin paths of length n+3. Example: a(2)=4 because in the 21 Motzkin paths of length 5 we have altogether 4 peaks at even height (shown between parentheses): HU(UD)D, U(UD)DH, U(UD)HD, UH(UD)D.
This is a kind of Motzkin transform of A121262 because the substitution x -> x*A001006(x) in the independent variable of the g.f. A121262(x) defines a sequence which is 1,0,0,0 followed by this sequence here. - R. J. Mathar, Nov 08 2008

Crossrefs

Cf. A014531.

Programs

  • Maple
    ser:=series((1-2*z-z^2)/2/z^3/(1-z)/sqrt(1-2*z-3*z^2)-1/2/z^3,z=0,32): seq(coeff(ser,z^n),n=1..28);
  • Mathematica
    CoefficientList[Series[((1-2*x-x^2)/(2*x^3*(1-x)*Sqrt[1-2*x-3*x^2])-1/(2*x^3))/x, {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 01 2014 *) (* adapted to the offset by Vincenzo Librandi, Feb 13 2014 *)
  • PARI
    x='x+O('x^30); Vec((1-2*x-x^2)/(2*x^3*(1-x)*sqrt(1-2*x-3*x^2))-1/(2*x^3)) \\ G. C. Greubel, Dec 20 2017

Formula

G.f.: (1-2*x-x^2)/(2*x^3*(1-x)*sqrt(1-2*x-3*x^2))-1/(2*x^3). D-finite with recurrence -(n-1)*(n+3)*a(n) +(n+2)*(3n-1)*a(n-1) +(n-1)*(n+1)*a(n-2) -3*n*(n+1)*a(n-3)=0. - R. J. Mathar, Nov 17 2011
a(n) ~ 3^(n+5/2) / (4*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 01 2014

A027907 Triangle of trinomial coefficients T(n,k) (n >= 0, 0 <= k <= 2*n), read by rows: n-th row is obtained by expanding (1 + x + x^2)^n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 3, 6, 7, 6, 3, 1, 1, 4, 10, 16, 19, 16, 10, 4, 1, 1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1, 1, 6, 21, 50, 90, 126, 141, 126, 90, 50, 21, 6, 1, 1, 7, 28, 77, 161, 266, 357, 393, 357, 266, 161, 77, 28, 7, 1, 1, 8, 36, 112, 266
Offset: 0

Views

Author

Keywords

Comments

When the rows are centered about their midpoints, each term is the sum of the three terms directly above it (assuming the undefined terms in the previous row are zeros). - N. J. A. Sloane, Dec 23 2021
T(n,k) = number of integer strings s(0),...,s(n) such that s(0)=0, s(n)=k, s(i) = s(i-1) + c, where c is 0, 1 or 2. Columns of T include A002426, A005717 and A014531.
Also number of ordered trees having n+1 leaves, all at level three and n+k+3 edges. Example: T(3,5)=3 because we have three ordered trees with 4 leaves, all at level three and 11 edges: the root r has three children; from one of these children two paths of length two are hanging (i.e., 3 possibilities) while from each of the other two children one path of length two is hanging. Diagonal sums are the tribonacci numbers; more precisely: Sum_{i=0..floor(2*n/3)} T(n-i,i) = A000073(n+2). - Emeric Deutsch, Jan 03 2004
T(n,k) = A111808(n,k) for 0 <= k <= n and T(n, 2*n-k) = A111808(n,k) for 0 <= k < n. - Reinhard Zumkeller, Aug 17 2005
The trinomial coefficients, T(n,i), are the absolute value of the coefficients of the chromatic polynomial of P_2 X P_n factored with x*(x-1)^i terms. Example: The chromatic polynomial of P_2 X P_2 is: x*(x-1) - 2*x*(x-1)^2 + x*(x-1)^3 and so T(1,0)=1, T(1,1)=2 and T(1,1) = 1. - Thomas J. Pfaff (tpfaff(AT)ithaca.edu), Oct 02 2006
T(n,k) is the number of distinct ways in which k unlabeled objects can be distributed in n labeled urns allowing at most 2 objects to fall into each urn. - N-E. Fahssi, Mar 16 2008
T(n,k) is the number of compositions of k into n parts p, each part 0 <= p <= 2. Adding 1 to each part, as a corollary, T(n,k) is the number of compositions of n+k into n parts p where 1 <= p <= 3. E.g., T(2,3)=2 since 5 = 3+2 = 2+3. - Steffen Eger, Jun 10 2011
Number of lattice paths from (0,0) to (n,k) using steps (1,0), (1,1), (1,2). - Joerg Arndt, Jul 05 2011
Number of lattice paths from (0,0) to (2*n-k,k) using steps (2,0), (1,1), (0,2). - Werner Schulte, Jan 25 2017
T(n,k) is number of distinct ways to sum the integers -1, 0 , and 1 n times to obtain n-k, where T(n,0) = T(n,2*n+1) = 1. - William Boyles, Apr 23 2017
T(n-1,k-1) is the number of 2-compositions of n with 0's having k parts; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 15 2020
T(n,k) is the number of ways to obtain a sum of n+k when throwing a 3-sided die n times. Follows from the "T(n,k) is the number of compositions of n+k into n parts p where 1 <= p <= 3" comment above. - Feryal Alayont, Dec 30 2024

Examples

			The triangle T(n, k) begins:
  n\k 0   1   2   3   4   5   6   7   8   9 10 11 12
  0:  1
  1:  1   1   1
  2:  1   2   3   2   1
  3:  1   3   6   7   6   3   1
  4:  1   4  10  16  19  16  10   4   1
  5:  1   5  15  30  45  51  45  30  15   5  1
  6:  1   6  21  50  90 126 141 126  90  50 21  6  1
Concatenated rows:
G.f. = 1 + (x^2+x+1)*x + (x^2+x+1)^2*x^4 + (x^2+x+1)^3*x^9 + ...
     = 1 + (x + x^2 + x^3) + (x^4 + 2*x^5 + 3*x^6 + 2*x^7 + x^8) +
  (x^9 + 3*x^10 + 6*x^11 + 7*x^12 + 6*x^13 + 3*x^14 + x^15) + ... .
As a centered triangle, this begins:
           1
        1  1  1
     1  2  3  2  1
  1  3  6  7  6  3  1
		

References

  • Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.
  • D. C. Fielder and C. O. Alford, Pascal's triangle: top gun or just one of the gang?, in G E Bergum et al., eds., Applications of Fibonacci Numbers Vol. 4 1991 pp. 77-90 (Kluwer).
  • L. Kleinrock, Uniform permutation of sequences, JPL Space Programs Summary, Vol. 37-64-III, Apr 30, 1970, pp. 32-43.

Crossrefs

Columns of T include A002426, A005717, A014531, A005581, A005712, etc. See also A035000, A008287.
First differences are in A025177. Pairwise sums are in A025564.

Programs

  • Haskell
    a027907 n k = a027907_tabf !! n !! k
    a027907_row n = a027907_tabf !! n
    a027907_tabf = [1] : iterate f [1, 1, 1] where
       f row = zipWith3 (((+) .) . (+))
                        (row ++ [0, 0]) ([0] ++ row ++ [0]) ([0, 0] ++ row)
    a027907_list = concat a027907_tabf
    -- Reinhard Zumkeller, Jul 06 2014, Jan 22 2013, Apr 02 2011
  • Maple
    A027907 := proc(n,k) expand((1+x+x^2)^n) ; coeftayl(%,x=0,k) ; end proc:
    seq(seq(A027907(n,k),k=0..2*n),n=0..5) ; # R. J. Mathar, Jun 13 2011
    T := (n,k) -> simplify(GegenbauerC(`if`(kPeter Luschny, May 08 2016
  • Mathematica
    Table[CoefficientList[Series[(Sum[x^i, {i, 0, 2}])^n, {x, 0, 2 n}], x], {n, 0, 10}] // Grid (* Geoffrey Critzer, Mar 31 2010 *)
    Table[Sum[Binomial[n, i]Binomial[n - i, k - 2i], {i, 0, n}], {n, 0, 10}, {k, 0, 2n}] (* Adi Dani, May 07 2011 *)
    T[ n_, k_] := If[ n < 0, 0, Coefficient[ (1 + x + x^2)^n, x, k]]; (* Michael Somos, Nov 08 2016 *)
    Flatten[DeleteCases[#,0]&/@CellularAutomaton[{Total[#] &, {}, 1}, {{1}, 0}, 8] ] (* Giorgos Kalogeropoulos, Nov 09 2021 *)
  • Maxima
    trinomial(n,k):=coeff(expand((1+x+x^2)^n),x,k);
    create_list(trinomial(n,k),n,0,8,k,0,2*n); /* Emanuele Munarini, Mar 15 2011 */
    
  • Maxima
    create_list(ultraspherical(k,-n,-1/2),n,0,6,k,0,2*n); /* Emanuele Munarini, Oct 18 2016 */
    
  • PARI
    {T(n, k) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, k))}; /* Michael Somos, Jun 27 2003 */
    

Formula

G.f.: 1/(1-z*(1+w+w^2)).
T(n,k) = Sum_{r=0..floor(k/3)} (-1)^r*binomial(n, r)*binomial(k-3*r+n-1, n-1).
Recurrence: T(0,0) = 1; T(n,k) = T(n-1,k-2) + T(n-1,k-1) + T(n-1,k-0), with T(n,k) = 0 if k < 0 or k > 2*n:
T(i,0) = T(i, 2*i) = 1 for i >= 0, T(i, 1) = T(i, 2*i-1) = i for i >= 1 and for i >= 2 and 2 <= j <= i-2, T(i, j) = T(i-1, j-2) + T(i-1, j-1) + T(i-1, j).
The row sums are powers of 3 (A000244). - Gerald McGarvey, Aug 14 2004
T(n,k) = Sum_{i=0..floor(k/2)} binomial(n, 2*i+n-k) * binomial(2*i+n-k, i). - Ralf Stephan, Jan 26 2005
T(n,k) = Sum_{j=0..n} binomial(n, j) * binomial(j, k-j). - Paul Barry, May 21 2005
T(n,k) = Sum_{j=0..n} binomial(k-j, j) * binomial(n, k-j). - Paul Barry, Nov 04 2005
From Loic Turban (turban(AT)lpm.u-nancy.fr), Aug 31 2006: (Start)
T(n,k) = Sum_{j=0..n} (-1)^j * binomial(n,j) * binomial(2*n-2*j, k-j); (G. E. Andrews (1990)) obtained by expanding ((1+x)^2 - x)^n.
T(n,k) = Sum_{j=0..n} binomial(n,j) * binomial(n-j, k-2*j); obtained by expanding ((1+x) + x^2)^n.
T(n,k) = (-1)^k*Sum_{j=0..n} (-3)^j * binomial(n,j) * binomial(2*n-2*j, k-j); obtained by expanding ((1-x)^2 + 3*x)^n.
T(n,k) = (1/2)^k * Sum_{j=0..n} 3^j * binomial(n,j) * binomial(2*n-2*j, k-2*j); obtained by expanding ((1+x/2)^2 + (3/4)*x^2)^n.
T(n,k) = (2^k/4^n) * Sum_{j=0..n} 3^j * binomial(n,j) * binomial(2*n-2*j, k); obtained by expanding ((1/2+x)^2 + 3/4)^n using T(n,k) = T(2*n-k). (End)
From Paul D. Hanna, Apr 18 2012: (Start)
Let A(x) be the g.f. of the flattened sequence, then:
G.f.: A(x) = Sum_{n>=0} x^(n^2) * (1+x+x^2)^n.
G.f.: A(x) = Sum_{n>=0} x^n*(1+x+x^2)^n * Product_{k=1..n} (1 - (1+x+x^2) * x^(4*k-3)) / (1 - (1+x+x^2)*x^(4*k-1)).
G.f.: A(x) = 1/(1 - x*(1+x+x^2)/(1 + x*(1-x^2)*(1+x+x^2)/(1 - x^5*(1+x+x^2)/(1 + x^3*(1-x^4)*(1+x+x^2)/(1 - x^9*(1+x+x^2)/(1 + x^5*(1-x^6)*(1+x+x^2)/(1 - x^13* (1+x+x^2)/(1 + x^7*(1-x^8)*(1+x+x^2)/(1 - ...))))))))), a continued fraction.
(End)
Triangle: G.f. = Sum_{n>=0} (1+x+x^2)^n * x^(n^2) * y^n. - Daniel Forgues, Mar 16 2015
From Peter Luschny, May 08 2016: (Start)
T(n+1,n)/(n+1) = A001006(n) (Motzkin) for n>=0.
T(n,k) = H(n, k) if k < n else H(n, 2*n-k) where H(n,k) = binomial(n,k)*hypergeom([(1-k)/2, -k/2], [n-k+1], 4).
T(n,k) = GegenbauerC(m, -n, -1/2) where m=k if k < n else 2*n-k. (End)
T(n,k) = (-1)^k * C(2*n,k) * hypergeom([-k, -(2*n-k)], [-n+1/2], 3/4), for all k with 0 <= k <= 2n. - Robert S. Maier, Jun 13 2023
T(n,n) = Sum_{k=0..2*n} (-1)^k*(T(n,k))^2 and T(2*n,2*n) = Sum_{k=0..2*n} (T(n,k))^2 for n >= 0. - Werner Schulte, Nov 08 2016
T(n,n) = A002426(n), central trinomial coefficients. - M. F. Hasler, Nov 02 2019
Sum_{k=0..n-1} T(n, 2*k) = (3^n-1)/2. - Tony Foster III, Oct 06 2020

A111808 Left half of trinomial triangle (A027907), triangle read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 6, 7, 1, 4, 10, 16, 19, 1, 5, 15, 30, 45, 51, 1, 6, 21, 50, 90, 126, 141, 1, 7, 28, 77, 161, 266, 357, 393, 1, 8, 36, 112, 266, 504, 784, 1016, 1107, 1, 9, 45, 156, 414, 882, 1554, 2304, 2907, 3139, 1, 10, 55, 210, 615, 1452, 2850, 4740, 6765, 8350
Offset: 1

Views

Author

Reinhard Zumkeller, Aug 17 2005

Keywords

Comments

Consider a doubly infinite chessboard with squares labeled (n,k), ranks or rows n in Z, files or columns k in Z (Z denotes ...,-2,-1,0,1,2,... ); number of king-paths of length n from (0,0) to (n,k), 0 <= k <= n, is T(n,n-k). - Harrie Grondijs, May 27 2005. Cf. A026300, A114929, A114972.
Triangle of numbers C^(2)(n-1,k), n>=1, of combinations with repetitions from elements {1,2,...,n} over k, such that every element i, i=1,...,n, appears in a k-combination either 0 or 1 or 2 times (cf. also A213742-A213745). - Vladimir Shevelev and Peter J. C. Moses, Jun 19 2012

References

  • Harrie Grondijs, Neverending Quest of Type C, Volume B - the endgame study-as-struggle.

Crossrefs

Row sums give A027914; central terms give A027908;
T(n, 0) = 0;
T(n, 1) = n for n>1;
T(n, 2) = A000217(n) for n>1;
T(n, 3) = A005581(n) for n>2;
T(n, 4) = A005712(n) for n>3;
T(n, 5) = A000574(n) for n>4;
T(n, 6) = A005714(n) for n>5;
T(n, 7) = A005715(n) for n>6;
T(n, 8) = A005716(n) for n>7;
T(n, 9) = A064054(n-5) for n>8;
T(n, n-5) = A098470(n) for n>4;
T(n, n-4) = A014533(n-3) for n>3;
T(n, n-3) = A014532(n-2) for n>2;
T(n, n-2) = A014531(n-1) for n>1;
T(n, n-1) = A005717(n) for n>0;
T(n, n) = central terms of A027907 = A002426(n).

Programs

  • Maple
    T := (n,k) -> simplify(GegenbauerC(k, -n, -1/2)):
    for n from 0 to 9 do seq(T(n,k), k=0..n) od; # Peter Luschny, May 09 2016
  • Mathematica
    Table[GegenbauerC[k, -n, -1/2], {n,0,10}, {k,0,n}] // Flatten (* G. C. Greubel, Feb 28 2017 *)

Formula

(1 + x + x^2)^n = Sum(T(n,k)*x^k: 0<=k<=n) + Sum(T(n,k)*x^(2*n-k): 0<=k
T(n, k) = A027907(n, k) = Sum_{i=0,..,(k/2)} binomial(n, n-k+2*i) * binomial(n-k+2*i, i), 0<=k<=n.
T(n, k) = GegenbauerC(k, -n, -1/2). - Peter Luschny, May 09 2016

Extensions

Corrected and edited by Johannes W. Meijer, Oct 05 2010

A055151 Triangular array of Motzkin polynomial coefficients.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 6, 2, 1, 10, 10, 1, 15, 30, 5, 1, 21, 70, 35, 1, 28, 140, 140, 14, 1, 36, 252, 420, 126, 1, 45, 420, 1050, 630, 42, 1, 55, 660, 2310, 2310, 462, 1, 66, 990, 4620, 6930, 2772, 132, 1, 78, 1430, 8580, 18018, 12012, 1716, 1, 91, 2002, 15015, 42042
Offset: 0

Author

Michael Somos, Jun 14 2000

Keywords

Comments

T(n,k) = number of Motzkin paths of length n with k up steps. T(n,k)=number of 0-1-2 trees with n edges and k+1 leaves, n>0. (A 0-1-2 tree is an ordered tree in which every vertex has at most two children.) E.g., T(4,1)=6 because we have UDHH, UHDH, UHHD, HHUD, HUHD, HUDH, where U=(1,1), D(1,-1), H(1,0). - Emeric Deutsch, Nov 30 2003
Coefficients in series reversion of x/(1+H*x+U*D*x^2) corresponding to Motzkin paths with H colors for H(1,0), U colors for U(1,1) and D colors for D(1,-1). - Paul Barry, May 16 2005
Eigenvector equals A119020, so that A119020(n) = Sum_{k=0..[n/2]} T(n,k)*A119020(k). - Paul D. Hanna, May 09 2006
Row reverse of A107131. - Peter Bala, May 07 2012
Also equals the number of 231-avoiding permutations of n+1 for which descents(w) = peaks(w) = k, where descents(w) is the number of positions i such that w[i]>w[i+1], and peaks(w) is the number of positions i such that w[i-1]w[i+1]. For example, T(4,1) = 6 because 13245, 12435, 14235, 12354, 12534, 15234 are the only 231-avoiding permutations of 5 elements with descents(w) = peaks(w) = 1. - Kyle Petersen, Aug 02 2013
Apparently, a refined irregular triangle related to this triangle (and A097610) is given in the Alexeev et al. link on p. 12. This entry's triangle is also related through Barry's comment to A125181 and A134264. The diagonals of this entry are the rows of A088617. - Tom Copeland, Jun 17 2015
The row length sequence of this irregular triangle is A008619(n) = 1 + floor(n/2). - Wolfdieter Lang, Aug 24 2015

Examples

			The irregular triangle T(n,k) begins:
n\k 0  1   2    3   4  5 ...
0:  1
1:  1
2:  1  1
3:  1  3
4:  1  6   2
5:  1 10  10
6:  1 15  30    5
7:  1 21  70   35
8:  1 28 140  140  14
9:  1 36 252  420 126
10: 1 45 420 1050 630 42
... reformatted. - _Wolfdieter Lang_, Aug 24 2015
		

References

  • Miklos Bona, Handbook of Enumerative Combinatorics, CRC Press (2015), page 617, Corollary 10.8.2
  • T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 4.3.

Crossrefs

A107131 (row reversed), A080159 (with trailing zeros), A001006 = row sums, A000108(n) = T(2n, n), A001700(n) = T(2n+1, n), A119020 (eigenvector), A001263 (Narayana numbers), A089627 (gamma vectors of type B associahedra), A101280 (gamma vectors of type A permutohedra).
Cf. A014531.

Programs

  • Maple
    b:= proc(x, y) option remember;
          `if`(y>x or y<0, 0, `if`(x=0, 1, expand(
           b(x-1, y) +b(x-1, y+1) +b(x-1, y-1)*t)))
        end:
    T:= n-> (p-> seq(coeff(p, t, i), i=0..degree(p)))(b(n, 0)):
    seq(T(n), n=0..20);  # Alois P. Heinz, Feb 05 2014
  • Mathematica
    m=(1-x-(1-2x+x^2-4x^2y)^(1/2))/(2x^2 y); Map[Select[#,#>0&]&, CoefficientList[ Series[m,{x,0,15}],{x,y}]]//Grid (* Geoffrey Critzer, Feb 05 2014 *)
    p[n_] := Hypergeometric2F1[(1-n)/2, -n/2, 2, 4 x]; Table[CoefficientList[p[n], x], {n, 0, 13}] // Flatten (* Peter Luschny, Jan 23 2018 *)
  • PARI
    {T(n, k) = if( k<0 || 2*k>n, 0, n! / ((n-2*k)! * k! * (k+1)!))}
    
  • PARI
    {T(n, k) = if( k<0 || 2*k>n, 0, polcoeff( polcoeff( 2 / (1 - x + sqrt((1 - x)^2 - 4*y*x^2 + x * O(x^n))), n), k))} /* Michael Somos, Feb 14 2006 */
    
  • PARI
    {T(n, k) = n++; if( k<0 || 2*k>n, 0, polcoeff( polcoeff( serreverse( x / (1 + x + y*x^2) + x * O(x^n)), n), k))} /* Michael Somos, Feb 14 2006 */

Formula

T(n,k) = n!/((n-2k)! k! (k+1)!) = A007318(n, 2k)*A000108(k). - Henry Bottomley, Jan 31 2003
E.g.f. row polynomials R(n,y): exp(x)*BesselI(1, 2*x*sqrt(y))/(x*sqrt(y)). - Vladeta Jovovic, Aug 20 2003
G.f. row polynomials R(n,y): 2 / (1 - x + sqrt((1 - x)^2 - 4 *y * x^2)).
From Peter Bala, Oct 28 2008: (Start)
The rows of this triangle are the gamma vectors of the n-dimensional (type A) associahedra (Postnikov et al., p. 38). Cf. A089627 and A101280.
The row polynomials R(n,x) = Sum_{k = 0..n} T(n,k)*x^k begin R(0,x) = 1, R(1,x) = 1, R(2,x) = 1 + x, R(3,x) = 1 + 3*x. They are related to the Narayana polynomials N(n,x) := Sum_{k = 1..n} (1/n)*C(n,k)*C(n,k-1)*x^k through x*(1 + x)^n*R(n, x/(1 + x)^2) = N(n+1,x). For example, for n = 3, x*(1 + x)^3*(1 + 3*x/(1 + x)^2) = x + 6*x^2 + 6*x^3 + x^4, the 4th Narayana polynomial.
Recursion relation: (n + 2)*R(n,x) = (2*n + 1)*R(n-1,x) - (n - 1)*(1 - 4*x)*R(n-2,x), R(0,x) = 1, R(1,x) = 1. (End)
G.f.: M(x,y) satisfies: M(x,y)= 1 + x M(x,y) + y*x^2*M(x,y)^2. - Geoffrey Critzer, Feb 05 2014
T(n,k) = A161642(n,k)*A258820(n,k) = (binomial(n,k)/A003989(n+1, k+1))* A258820(n,k). - Tom Copeland, Jun 18 2015
Let T(n,k;q) = n!*(1+k)/((n-2*k)!*(1+k)!^2)*hypergeom([k,2*k-n],[k+2],q) then T(n,k;0) = A055151(n,k), T(n,k;1) = A008315(n,k) and T(n,k;-1) = A091156(n,k). - Peter Luschny, Oct 16 2015
From Tom Copeland, Jan 21 2016: (Start)
Reversed rows of A107131 are rows of this entry, and the diagonals of A107131 are the columns of this entry. The diagonals of this entry are the rows of A088617. The antidiagonals (bottom to top) of A088617 are the rows of this entry.
O.g.f.: [1-x-sqrt[(1-x)^2-4tx^2]]/(2tx^2), from the relation to A107131.
Re-indexed and signed, this triangle gives the row polynomials of the compositional inverse of the shifted o.g.f. for the Fibonacci polynomials of A011973, x / [1-x-tx^2] = x + x^2 + (1+t) x^3 + (1+2t) x^4 + ... . (End)
Row polynomials are P(n,x) = (1 + b.y)^n = Sum{k=0 to n} binomial(n,k) b(k) y^k = y^n M(n,1/y), where b(k) = A126120(k), y = sqrt(x), and M(n,y) are the Motzkin polynomials of A097610. - Tom Copeland, Jan 29 2016
Coefficients of the polynomials p(n,x) = hypergeom([(1-n)/2, -n/2], [2], 4x). - Peter Luschny, Jan 23 2018
Sum_{k=1..floor(n/2)} k * T(n,k) = A014531(n-1) for n>1. - Alois P. Heinz, Mar 29 2020

A014532 Form array in which n-th row is obtained by expanding (1+x+x^2)^n and taking the 3rd column from the center.

Original entry on oeis.org

1, 4, 15, 50, 161, 504, 1554, 4740, 14355, 43252, 129844, 388752, 1161615, 3465840, 10329336, 30759120, 91538523, 272290140, 809676735, 2407049106, 7154586747, 21263575256, 63191778950, 187790510700, 558069593445, 1658498131836
Offset: 1

Keywords

Comments

Number of Dyck paths of semilength n+2 having exactly one occurrence of UUU, where U=(1,1). E.g. a(2)=4 because we have UDUUUDDD, UUUDDDUD, UUUDDUDD and UUUDUDDD, where U=(1,1) and D=(1,-1). - Emeric Deutsch, Dec 05 2003
a(n) is the number of Motzkin (2n+2)-paths whose longest basin has length n-1. A basin is a sequence of contiguous flatsteps preceded by a down step and followed by an up step. Example: a(2) counts FUDFUD, UDFUDF, UDFUFD, UFDFUD. - David Callan, Jul 15 2004
a(n) is the total number of valleys (DUs) in all Motzkin (n+3)-paths. Example: a(2)=4 counts the valleys (indicated by *) in FUD*UD, UD*UDF, UD*UFD, UFD*UD; the remaining 17 Motzkin 5-paths contain no valleys. - David Callan, Jul 03 2006
a(n) is the number of lattice paths from (0,0) to (n+1,n-1) taking north and east steps avoiding north^{>=3}. - Shanzhen Gao, Apr 20 2010
a(n) is the number of paths in the half-plane x>=0, from (0,0) to (n+2,3), and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). For example, for n=2, we have the 4 paths: HUUU, UHUU, UUHU, UUUH. - José Luis Ramírez Ramírez, Apr 19 2015

References

  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.

Crossrefs

First differences are in A025181.

Programs

  • Maple
    a := n -> simplify(GegenbauerC(n-1, -n-2, -1/2)):
    seq(a(n), n=1..26); # Peter Luschny, May 09 2016
  • Mathematica
    Table[GegenbauerC[n - 1, -n - 2, -1/2], {n,1,50}] (* G. C. Greubel, Feb 28 2017 *)
  • PARI
    z='z+O('z^50); Vec(2*z/(1-4*z+z^2+6*z^3+(1-3*z+2*z^3)*sqrt(1-2*z-3*z^2))) \\ G. C. Greubel, Feb 28 2017

Formula

G.f.: 2*z/(1-4*z+z^2+6*z^3+(1-3*z+2*z^3)*sqrt(1-2*z-3*z^2)). - Emeric Deutsch, Dec 05 2003
E.g.f.: exp(x)*BesselI(3, 2x) [0, 0, 0, 1, 4, 15..]. - Paul Barry, Sep 21 2004
a(n-2) = A111808(n,n-3) for n>2. - Reinhard Zumkeller, Aug 17 2005
a(n) = Sum_{i=0..floor((n-1)/2)} binomial(n+2,n-1-i) * binomial(n-1-i,i). - Shanzhen Gao, Apr 20 2010
a(n) = -(1/(162*(n+5)*(n+3)))*(9*n+18)*(-1)^n*(-3)^(1/2) * ((n+7)*hypergeom([1/2, n+5],[1],4/3) + hypergeom([1/2, n+4],[1],4/3) * (5*n+19)). - Mark van Hoeij, Oct 30 2011
D-finite with recurrence -(n+5)*(n-1)*a(n) +(n+2)*(2*n+3)*a(n-1) +3*(n+2)*(n+1)*a(n-2)=0. - R. J. Mathar, Dec 02 2012
a(n) ~ 3^(n+5/2)/(2*sqrt(Pi*n)). - Vaclav Kotesovec, Aug 10 2013
G.f.: z*M(z)^3/(1-z-2*z^2*M(z)), where M(z) is the g.f. of Motzkin paths (A001006). - José Luis Ramírez Ramírez, Apr 19 2015
From Peter Luschny, May 09 2016: (Start)
a(n) = C(4+2*n, n-1)*hypergeom([-n+1, -n-5], [-3/2-n], 1/4).
a(n) = GegenbauerC(n-1, -n-2, -1/2). (End)

Extensions

More terms from James Sellers, Feb 05 2000

A217540 Scambler statistic on Dyck paths. Triangle T(n, k) read by rows, n >= 0, -n <= k <= n, T(n, k) is the number of Dyck paths of semilength n and k = number of returns + number of hills - number of peaks.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 2, 0, 1, 0, 0, 1, 3, 4, 2, 3, 0, 1, 0, 0, 1, 6, 10, 9, 8, 3, 4, 0, 1, 0, 0, 1, 10, 25, 30, 26, 17, 13, 4, 5, 0, 1, 0, 0, 1, 15, 56, 90, 90, 70, 49, 27, 19, 5, 6, 0, 1, 0, 0, 1, 21, 112, 245, 301, 266, 197, 128, 80, 39, 26, 6, 7, 0, 1
Offset: 0

Author

Peter Luschny, Oct 21 2012

Keywords

Examples

			[n\k] -8,-7,-6, -5,  -4,  -3,  -2,  -1,  0,   1,  2,  3,  4, 5, 6, 7, 8
-----------------------------------------------------------------------
[ 0 ]                                    1,
[ 1 ]                               0,   0,   1,
[ 2 ]                          0,   0,   1,   0,  1,
[ 3 ]                     0,   0,   1,   1,   2,  0,  1,
[ 4 ]                0,   0,   1,   3,   4,   2,  3,  0,  1,
[ 5 ]           0,   0,   1,   6,  10,   9,   8,  3,  4,  0, 1,
[ 6 ]       0,  0,   1,  10,  25,  30,  26,  17, 13,  4,  5, 0, 1,
[ 7 ]    0, 0,  1,  15,  56,  90,  90,  70,  49, 27, 19,  5, 6, 0, 1,
[ 8 ] 0, 0, 1, 21, 112, 245, 301, 266, 197, 128, 80, 39, 26, 6, 7, 0, 1
.
T(5, -2) = 6 counting the Dyck words
[1101011000] (()()(())) [1101100100] (()(())()) [1101101000] (()(()()))
[1110010100] ((())()()) [1110100100] ((()())()) [1110101000] ((()()())) .
		

Programs

  • Maple
    b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
          `if`(x=0, z, expand(`if`(y=0, z, 1)*(b(x-1, y+1, true)
          +b(x-1, y-1, false)*`if`(t and y<>1, 1/z, 1)))))
        end:
    T:= n-> `if`(n=0, 1, (p-> seq(coeff(p, z, i), i=-n..n))
                         (b(2*n-1, 1, true))):
    seq(T(n), n=0..10);  # Alois P. Heinz, Jun 10 2014
  • Mathematica
    b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, z, Expand[If[y == 0, z, 1]*(b[x-1, y+1, True]+b[x-1, y-1, False]*If[t && y != 1, 1/z, 1])]]]; T[n_] := If[n == 0, 1, Function[p, Table[Coefficient[p, z, i], {i, -n, n}]][b[2*n-1, 1, True]]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Oct 24 2016, after Alois P. Heinz *)
  • Sage
    def A217540(n, k):
        def characteristic(d):
            count = 1
            h = d.heights()
            for i in (1..len(d)-1):
                if d[i-1]==1 and d[i]==0: count -= 1
                if h[i]==0: count +=1
                else:
                    if h[i-1]==0 and h[i+1]==0: count += 1
            return count
        if n == 0: return 1
        count = 0
        for d in DyckWords(n):
            if k == characteristic(d): count += 1
        return count
    for n in (0..6): [A217540(n, k) for k in (-n..n)]

Formula

T(n,-1) = A014531(n-2) = [0,0,0],1,3,10,30,90,...
T(n, 0) = A113682(n-2) = [1,0],1,1,4,9,26,70,197,...
T(n, 1) = A194588(n-1) = [0],1,0,2,2,8,17,49,128,...
Sum(k>=0,T(n,k)) = A189912(n-1) = [1],1,2,4,10,25, 66,177,..
Sum(k< 0,T(n,k)) = A217539(n) = 0,0,0,1, 4,17, 66,252,..
Sum(-n<=k<=n,T(n,k)) = A000108(n) = 1,1,2,5,14,42,132,429,..

A025180 a(n) = number of (s(0), s(1), ..., s(n)) such that s(i) is an integer, s(0) = 0, |s(1)| = 1, |s(i) - s(i-1)| <= 1 for i >= 2, s(n) = 2. Also a(n) = T(n,n-2), where T is the array defined in A025177.

Original entry on oeis.org

1, 2, 7, 20, 60, 176, 518, 1520, 4461, 13090, 38423, 112828, 331487, 974442, 2866125, 8434992, 24838275, 73181142, 215729781, 636275820, 1877569134, 5543095404, 16372140876, 48377825216, 143009973875, 422918975726, 1251154692297
Offset: 2

Keywords

Crossrefs

First differences of A014531. First differences are in A026069.

Formula

Conjecture: -(n+2)*(n-3)*a(n) +2*(2*n+1)*(n-3)*a(n-1) +(-n^2+10*n-18)*a(n-2) -3*(2*n-3)*(n-3)*a(n-3)=0. - R. J. Mathar, Feb 25 2015

A026069 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is an integer, s(0) = 0, |s(i) - s(i-1)| = 1 for i = 1,2; |s(i) - s(i-1)| <= 1 for i >= 3, s(n) = 2. Also a(n) = T(n,n-2), where T is the array defined in A024996.

Original entry on oeis.org

1, 5, 13, 40, 116, 342, 1002, 2941, 8629, 25333, 74405, 218659, 642955, 1891683, 5568867, 16403283, 48342867, 142548639, 420546039, 1241293314, 3665526270, 10829045472, 32005684340, 94632148659, 279909001851, 828235716571, 2451561077995
Offset: 3

Keywords

Crossrefs

First differences of A025180. Second differences of A014531.

Extensions

a(29) corrected by Sean A. Irvine, Sep 14 2019

A359364 Triangle read by rows. The Motzkin triangle, the coefficients of the Motzkin polynomials. M(n, k) = binomial(n, k) * CatalanNumber(k/2) if k is even, otherwise 0.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 6, 0, 2, 1, 0, 10, 0, 10, 0, 1, 0, 15, 0, 30, 0, 5, 1, 0, 21, 0, 70, 0, 35, 0, 1, 0, 28, 0, 140, 0, 140, 0, 14, 1, 0, 36, 0, 252, 0, 420, 0, 126, 0, 1, 0, 45, 0, 420, 0, 1050, 0, 630, 0, 42, 1, 0, 55, 0, 660, 0, 2310, 0, 2310, 0, 462, 0
Offset: 0

Author

Peter Luschny, Jan 09 2023

Keywords

Comments

The generalized Motzkin numbers M(n, k) are a refinement of the Motzkin numbers M(n) (A001006) in the sense that they are coefficients of polynomials M(n, x) = Sum_{n..k} M(n, k) * x^k that take the value M(n) at x = 1. The coefficients of x^n are the aerated Catalan numbers A126120.
Variants are the irregular triangle A055151 with zeros deleted, A097610 with reversed rows, A107131 and A080159.
In the literature the name 'Motzkin triangle' is also used for the triangle A026300, which is generated from the powers of the generating function of the Motzkin numbers.

Examples

			Triangle M(n, k) starts:
[0] 1;
[1] 1, 0;
[2] 1, 0,  1;
[3] 1, 0,  3, 0;
[4] 1, 0,  6, 0,   2;
[5] 1, 0, 10, 0,  10, 0;
[6] 1, 0, 15, 0,  30, 0,   5;
[7] 1, 0, 21, 0,  70, 0,  35, 0;
[8] 1, 0, 28, 0, 140, 0, 140, 0,  14;
[9] 1, 0, 36, 0, 252, 0, 420, 0, 126, 0;
		

Crossrefs

Cf. A001006 (Motzkin numbers), A026300 (Motzkin gf. triangle), A126120 (aerated Catalan), A000108 (Catalan).

Programs

  • Maple
    CatalanNumber := n -> binomial(2*n, n)/(n + 1):
    M := (n, k) -> ifelse(irem(k, 2) = 1, 0, CatalanNumber(k/2)*binomial(n, k)):
    for n from 0 to 9 do seq(M(n, k), k = 0..n) od;
    # Alternative, as coefficients of polynomials:
    p := n -> hypergeom([(1 - n)/2, -n/2], [2], (2*x)^2):
    seq(print(seq(coeff(simplify(p(n)), x, k), k = 0..n)), n = 0..9);
    # Using the exponential generating function:
    egf := exp(x)*BesselI(1, 2*x*t)/(x*t): ser:= series(egf, x, 11):
    seq(print(seq(coeff(simplify(n!*coeff(ser, x, n)), t, k), k = 0..n)), n = 0..9);
  • Python
    from functools import cache
    @cache
    def M(n: int, k: int) -> int:
        if k %  2: return 0
        if n <  3: return 1
        if n == k: return (2 * (n - 1) * M(n - 2, n - 2)) // (n // 2 + 1)
        return (M(n - 1, k) * n) // (n - k)
    for n in range(10): print([M(n, k) for k in range(n + 1)])

Formula

Let p(n, x) = hypergeom([(1 - n)/2, -n/2], [2], (2*x)^2).
p(n, 1) = A001006(n); p(n, sqrt(2)) = A025235(n); p(n, 2) = A091147(n).
p(2, n) = A002522(n); p(3, n) = A056107(n).
p(n, n) = A359649(n); 2^n*p(n, 1/2) = A000108(n+1).
M(n, k) = [x^k] p(n, x).
M(n, k) = [t^k] (n! * [x^n] exp(x) * BesselI(1, 2*t*x) / (t*x)).
M(n, k) = [t^k][x^n] ((1 - x - sqrt((x-1)^2 - (2*t*x)^2)) / (2*(t*x)^2)).
M(n, n) = A126120(n).
M(n, n-1) = A138364(n), the number of Motzkin n-paths with exactly one flat step.
M(2*n, 2*n) = A000108(n), the number of peakless Motzkin paths having a total of n up and level steps.
M(4*n, 2*n) = A359647(n), the central terms without zeros.
M(2*n+2, 2*n) = A002457(n) = (-4)^n * binomial(-3/2, n).
Sum_{k=0..n} M(n - k, k) = A023426(n).
Sum_{k=0..n} k * M(n, k) = 2*A014531(n-1) = 2*GegenbauerC(n - 2, -n, -1/2).
Sum_{k=0..n} i^k*M(n, k) = A343773(n), (i the imaginary unit), is the excess of the number of even Motzkin n-paths (A107587) over the odd ones (A343386).
Sum_{k=0..n} Sum_{j=0..k} M(n, j) = A189912(n).
Sum_{k=0..n} Sum_{j=0..k} M(n, n-j) = modified A025179(n).
For a recursion see the Python program.

A025567 a(n) = T(n,n+1), where T is the array defined in A025564.

Original entry on oeis.org

1, 4, 13, 40, 120, 356, 1050, 3088, 9069, 26620, 78133, 229384, 673699, 1979628, 5820195, 17121312, 50394579, 148413996, 437324919, 1289330520, 3803175474, 11223840012, 33139076292, 97889042384, 289276841475, 855205791076, 2529279459099
Offset: 1

Keywords

Crossrefs

Pairwise sums of A014531.

Programs

  • Mathematica
    T[, 0] = 1; T[1, 1] = 2; T[n, k_] /; 0 <= k <= 2n := T[n, k] = T[n-1, k-2] + T[n-1, k-1] + T[n-1, k]; T[, ] = 0;
    a[n_] := T[n+1, n+3];
    Array[a, 27] (* Jean-François Alcover, Oct 30 2018 *)
  • PARI
    x='x+O('x^66); Vec((x^2-1-sqrt(1+x)*(x^2+2*x-1)/sqrt(1-3*x))/(2*x^3)) \\ Joerg Arndt, May 01 2013

Formula

G.f.: (x^2-1-sqrt(1+x)*(x^2+2*x-1)/sqrt(1-3*x))/(2*x^3). - Mark van Hoeij, May 01 2013
Conjecture: (n+3)*a(n) +4*(-n-2)*a(n-1) +2*a(n-2) +8*(n-1)*a(n-3) +3*(n-3)*a(n-4)=0. - R. J. Mathar, Apr 03 2015
Conjecture: (n-1)*(n-2)*(n+3)*a(n) -2*n*(n-2)*(n+2)*a(n-1) -3*n*(n-1)^2*a(n-2)=0. - R. J. Mathar, Apr 03 2015
a(n) ~ 2 * 3^(n + 1/2) / sqrt(Pi*n). - Vaclav Kotesovec, May 02 2024
Showing 1-10 of 14 results. Next