A000957 -id:A000957 - cp's OEIS frontend

A124575 Triangle read by rows: row n is the first row of the matrix M[n]^(n-1), where M[n] is the n X n tridiagonal matrix with main diagonal (2,4,4,...) and super- and subdiagonals (1,1,1,...).

1, 2, 1, 5, 6, 1, 16, 30, 10, 1, 62, 146, 71, 14, 1, 270, 717, 444, 128, 18, 1, 1257, 3582, 2621, 974, 201, 22, 1, 6096, 18206, 15040, 6718, 1800, 290, 26, 1, 30398, 93960, 85084, 43712, 14208, 2986, 395, 30, 1, 154756, 491322, 478008, 274140, 103530

Offset: 0

Gary W. Adamson & Roger L. Bagula, Nov 05 2006

Column k=0 yields A033543 (2nd binomial transform of the sequence A000957(n+1)). Row sums yield A133158. [Corrected by Philippe Deléham, Oct 24 2007, Dec 05 2009]
Triangle T(n,k), 0 <= k <= n, read by rows given by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = 2*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 4*T(n-1,k) + T(n-1,k+1) for k >= 1. - Philippe Deléham, Mar 27 2007
This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1)  +y*T(n-1,k) + T(n-1,k+1) for k >= 1. Other triangles arise from choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007

			Row 2 is (5,6,1) because M[3]= [2,1,0;1,4,1;0,1,4] and M[3]^2=[5,6,1;6,18,8;1,8,17].
Triangle starts:
    1;
    2,   1;
    5,   6,   1;
   16,  30,  10,   1;
   62, 146,  71,  14,  1;
  270, 717, 444, 128, 18, 1;

G. C. Greubel, Table of n, a(n) for the first 100 rows, flattened

Cf. A124576, A124574, A052179, A064613, A133158.

with(linalg): m:=proc(i,j) if i=1 and j=1 then 2 elif i=j then 4 elif abs(i-j)=1 then 1 else 0 fi end: for n from 3 to 11 do A[n]:=matrix(n,n,m): B[n]:=multiply(seq(A[n],i=1..n-1)) od: 1; 2,1; for n from 3 to 11 do seq(B[n][1,j],j=1..n) od; # yields sequence in triangular form

M[n_] := SparseArray[{{1, 1} -> 2, Band[{2, 2}] -> 4, Band[{1, 2}] -> 1, Band[{2, 1}] -> 1}, {n, n}]; row[1] = {1}; row[n_] := MatrixPower[M[n], n-1] // First // Normal; Table[row[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jan 09 2014 *)

T(n,k) = T(n-1,k-1) + 4*T(n-1,k) + T(n-1,k-1) for k >= 2.
Sum_{k=0..n} T(n,k)*(3*k+1) = 6^n. - Philippe Deléham, Mar 27 2007
Sum_{k>=0} T(m,k)*T(n,k) = T(m+n,0) = A033543(m+n). - Philippe Deléham, Nov 22 2009

Edited by N. J. A. Sloane, Dec 04 2006

A014300 Number of nodes of odd outdegree in all ordered rooted (planar) trees with n edges.

Original entry on oeis.org

1, 2, 7, 24, 86, 314, 1163, 4352, 16414, 62292, 237590, 909960, 3497248, 13480826, 52097267, 201780224, 783051638, 3044061116, 11851853042, 46208337584, 180383564228, 704961896036, 2757926215742, 10799653176704, 42326626862636, 166021623024584, 651683311373788

Offset: 1

Emeric Deutsch

Also total number of blocks of odd size in all Catalan(n) possible noncrossing partitions of [n].
Convolution of the sequence of central binomial coefficients 1,2,6,20,70,... (A000984) and of the sequence of Fine numbers 1,0,1,2,6,18,... (A000957).
Row sums of A119307. - Paul Barry, May 13 2006
Hankel transform is A079935. - Paul Barry, Jul 17 2009
Also for n>=1 the number of unimodal functions f:[n]->[n] with f(i)<>f(i+1). a(3) = 7: [1,2,1], [1,2,3], [1,3,1], [1,3,2], [2,3,1], [2,3,2], [3,2,1]. - Alois P. Heinz, May 23 2013
Also, number of sets of n rational numbers on [0,1) such that if x belongs to the set, the fractional part of 2x also belongs to it. - Jianing Song and Andrew Howroyd, May 18 2018
Let A(i, j) denote the infinite array such that the i-th row of this array is the sequence obtained by applying the partial sum operator i times to the function ((-1)^(n + 1) + 1)/2 for n > 0. Then A(n, n) equals a(n) for all n > 0. - John M. Campbell, Jan 20 2019
The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p >= 3 and positive integers n and k. - Peter Bala, Jan 07 2022

Alois P. Heinz, Table of n, a(n) for n = 1..500
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Hacène Belbachir and Abdelghani Mehdaoui, Diagonal sums in Pascal pyramid (1, 2, r), Les Annales RECITS (2019) Vol. 6, 45-52.
N. Dershowitz and S. Zaks, Ordered trees and non-crossing partitions, Discrete Math., 62 (1986), 215-218.
Emeric Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Index entries for sequences related to rooted trees

Cf. A059481, A000957, A000984, A072547, A119259, A119307, A079935, A333564.

[(&+[(-1)^(n-k)*Binomial(n+k-1, k-1): k in [0..n]]): n in [1..30]]; // G. C. Greubel, Feb 19 2019

a:= proc(n) a(n):= `if`(n<3, n, ((12-40*n+21*n^2) *a(n-1)+
       2*(3*n-1)*(2*n-3) *a(n-2))/ (2*(3*n-4)*n))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Oct 30 2012

Rest[CoefficientList[Series[2x/(1-4x+(1+2x)Sqrt[1-4x]),{x,0,40}],x]]  (* Harvey P. Dale, Apr 25 2011 *)
a[n_] := Sum[Binomial[2k, n-1], {k, 0, n-1}]; Array[a, 30] (* Jean-François Alcover, Dec 25 2015, after Paul Barry *)

a(n) = n--; sum(k=0, n, binomial(2*k,n)); \\ Michel Marcus, May 18 2018

from itertools import count, islice
def A014300_gen(): # generator of terms
    yield from (1,2)
    a, c = 1, 1
    for n in count(1):
        yield (a:=(3*n+5)*(c:=c*((n<<2)+2)//(n+2))-a>>1)
A014300_list = list(islice(A014300_gen(),20)) # Chai Wah Wu, Apr 26 2023

[sum((-1)^(n-k)*binomial(n+k-1, k-1) for k in (0..n)) for n in (1..30)] # G. C. Greubel, Feb 19 2019

a(n) = (binomial(2*n, n) + A000957(n))/3; [simplified by Alexander Burstein, Nov 24 2023]
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k-1). - Vladeta Jovovic, Aug 28 2002
G.f.: 2*z/(1-4*z+(1+2*z)*sqrt(1-4*z)).
a(n) = Sum_{j=0..floor((n-1)/2)} binomial(2*n-2*j-2, n-1).
2*a(n) + a(n-1) = (3*n-1)*Catalan(n-1). - Vladeta Jovovic, Dec 03 2004
a(n) = (-1)^n*Sum_{i=0..n} Sum_{j=n..2*n} (-1)^(i+j)*binomial(j, i). - Benoit Cloitre, Jun 18 2005
a(n) = Sum_{k=0..n} C(2*k,n) [offset 0]. - Paul Barry, May 13 2006
a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n+k-1,k-1). - Paul Barry, Jul 18 2006
From Paul Barry, Jul 17 2009: (Start)
a(n) = Sum_{k=0..n} C(2*n-k,n-k)*(1+(-1)^k)/2.
a(n) = Sum_{k=0..n} C(n+k,k)*(1+(-1)^(n-k))/2. (End)
a(n) is the coefficient of x^(n+1)*y^(n+1) in 1/(1- x^2*y/((1-2*x)*(1-y))). - Ira M. Gessel, Oct 30 2012
a(n) = -binomial(2*n,n-1)*hyper2F1([1,2*n+1],[n+2], 2). - Peter Luschny, Jul 25 2014
a(n) = [x^n] x/((1 - x^2)*(1 - x)^n). - Ilya Gutkovskiy, Oct 25 2017
a(n) ~ 4^n / (3*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 25 2017
D-finite with recurrence: 2*n*a(n) +(-3*n-4)*a(n-1) +2*(-9*n+19)*a(n-2) +4*(-2*n+5)*a(n-3)=0. - R. J. Mathar, Feb 20 2020
a(n) = A333564(n)/2^n. - Peter Bala, Apr 09 2020
a(n) = (1/2)*(binomial(2*n,n) - A072547(n)). - Peter Bala, Mar 28 2023

A072547 Main diagonal of the array in which first column and row are filled alternatively with 1's or 0's and then T(i,j) = T(i-1,j) + T(i,j-1).

Original entry on oeis.org

1, 0, 2, 6, 22, 80, 296, 1106, 4166, 15792, 60172, 230252, 884236, 3406104, 13154948, 50922986, 197519942, 767502944, 2987013068, 11641557716, 45429853652, 177490745984, 694175171648, 2717578296116, 10648297329692, 41757352712480

Offset: 1

Benoit Cloitre, Aug 05 2002

nonn

A Catalan transform of A078008 under the mapping g(x)->g(xc(x)). - Paul Barry, Nov 13 2004
Number of positive terms in expansion of (x_1 + x_2 + ... + x_{n-1} - x_n)^n. - Sergio Falcon, Feb 08 2007
Hankel transform is A088138(n+1). - Paul Barry, Feb 17 2009
Without the beginning "1", we obtain the first diagonal over the principal diagonal of the array notified by B. Cloitre in A026641 and used by R. Choulet in A172025, and from A172061 to A172066. - Richard Choulet, Jan 25 2010
Also central terms of triangles A108561 and A112465. - Reinhard Zumkeller, Jan 03 2014
With offset 0 and for p prime, the p-th term is divisible by p. - F. Chapoton, Dec 03 2021

			The array begins:
  1 0 1 0 1..
  0 0 1 1 2..
  1 1 2 3 5..
  0 1 3 6 11..
so sequence begins : 1, 0, 2, 6, ...

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
David Anderson, E. S. Egge, M. Riehl, L. Ryan, R. Steinke, and Y. Vaughan, Pattern Avoiding Linear Extensions of Rectangular Posets, arXiv:1605.06825 [math.CO], 2016.
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015. [It is only a conjecture that this is the same sequence. It would be nice to have a proof.]
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, J. Integer Sequ., Vol. 8 (2005), Article 05.4.5.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Colin Defant, Proofs of Conjectures about Pattern-Avoiding Linear Extensions, arXiv:1905.02309 [math.CO], 2019.
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)

Cf. A014300, A014301, A026641, A092785, A000957.

Cf. A026641, A172025, A172061, A172062, A172063, A172064, A172065, A172066. - Richard Choulet, Jan 25 2010

a072547 n = a108561 (2 * (n - 1)) (n - 1)
-- Reinhard Zumkeller, Jan 03 2014

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( x*(1 + Sqrt(1-4*x))/(Sqrt(1-4*x)*(3-Sqrt(1-4*x))) )); // G. C. Greubel, Feb 17 2019

taylor( (2/(3*sqrt(1-4*z)-1+4*z))*((1-sqrt(1-4*z))/(2*z))^(-1),z=0,42); for n from -1 to 40 do a(n):=sum('(-1)^(p)*binomial(2n-p+1,1+n-p)',p=0..n+1): od:seq(a(n),n=-1..40):od; # Richard Choulet, Jan 25 2010

CoefficientList[Series[(2/(3*Sqrt[1-4*x]-1+4*x))*((1-Sqrt[1-4*x]) /(2*x))^(-1), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 13 2014 *)
a[n_] := Binomial[2 n - 2, n] Hypergeometric2F1[1, 2 - n, n + 1, 1/2] / 2 + (-2)^(1 - n); Table[a[n], {n, 1, 26}] (* Peter Luschny, Dec 03 2021 *)

a(n) = (-1)^n*sum(k=0, n, binomial(-n, k));
vector(100, n, a(n-1)) \\ Altug Alkan, Oct 02 2015

a=(x*(1+sqrt(1-4*x))/(sqrt(1-4*x)*(3-sqrt(1-4*x)))).series(x, 30).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Feb 17 2019

If offset is 0, a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k). - Vladeta Jovovic, Feb 18 2003
G.f.: x*(1-x*C)/(1-2*x*C)/(1+x*C), where C = (1-sqrt(1-4*x))/(2*x) is g.f. for Catalan numbers (A000108). - Vladeta Jovovic, Feb 18 2003
a(n) = Sum_{j=0..floor((n-1)/2)} binomial(2*n-2*j-4, n-3). - Emeric Deutsch, Jan 28 2004
a(n) = A108561(2*(n-1),n-1). - Reinhard Zumkeller, Jun 10 2005
a(n) = (-1)^n*Sum_{k=0..n} binomial(-n,k) (offset 0). - Paul Barry, Feb 17 2009
Other form of the G.f: f(z) = (2/(3*sqrt(1-4*z) -1 +4*z))*((1 -sqrt(1-4*z))/(2*z))^(-1). - Richard Choulet, Jan 25 2010
D-finite with recurrence 2*(-n+1)*a(n) + (9*n-17)*a(n-1) + (-3*n+19)*a(n-2) + 2*(-2*n+7)*a(n-3) = 0. - R. J. Mathar, Nov 30 2012
From Peter Bala, Oct 01 2015: (Start)
a(n) = [x^n] ((1 - x)^2/(1 - 2*x))^n.
Exp( Sum_{n >= 1} a(n+1)*x^n/n ) = 1 + x^2 + 2*x^3 + 6*x^4 + 18*x^5 + ... is the o.g.f for A000957. (End)
a(n) = binomial(2*n-2, n)*hypergeom([1, 2-n], [n+1], 1/2) / 2 + (-2)^(1-n). - Peter Luschny, Dec 03 2021
a(n) = 2 * A014301(n-1) for n>=3. - Alois P. Heinz, Dec 27 2023

Corrected and extended by Vladeta Jovovic, Feb 17 2003

A126093 Inverse binomial matrix applied to A110877.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 2, 6, 4, 1, 6, 18, 15, 6, 1, 18, 57, 54, 28, 8, 1, 57, 186, 193, 118, 45, 10, 1, 186, 622, 690, 474, 218, 66, 12, 1, 622, 2120, 2476, 1856, 976, 362, 91, 14, 1, 2120, 7338, 8928, 7164, 4170, 1791, 558, 120, 16, 1

Offset: 0

Philippe Deléham, Mar 03 2007

Diagonal sums are A065601. - Philippe Deléham, Mar 05 2007

This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k>=1 . Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007

			Triangle begins:
     1;
     0,    1;
     1,    2,    1;
     2,    6,    4,    1;
     6,   18,   15,    6,    1;
    18,   57,   54,   28,    8,    1;
    57,  186,  193,  118,   45,   10,   1;
   186,  622,  690,  474,  218,   66,  12,   1;
   622, 2120, 2476, 1856,  976,  362,  91,  14,  1;
  2120, 7338, 8928, 7164, 4170, 1791, 558, 120, 16, 1;
Production matrix begins
  0, 1;
  1, 2, 1;
  0, 1, 2, 1;
  0, 0, 1, 2, 1;
  0, 0, 0, 1, 2, 1;
  0, 0, 0, 0, 1, 2, 1;
  0, 0, 0, 0, 0, 1, 2, 1;
  0, 0, 0, 0, 0, 0, 1, 2, 1;
  0, 0, 0, 0, 0, 0, 0, 1, 2, 1;
- _Philippe Deléham_, Nov 07 2011

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Yidong Sun and Luping Ma, Minors of a class of Riordan arrays related to weighted partial Motzkin paths, Eur. J. Comb. 39, 157-169 (2014), Table 2.2.

T[0, 0, x_, y_]:= 1; T[n_, 0, x_, y_]:= x*T[n-1,0,x,y] + T[n-1,1,x,y]; T[n_, k_, x_, y_]:= T[n, k, x, y]= If[k<0 || k>n, 0, T[n-1,k-1,x,y] + y*T[n-1,k,x,y] + T[n-1,k+1,x,y]]; Table[T[n,k,0,2], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Apr 21 2017 *)

@CachedFunction
def T(n, k, x, y):
    if (k<0 or k>n): return 0
    elif (n==0 and k==0): return 1
    elif (k==0): return x*T(n-1,0,x,y) + T(n-1,1,x,y)
    else: return T(n-1,k-1,x,y) + y*T(n-1,k,x,y) + T(n-1,k+1,x,y)
[[T(n,k,0,2) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jan 27 2020

Triangle T(n,k), 0<=k<=n, read by rows defined by : T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0) = T(n-1,1), T(n,k) = T(n-1,k-1) + 2*T(n-1,k) + T(n-1,k+1) for k>=1.
Sum_{k=0..n} T(m,k)*T(n,k) = T(m+n,0) = A000957(m+n+1).
Sum_{k=0..n-1} T(n,k) = A026641(n), for n>=1. - Philippe Deléham, Mar 05 2007
Sum_{k=0..n} T(n,k)*(3k+1) = 4^n. - Philippe Deléham, Mar 22 2007

A014301 Number of internal nodes of even outdegree in all ordered rooted trees with n edges.

Original entry on oeis.org

0, 1, 3, 11, 40, 148, 553, 2083, 7896, 30086, 115126, 442118, 1703052, 6577474, 25461493, 98759971, 383751472, 1493506534, 5820778858, 22714926826, 88745372992, 347087585824, 1358789148058, 5324148664846, 20878676356240, 81937643449468, 321786401450268

Offset: 1

Emeric Deutsch

nonn

Number of protected vertices in all ordered rooted trees with n edges. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants. - Emeric Deutsch, Aug 20 2008
1,3,11,... gives the diagonal sums of A111418. Hankel transform of a(n) is A128834. Hankel transform of a(n+1) is A187340. - Paul Barry, Mar 08 2011
a(n) = A035317(2*n-1,n-1) for n > 0. - Reinhard Zumkeller, Jul 19 2012
Apparently the number of peaks in all Dyck paths of semilength n+1 that are the same height as the preceding peak. - David Scambler, Apr 22 2013
Define an infinite triangle by T(n,0)=A001045(n) (the first column) and T(r,c) = Sum_{k=c-1..r} T(k,c-1) (the sum of all the terms in the preceding column down to row r). Then T(n,n)=a(n+1). The triangle is 0; 1,1; 1,2,3; 3,5,8,11; 5,10,18,29,40; 11,21,39,68,108,148;... Example: T(5,2)=39=the sum of the terms in column 1 from T(1,1) to T(5,1), namely, 1+2+5+10+21. - J. M. Bergot, May 17 2013
Also for n>=1 the number of unimodal functions f:[n]->[n] with f(1)<>1 and f(i)<>f(i+1). a(4) = 11: [2,3,2,1], [2,3,4,1], [2,3,4,2], [2,3,4,3], [2,4,2,1], [2,4,3,1], [2,4,3,2], [3,4,2,1], [3,4,3,1], [3,4,3,2], [4,3,2,1]. - Alois P. Heinz, May 23 2013

G. C. Greubel, Table of n, a(n) for n = 1..1000
Gi-Sang Cheon and Louis W. Shapiro, Protected points in ordered trees, Appl. Math. Letters, 21, 2008, 516-520.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020, Corollary 3.4.
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
Index entries for sequences related to rooted trees

Cf. A059481, A026641, A143362, A143363.

[(1/2)*(&+[(-1)^(n-k)*Binomial(n+k-1,k): k in [0..n]]): n in [1..30]]; // G. C. Greubel, Jan 15 2018

Rest[CoefficientList[Series[(1-2*x-Sqrt[1-4*x])/(3*Sqrt[1-4*x]-1+4*x), {x, 0, 50}], x]] (* G. C. Greubel, Jan 15 2018 *)

x='x+O('x^30); Vec((1-2*x-sqrt(1-4*x))/(3*sqrt(1-4*x)-1+4*x)) \\ G. C. Greubel, Jan 15 2018

from itertools import count, islice
def A014301_gen(): # generator of terms
    yield from (0,1)
    a, b, c = 0, 3, 1
    for n in count(1):
        yield ((b:=b*((n<<1)+3<<1)//(n+2))-(a:=(c:=c*((n<<2)+2)//(n+2))-a>>1))//3
A014301_list = list(islice(A014301_gen(),20)) # Chai Wah Wu, Apr 27 2023

a(n) = binomial(2*n-1, n)/3 - A000957(n)/3;
a(n) = (1/2)*Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k). - Vladeta Jovovic, Aug 28 2002
From Emeric Deutsch, Jan 26 2004: (Start)
G.f.: (1-2*z-sqrt(1-4*z))/(3*sqrt(1-4*z)-1+4*z).
a(n) = [A026641(n) - A026641(n-1)]/3 for n>1. (End)
a(n) = (1/2)*Sum_{j=0..floor(n/2)} binomial(2n-2j-2, n-2).
a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n+k,k-1). - Paul Barry, Jul 18 2006
D-finite with recurrence: 2*n*a(n) +(-9*n+8)*a(n-1) +(3*n-16)*a(n-2) +2*(2*n-5)*a(n-3)=0. - R. J. Mathar, Dec 03 2012

A000958 Number of ordered rooted trees with n edges having root of odd degree.

Original entry on oeis.org

1, 1, 3, 8, 24, 75, 243, 808, 2742, 9458, 33062, 116868, 417022, 1500159, 5434563, 19808976, 72596742, 267343374, 988779258, 3671302176, 13679542632, 51134644014, 191703766638, 720629997168, 2715610275804, 10256844598900, 38822029694628, 147229736485868

Offset: 1

N. J. A. Sloane

a(n) is the number of Dyck n-paths containing no peak at height 2 before the first return to ground level. Example: a(3)=3 counts UUUDDD, UDUUDD, UDUDUD. - David Callan, Jun 07 2006
Also number of order trees with n edges and having no even-length branches starting at the root. - Emeric Deutsch, Mar 02 2007
Convolution of the Catalan sequence 1,1,2,5,14,42,... (A000108) and the Fine sequence 1,0,1,2,6,18,... (A000957). a(n) = A127541(n,0). - Emeric Deutsch, Mar 02 2007
The Catalan transform of A008619. - R. J. Mathar, Nov 06 2008
Hankel transform is F(2n+1). - Paul Barry, Dec 01 2008
Starting with offset 2 = iterates of M * [1,1,0,0,0,...] where M = a tridiagonal matrix with [0,2,2,2,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - Gary W. Adamson, Jan 09 2009
Equals INVERT transform of A032357. - Gary W. Adamson, Apr 10 2009
a(n) is the number of Dyck paths of semilength n+1 that have equal length inclines incident with the first return to ground level. For example, for UUDDUUDDUD these inclines are DD and UU (steps 3 through 6), and a(3)=3 counts UDUDUUDD, UDUDUDUD, UUDDUUDD. - David Callan, Aug 23 2011
a(n) is the number of imprimitive Dyck paths of semilength n+1 for which the heights of the first and the last peaks coincide, this gives the connection to A193215. - Volodymyr Mazorchuk, Aug 27 2011
a(n) is the number of parking functions of size n-1 avoiding the patterns 123 and 132. - Lara Pudwell, Apr 10 2023
a(n) is the number of Dyck paths of semilength n that contain no UDUs at ground level. For example, a(3) = 3 counts UUUDDD, UUDUDD, UUDDUD. - David Callan, Feb 02 2024

Ki Hang Kim, Douglas G. Rogers, and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013) - N. J. A. Sloane, Jun 05 2012
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 200 terms from T. D. Noe)
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Paul Barry, Moment sequences, transformations, and Spidernet graphs, arXiv:2307.00098 [math.CO], 2023.
Paul Barry, The Triple Riordan Group, arXiv:2412.05461 [math.CO], 2024. See pp. 6, 10.
Dennis E. Davenport, Louis W. Shapiro, and Leon C. Woodson, A bijection between the triangulations of convex polygons and ordered trees, Integers (2020) Vol. 20, Article #A8.
Emeric Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.
T. Fine, Extrapolation when very little is known about the source, Information and Control 16 (1970), 331-359.
D. G. Rogers, Similarity relations on finite ordered sets, J. Combin. Theory, A 23 (1977), 88-98. Erratum, loc. cit., 25 (1978), 95-96.
Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186. See Table 2.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.
Index entries for sequences related to rooted trees

First column of A065602, A098747 and A362563. Row sums of A362563.
Cf. A127541, A127539, A000108, A000957, A032357.
Partial differences give A118973 (for n>=1).

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (1-x-(1+x)*Sqrt(1-4*x))/(2*x*(x+2)) )); // G. C. Greubel, Feb 27 2019

g:=(1-x-(1+x)*sqrt(1-4*x))/2/x/(x+2): gser:=series(g,x=0,30): seq(coeff(gser,x,n),n=1..26); # Emeric Deutsch, Mar 02 2007
A958 := n -> add(binomial(2*n-2*k-2, n-1)*(2*k+1)/n, k=0..floor((n-1)/2)): seq(A958(n), n=1..28); # Johannes W. Meijer, Jul 26 2013
A000958List := proc(m) local A, P, n; A := [1,1]; P := [1,1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-2]]);
A := [op(A), P[-1]] od; A end: A000958List(28); # Peter Luschny, Mar 26 2022
# next Maple program:
b:= proc(n) option remember; `if`(n<3, n*(2-n),
      ((7*n-12)*b(n-1)+(4*n-6)*b(n-2))/(2*n))
    end:
a:= n-> b(n)+b(n+1):
seq(a(n), n=1..32);  # Alois P. Heinz, Apr 26 2023

nn = 30; Rest[CoefficientList[Series[(1-x-(1+x)*Sqrt[1-4*x])/(2*x*(x+2)), {x, 0, nn}], x]] (* T. D. Noe, May 09 2012 *)

my(x='x+O('x^30)); Vec((1-x-(1+x)*sqrt(1-4*x))/(2*x*(x+2))) \\ G. C. Greubel, Feb 27 2019

from itertools import accumulate
def A000958_list(size):
    if size < 1: return []
    L, accu = [], [1]
    for n in range(size-1):
        accu = list(accumulate(accu+[-accu[-1]]))
        L.append(accu[n])
    return L
print(A000958_list(29)) # Peter Luschny, Apr 25 2016

from itertools import count, islice
def A000958_gen(): # generator of terms
    yield 1
    a, c = 0, 1
    for n in count(1):
        yield (c:=c*((n<<2)+2)//(n+2))+a>>1
        a = c-a>>1
A000958_list = list(islice(A000958_gen(),20)) # Chai Wah Wu, Apr 26 2023

a=((1-x-(1+x)*sqrt(1-4*x))/(2*x*(x+2))).series(x, 30).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Feb 27 2019

a(n) = A000957(n) + A000957(n+1).
G.f.: (1-x-(1+x)*sqrt(1-4*x))/(2*x*(x+2)). - Paul Barry, Jan 26 2007
G.f.: z*C/(1-z^2*C^2), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function. - Emeric Deutsch, Mar 02 2007
a(n+1) = Sum_{k=0..floor(n/2)} A039599(n-k,k). - Philippe Deléham, Mar 13 2007
a(n) = (-1/2)^n*(-2 - 5*Sum_{k=1..n-1} (-8)^k*Gamma(1/2+k)*(4/5+k)/(sqrt(Pi)*Gamma(k+3))). - Mark van Hoeij, Nov 11 2009
a(n) + a(n+1) = A135339(n+1). - Philippe Deléham, Dec 02 2009
From Gary W. Adamson, Jul 14 2011: (Start)
a(n) = sum of top row terms in M^(n-1), where M = the following infinite square production matrix:
  0, 1, 0, 0, 0, 0, ...
  1, 1, 1, 0, 0, 0, ...
  1, 1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, 1, ...
  ... (End)
D-finite with recurrence 2*(n+1)*a(n) + (-5*n+3)*a(n-1) + (-11*n+21)*a(n-2) + 2 *(-2*n+5)*a(n-3) = 0. - R. J. Mathar, Dec 03 2012
a(n) ~ 5*4^n/(9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2013
a(n) = Catalan(n-1)*h(n-1) for n>=2 where h(n) = hypergeom([1,3/2,-n/2,(1-n)/2],[1/2,-n,-n+1/2], 1). - Peter Luschny, Apr 25 2016

A065600 Triangle T(n,k) giving number of Dyck paths of length 2n with exactly k hills (0 <= k <= n).

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 6, 4, 3, 0, 1, 18, 13, 6, 4, 0, 1, 57, 40, 21, 8, 5, 0, 1, 186, 130, 66, 30, 10, 6, 0, 1, 622, 432, 220, 96, 40, 12, 7, 0, 1, 2120, 1466, 744, 328, 130, 51, 14, 8, 0, 1, 7338, 5056, 2562, 1128, 455, 168, 63, 16, 9, 0, 1, 25724, 17672, 8942, 3941, 1590, 602, 210, 76, 18, 10, 0, 1

Offset: 0

N. J. A. Sloane, Dec 02 2001

T(n,k) is the number of Łukasiewicz paths of length n having k level steps (i.e., (1,0)) on the x-axis. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1)=2 because we have HUD and UDH, where H=(1,0), U(1,1) and D=(1,-1). - Emeric Deutsch, Jan 06 2005
The summand i*binomial(k+i,i)*binomial(2*n-2*k-2*i,n-k)/(n-k-i) in the Maple formula below counts Dyck n-paths containing k low peaks and k+i returns altogether. For example, with n=3, k=1, i=1, it counts the 2 paths UDUUDD, UUDDUD: each has k=1 low peaks and k+i=2 returns to ground level. - David Callan, Nov 02 2005
Renewal array for the Fine numbers: Riordan array (f(x)/x,f(x)) where f(x) is the g.f. for A000957. Row sums are the Catalan numbers A000108. - Paul Barry, Oct 30 2006, Jan 27 2009
T(n,k) is the number of 321-avoiding permutations of [n] having k fixed points. Example: T(4,2)=3 because we have 1243, 1324 and 2134. T(n,k) is the number of Dyck paths of semilength n having k centered tunnels. Example: T(4,2)=3 because we have UD(U)(U)(D)(D)UD, (U)UD(U)(D)UD(D) and (U)(U)UDUD(D)(D) (the extremities of the centered tunnels are shown between parentheses). - Emeric Deutsch, Sep 06 2007
Inverse of Riordan array ((1-2x)/(1-x)^2,x(1-2x)/(1-x)^2); see A124394. - Paul Barry, Jan 27 2009
Triangle read by rows, product of A033184 and A130595 considered as infinite lower triangular arrays; A065600 = A033184*A130595. - Philippe Deléham, Dec 07 2009
T(n,k) is the number of ordered, unlabeled, rooted trees with n+1 nodes that have exactly k subtrees of size 1.  A subtree of size 1 is a subtree attached to the root that consists of only a single node.  Cf. A000957 (column 1). - Geoffrey Critzer, Sep 16 2013
Also the convolution triangle of the Fine numbers A000957. - Peter Luschny, Oct 08 2022

			From _Philippe Deléham_, Feb 23 2012: (Start)
Triangle begins:
   1;
   0,  1;
   1,  0,  1;
   2,  2,  0,  1;
   6,  4,  3,  0,  1;
  18, 13,  6,  4,  0,  1;
  57, 40, 21,  8,  5,  0,  1; (End)
T(4,2)=3 because we have (UD)(UD)UUDD, (UD)UUDD(UD) and UUDD(UD)(UD), where U=(1,1), D=(1,-1) (the hills, i.e., peaks at level 1, are shown between parentheses).

Alois P. Heinz, Rows n = 0..200, flattened
E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.
Naiomi Cameron, J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.
S. Elizalde and I. Pak, Bijections for refined restricted permutations, Journal of Combinatorial Theory Ser. A, 105, 2004, 207-219.
FindStat - Combinatorial Statistic Finder, The number of centered tunnels of a Dyck path.
Shishuo Fu, Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
B. Hackl, H. Prodinger, Growing and destroying Catalan-Stanley trees, arxiv:1704.03734 [math.CO] (2017), proposition 2.1
R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 235.
A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
Index entries for sequences related to Łukasiewicz

First columns are A000957, A065601, A294527.

T := proc(n,k) if k0, b(x-1, y-1, 0)*`if`(t*y=1, z, 1), 0)+
      `if`(y (p-> seq(coeff(p, z, i), i=0..n))(b(n+n, 0$2)):
seq(T(n), n=0..12);  # Alois P. Heinz, Nov 02 2017
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, A000957); # Peter Luschny, Oct 08 2022

t[n_, k_] := If[ kJean-François Alcover, Dec 14 2011, after Maple *)
nn=10;g=(1-(1-4x)^(1/2))/2;CoefficientList[Series[x/(1-(g-x+y x)),{x,0,nn}],{x,y}]//Grid (* Geoffrey Critzer, Sep 16 2013 *)
T[ n_, k_] := If[ k < 0 || k > n, 0, Coefficient[ SeriesCoefficient[ Series[ 2 / (1 + 2*x + Sqrt[1 - 4*x] - 2*x*y), {x, 0, n}], {x, 0, n}], y, k]]; (* Michael Somos, Jun 01 2016 *)

{T(n, k) = if( k<0 || k>n, 0, polcoeff( polcoeff( 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y) + x * O(x^n), n), k))}; /* Michael Somos, Jun 01 2016 */

See Maple line.
G.f.: (1 - (1 - 4*x)^(1/2))/(x*(3 - y + (1 - 4*x)^(1/2)*(y-1))) = Sum_{n>=0, k>=0} T(n, k)x^n*y^k. - David Callan, Aug 17 2004
G.f.: 1/(1-xy-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-.... (continued fraction). - Paul Barry, Jan 27 2009
G.f.: ((1-sqrt(1-4*x))/(3-sqrt(1-4*x)))^k = Sum_{n>=k} T(n+1,k+1)*x^n, where T(n,k) = (Sum_{i=0..n-k} (-1)^i*(k+i+1)*binomial(k+i,i)*binomial(2*n-k-i,n))/(n+1). - Vladimir Kruchinin, Dec 20 2011
T(n,k) = T(n-1,k-1) + Sum_{i>=0} T(n-1,k+1+i)*2^i. - Philippe Deléham, Feb 23 2012
G.f.: 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y). - Michael Somos, Jun 01 2016

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003

A064310 Generalized Catalan numbers C(-1; n).

Original entry on oeis.org

1, 1, 0, 1, -2, 6, -18, 57, -186, 622, -2120, 7338, -25724, 91144, -325878, 1174281, -4260282, 15548694, -57048048, 210295326, -778483932, 2892818244, -10786724388, 40347919626, -151355847012, 569274150156

Offset: 0

Wolfdieter Lang, Sep 21 2001

See triangle A064334 with columns m built from C(-m; n), m >= 0, also for Derrida et al. references.

Unsigned sequence with a(0) := 0 is A000957 (Fine).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. [_N. J. A. Sloane_, Oct 08 2012]
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017).
P. Pagacz and M. Wojtylak, On the spectral properties of a class of H-selfadjoint random matrices and the underlying combinatorics, arXiv:1310.2122 [math.PR], 2013.

Cf. A000108, A000957, A039599, A106566.

[1] cat [(1 +(&+[(-2)^k*Binomial(2*k,k)/(k+1): k in [0..n-1]]))/2^n: n in [1..30]]; // G. C. Greubel, Feb 27 2019

a[n_]:= (1/2)^n*(1 + Sum[ CatalanNumber[k]*(-2)^k, {k, 0, n-1}]); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 17 2013 *)

{a(n) = (1 + sum(k=0, n-1, (-2)^k*binomial(2*k,k)/(k+1)))/2^n};
vector(30, n, n--; a(n)) \\ G. C. Greubel, Feb 27 2019

from itertools import count, islice
def A064310_gen(): # generator of terms
    yield from (1,1,0)
    a, c = 0, 1
    for n in count(1):
        yield (a:=(c:=c*((n<<2)+2)//(n+2))-a>>1)*(1 if n&1 else -1)
A064310_list = list(islice(A064310_gen(),20)) # Chai Wah Wu, Apr 27 2023

[1] + [(1 +sum((-2)^k*catalan_number(k) for k in (0..n-1)))/2^n for n in (1..30)] # G. C. Greubel, Feb 27 2019

a(n) = Sum_{m=0..n-1} (-1)^m*(n-m)*binomial(n-1+m, m)/n.
a(n) = ((1/2)^n)*(1 + Sum_{k=0..n-1} C(k)*(-2)^k ), n >= 1, a(0)= 1, with C(n)=A000108(n) (Catalan).
G.f.: (1+x*c(-x)/2)/(1-x/2) = 1/(1-x*c(-x)) with c(x) g.f. of Catalan numbers A000108.
a(n) = Sum_{k=0..n} (-1)^(n-k)*A106566(n, k). - Philippe Deléham, Sep 18 2005
(-1)^n*a(n) = Sum_{k=0..n} A039599(n,k)*(-2)^k. - Philippe Deléham, Mar 13 2007
Conjecture: 2*n*a(n) + (7*n-12)*a(n-1) + 2*(-2*n+3)*a(n-2) = 0. - R. J. Mathar, Dec 02 2012

A100754 Triangle read by rows: T(n, k) = number of hill-free Dyck paths (i.e., no peaks at height 1) of semilength n and having k peaks.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 8, 8, 1, 1, 13, 29, 13, 1, 1, 19, 73, 73, 19, 1, 1, 26, 151, 266, 151, 26, 1, 1, 34, 276, 749, 749, 276, 34, 1, 1, 43, 463, 1781, 2762, 1781, 463, 43, 1, 1, 53, 729, 3758, 8321, 8321, 3758, 729, 53, 1, 1, 64, 1093, 7253, 21659, 31004, 21659, 7253, 1093, 64, 1

Offset: 2

Emeric Deutsch, Jan 14 2005

Row n has n - 1 terms. Row sums yield the Fine numbers (A000957).
Related to the number of certain sets of non-crossing partitions for the root system A_n (p. 11, Athanasiadis and Savvidou). - Tom Copeland, Oct 19 2014
T(n,k) is the number of permutations pi of [n-1] with k - 1 descents such that s(pi) avoids the patterns 132, 231, and 312, where s is West's stack-sorting map. - Colin Defant, Sep 16 2018
The absolute values of the polynomials at -1 and j (cube root of 1) seem to be given by A126120 and A005043. - F. Chapoton, Nov 16 2021
Don Knuth observes that this sequence also arrises from the enumeration of restricted max-and-min-closed relations, only there it appears as an array read by antidiagonals: see the Knuth "Notes" link and A372068. Knuth also gives a formula expressing the array A372368 in terms of this array. He also reports that there is strong experimental evidence that the n-th term of row m in this array is a polynomial of degree 2*m-2 in n. - N. J. A. Sloane, May 12 2024

			T(4, 2) = 4 because we have UU*DDUU*DD, UU*DUU*DDD, UUU*DDU*DD and UUU*DU*DDD, where U = (1, 1), D = (1,-1) and * indicates the peaks.
Triangle starts:
   1;
   1,  1;
   1,  4,   1;
   1,  8,   8,    1;
   1, 13,  29,   13,    1;
   1, 19,  73,   73,   19,    1;
   1, 26, 151,  266,  151,   26,    1;
   1, 34, 276,  749,  749,  276,   34,   1;
   1, 43, 463, 1781, 2762, 1781,  463,  43,  1;
   1, 53, 729, 3758, 8321, 8321, 3758, 729, 53, 1;
   ...
As an array (for which the rows of the preceding triangle are the antidiagonals):
   1,  1,    1,     1,      1,      1,       1,        1,        1, ...
   1,  4,    8,    13,     19,     26,      34,       43,       53, ...
   1,  8,   29,    73,    151,    276,     463,      729,     1093, ...
   1, 13,   73,   266,    749,   1781,    3758,     7253,    13061, ...
   1, 19,  151,   749,   2762,   8321,   21659,    50471,   107833, ...
   1, 26,  276,  1781,   8321,  31004,   97754,   271125,   679355, ...
   1, 34,  463,  3758,  21659,  97754,  367285,  1196665,  3478915, ...
   1, 43,  729,  7253,  50471, 271125, 1196665,  4526470, 15118415, ...
   1, 53, 1093, 13061, 107833, 679355, 3478915, 15118415, 57500480, ...
   ...

Alois P. Heinz, Rows n = 2..142, flattened
C. Athanasiadis and C. Savvidou, The local h-vector of the cluster subdivision of a simplex, arXiv preprint arXiv:1204.0362 [math.CO], 2012.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
D. E. Knuth, Notes on four arrays of numbers arising from the enumeration of CRC constraints and min-and-max-closed constraints, May 06 2024

Cf. A000957, A108263, A132081.

See also A099594, A272644, A372066, A372067, A372068.

T := (n, k) -> add((j/(n-j))*binomial(n-j, k-j)*binomial(n-j,k), j=0..min(k,n-k)): for n from 2 to 13 do seq(T(n, k), k = 1..n-1) od; # yields the sequence in triangular form

T[n_, k_] := Sum[(j/(n-j))*Binomial[n-j, k-j]*Binomial[n-j, k], {j, 0, Min[k, n-k]}]; Table[T[n, k], {n, 2, 13}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Feb 19 2017, translated from Maple *)

T(n, k) = Sum_{j=0..min(k, n-k)} (j/(n-j)) * C(n-j, k-j) * C(n-j, k), n >= 2.
G.f.: t*z*r/(1 - t*z*r), where r = r(t, z) is the Narayana function defined by r = z*(1 + r)*(1 + t*r).
From Tom Copeland, Oct 19 2014: (Start)
With offset 0 for A108263 and offset 1 for A132081, row polynomials of this entry P(n, x) = Sum_{i} A108263(n, i)*x^i*(1 + x)^(n - 2*i) = Sum_{i} A132081(n - 2, i)*x^i*(1 + x)^(n - 2*i).
E.g., P(4, x) = 1*x*(1 + x)^(4 - 2*1) + 2*x^2*(1 + x)^(4 - 2*2) = x + 4*x^2 + x^3.
Equivalently, let Q(n, x) be the row polynomials of A108263. Then P(n, x) = (1 + x)^n * Q(n, x/(1 + x)^2).
E.g., P(4, x) = (1 + x)^4 * (x/(1 + x)^2 + 2 * (x/(1 + x)^2)^2).
See Athanasiadis and Savvidou (p. 7). (End)

A117641 Number of 3-Motzkin paths of length n with no level steps at height 0.

Original entry on oeis.org

1, 0, 1, 3, 11, 42, 167, 684, 2867, 12240, 53043, 232731, 1031829, 4615542, 20805081, 94410363, 430945739, 1977366192, 9115261211, 42195093993, 196060049129, 914110333422, 4275222950221, 20051858039718, 94294269673861

Offset: 0

Louis Shapiro, Apr 10 2006

Hankel transform of this sequence forms A000012 = [1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007

			The a(4) = 11 paths are UUDD, UDUD and 9 of the form UXYD where each of X and Y are level steps in any of three colors.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Isaac DeJager, Madeleine Naquin, Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
L. W. Shapiro, C. J. Wang, A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height, JIS 12 (2009) 09.3.2.

Cf. A000957, A001006, A002212, A005043, A097331, A000108.

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (1+3*x-Sqrt(1-6*x+5*x^2))/(2*x*(3+x)) )); // G. C. Greubel, Apr 04 2019

CoefficientList[ Series[(1 + 3x - Sqrt[1 - 6x + 5x^2])/(2x^2 + 6x), {x, 0, 25}], x] (* Robert G. Wilson v *)

a(n):=sum(3^(n-2*j)*binomial(n+1,j)*binomial(n-j-1,n-2*j),j,0,floor(n/2))/(n+1); /*  Vladimir Kruchinin, Apr 04 2019 */

my(x='x+O('x^30)); Vec( (1+3*x-sqrt(1-6*x+5*x^2))/(2*x*(3+x)) ) \\ G. C. Greubel, Apr 04 2019

((1+3*x-sqrt(1-6*x+5*x^2))/(2*x*(3+x))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Apr 04 2019

G.f.: (1 +3*x -sqrt(1 -6*x +5*x^2))/(2*x*(3+x)).
G.f. as continued fraction is 1/(1-0*x-x^2/(1-3*x-x^2/(1-3*x-x^2/(1-3*x-x^2/(.....))))). - Paul Barry, Dec 02 2008
a(n) = A126970(n,0). - Philippe Deléham, Nov 24 2009
a(n) = Sum_{k=0..n} A091965(n,k)*(-3)^k. - Philippe Deléham, Nov 28 2009
a(n) = Sum_{k=1..n} Sum_{j=0..floor((n-2*k)/2)} 3^(n-2*k-2*j)*(k/(k+2*j))*binomial(k+2*j,j)*binomial(n-k-1,n-2*k-2*j). - José Luis Ramírez Ramírez, Mar 22 2012
D-finite with recurrence: 3*(n+1)*a(n) +(-17*n+10)*a(n-1) +9*(n-3)*a(n-2) +5*(n-2)*a(n-3)=0. - R. J. Mathar, Dec 02 2012
a(n) ~ 5^(n+3/2) / (32 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 13 2014
a(n) = 1/(n+1)*Sum_{j=0..floor(n/2)} 3^(n-2*j)*C(n+1,j)*C(n-j-1,n-2*j). - Vladimir Kruchinin, Apr 04 2019

cp's OEIS Frontend

A124575 Triangle read by rows: row n is the first row of the matrix M[n]^(n-1), where M[n] is the n X n tridiagonal matrix with main diagonal (2,4,4,...) and super- and subdiagonals (1,1,1,...).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A014300 Number of nodes of odd outdegree in all ordered rooted (planar) trees with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

A072547 Main diagonal of the array in which first column and row are filled alternatively with 1's or 0's and then T(i,j) = T(i-1,j) + T(i,j-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A126093 Inverse binomial matrix applied to A110877.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Sage

Formula

A014301 Number of internal nodes of even outdegree in all ordered rooted trees with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

A000958 Number of ordered rooted trees with n edges having root of odd degree.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs