A005717 -id:A005717 - cp's OEIS frontend

A239101 Riordan array read by rows, corresponding to array in A180562.

1, 2, 1, 4, 2, 1, 10, 5, 2, 1, 26, 13, 6, 2, 1, 70, 35, 16, 7, 2, 1, 192, 96, 45, 19, 8, 2, 1, 534, 267, 126, 56, 22, 9, 2, 1, 1500, 750, 357, 160, 68, 25, 10, 2, 1, 4246, 2123, 1016, 463, 198, 81, 28, 11, 2, 1, 12092, 6046, 2907, 1337, 586, 240, 95, 31

Offset: 0

N. J. A. Sloane, Mar 25 2014

Take lower triangle of square array in A180562, read from right to left.
Row sums are in A225034. - Philippe Deléham, Mar 25 2014
Riordan array (f(x), (f(x)-1)/(2*f(x))) where f(x) = sqrt((1+x)/(1-3*x)). - Philippe Deléham, Mar 25 2014

			Triangle begins:
1
2 1
4 2 1
10 5 2 1
26 13 6 2 1
70 35 16 7 2 1
192 96 45 19 8 2 1
...
192 = 2*96, 96 = 70 - 35 + 16 + 45, 45 = 35 - 16 + 7 + 19, etc. - _Philippe Deléham_, Mar 25 2014
Production matrix is:
2, 1
0, 0, 1
2, 1, 0, 1
2, 1, 1, 0, 1
2, 1, 1, 1, 0, 1
2, 1, 1, 1, 1, 0, 1
2, 1, 1, 1, 1, 1, 0, 1
2, 1, 1, 1, 1, 1, 1, 0, 1
... _Philippe Deléham_, Sep 15 2014

D. Baccherini, D. Merlini, R. Sprugnoli, Binary words excluding a pattern and proper Riordan arrays, Discrete Math. 307 (2007), no. 9-10, 1021--1037. MR2292531 (2008a:05003).

Cf. A180562.

Cf. T(n,0) = A025565(n+1), T(n+1,1) = A005773(n+1), T(n+2,2) = A005717(n+1), A225034 (Row sums). - Philippe Deléham, Mar 25 2014

T(0,0) = 1, T(n,0) = 2*T(n,1) for n>0, T(n,k) = T(n-1,k-1) - T(n-1,k) + T(n-1,k+1) + T(n,k+1) for k>0, T(n,k) = 0 if k<0 or if k>n. - Philippe Deléham, Mar 25 2014

More terms from Philippe Deléham, Mar 25 2014

A273020 a(n) = Sum_{k=0..n} C(n,k)((-1)^n(C(k,n-k)-C(k,n-k-1))+C(n-k,k+1)).

Original entry on oeis.org

1, 1, 3, 5, 19, 39, 141, 321, 1107, 2675, 8953, 22483, 73789, 190345, 616227, 1621413, 5196627, 13882947, 44152809, 119385663, 377379369, 1030434069, 3241135527, 8921880135, 27948336381, 77459553549, 241813226151, 674100041501, 2098240353907, 5878674505303, 18252025766941

Offset: 0

Peter Luschny, May 13 2016

nonn

A. Bostan and M. Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 (2008).

Cf. A005043, A005717, A082758, A273019.

seq(simplify(hypergeom([-n,1/2],[2],4) + n*hypergeom([-n/2+1,-n/2+1/2],[2],4)), n=0..30);

Table[ JacobiP[n, 1, -n-3/2, -7]/(n+1) + GegenbauerC[n-1,-n,-1/2], {n,0,30} ]

def A():
    a, b, c, d, n = 0, 1, 1, -1, 1
    yield 1
    while True:
        yield d + b*(1-(-1)^n)
        n += 1
        a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))
        c, d = d, (3*(n-1)*c-(2*n-1)*d)//n
A273020 = A()
print([next(A273020) for _ in range(31)])

a(n) = JacobiP(n, 1, -n-3/2, -7)/(n+1) + GegenbauerC(n-1, -n, -1/2), with a(0) = 1.
a(n) = hypergeom([-n,1/2], [2], 4) + n*hypergeom([-n/2+1,-n/2+1/2], [2], 4).
a(n) = (-1)^n*A005043(n) + A005717(n).
a(2*n) = A082758(n).
a(2*n+1) = A273019(n).

A292628 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of e.g.f. exp(kx)BesselI(1,2*x).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 2, 3, 0, 1, 4, 6, 0, 0, 1, 6, 15, 16, 10, 0, 1, 8, 30, 56, 45, 0, 0, 1, 10, 51, 144, 210, 126, 35, 0, 1, 12, 78, 304, 685, 792, 357, 0, 0, 1, 14, 111, 560, 1770, 3258, 3003, 1016, 126, 0, 1, 16, 150, 936, 3885, 10224, 15533, 11440, 2907, 0, 0, 1, 18, 195, 1456, 7570, 26550, 58947, 74280, 43758, 8350, 462

Offset: 0

Ilya Gutkovskiy, Sep 20 2017

A(n,k) is the k-th binomial transform of A138364 evaluated at n.

			E.g.f. of column k: A_k(x) = x/1! + 2*k*x^2/2! + 3*(k^2 + 1)*x^3/3! + 4*k*(k^2 + 3)*x^4/4! + 5*(k^4 + 6*k^2 + 2)*x^5/5! + ...
Square array begins:
   0,   0,    0,    0,     0,     0,  ...
   1,   1,    1,    1,     1,     1,  ...
   0,   2,    4,    6,     8,    10,  ...
   3,   6,   15,   30,    51,    78,  ...
   0,  16,   56,  144,   304,   560,  ...
  10,  45,  210,  685,  1770,  3885,  ...

N. J. A. Sloane, Transforms

Columns k=0..3 give A138364, A005717, A001791, A026376.
Main diagonal gives A292629.
Cf. A292627.

Table[Function[k, n! SeriesCoefficient[Exp[k x] BesselI[1, 2 x], {x, 0, n}]][j - n], {j, 0, 11}, {n, 0, j}] // Flatten

E.g.f. of column k: exp(k*x)*BesselI(1,2*x).

A383583 a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k-1,k) binomial(k,n-3*k).

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 2, 3, 0, 3, 12, 10, 4, 30, 60, 40, 60, 210, 286, 231, 560, 1267, 1428, 1722, 4208, 7182, 8064, 13275, 28080, 40656, 51754, 97020, 176088, 240251, 355872, 667810, 1081092, 1506648, 2475616, 4401696, 6693492, 9904752, 16950662, 28359201

Offset: 0

Seiichi Manyama, May 01 2025

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A005717, A383584.

Cf. A383571.

[&+[Binomial(n-2*k-1, k) * Binomial(k, n-3*k): k in [0..Floor(n div 3)]]: n in [0..45]]; // Vincenzo Librandi, May 03 2025

Table[Sum[Binomial[n-2*k-1,k]* Binomial[k,n-3*k],{k,0,Floor[n/3]}],{n,0,45}] (* Vincenzo Librandi, May 03 2025 *)

a(n) = sum(k=0, n\3, binomial(n-2*k-1, k)*binomial(k, n-3*k));

G.f.: (1/2) * ( 1 + 1/sqrt(1 - 4*x^4/(1-x^3)^2) ).

a(n) ~ phi^(n-1) / (2 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, May 01 2025

A383584 a(n) = Sum_{k=0..floor(n/4)} binomial(n-3k-1,k) binomial(k,n-4*k).

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 3, 0, 0, 3, 12, 10, 0, 4, 30, 60, 35, 5, 60, 210, 280, 132, 105, 560, 1260, 1267, 630, 1260, 4200, 6938, 5796, 4236, 11550, 27729, 36396, 28644, 34155, 90100, 168663, 188100, 163020, 276573, 631290, 973830, 995280, 1068222, 2111252, 4104100

Offset: 0

Seiichi Manyama, May 01 2025

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A005717, A383583.

Cf. A383572.

[&+[Binomial(n-3*k-1,k) * Binomial(k,n-4*k): k in [0..Floor(n div 4)]]: n in [0..45]]; // Vincenzo Librandi, May 02 2025

Table[Sum[Binomial[n-3*k-1,k]* Binomial[k,n-4*k],{k,0,Floor[n/4]}],{n,0,40}] (* Vincenzo Librandi, May 02 2025 *)

a(n) = sum(k=0, n\4, binomial(n-3*k-1, k)*binomial(k, n-4*k));

G.f.: (1/2) * ( 1 + 1/sqrt(1 - 4*x^5/(1-x^4)^2) ).

A102004 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and having k branches of even length (n>=0, 0<=k<=floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 6, 7, 1, 16, 20, 6, 40, 64, 26, 2, 109, 196, 108, 16, 297, 619, 414, 96, 4, 836, 1940, 1557, 484, 45, 2377, 6142, 5690, 2247, 331, 9, 6869, 19454, 20535, 9792, 2010, 126, 20042, 61893, 73123, 40997, 10820, 1116, 21, 59071, 197280, 258220

Offset: 0

Emeric Deutsch, Dec 25 2004

Row n has 1+floor(n/2) terms.
Row sums are the Catalan numbers (A000108).
T(2n,n) = A001006(n-1) for n>=1 (the Motzkin numbers).
T(2n+1,n) = A005717(n+1) for n>=0.

			T(3,0)=3 because we have: (i) tree with 3 edges hanging from the root, (ii) tree with one edge hanging from the root, at the end of which 2 edges are hanging and (iii) tree with a path of length 3 hanging from the root.
Triangle starts:
1;
1;
1,   1;
3,   2;
6,   7, 1;
16, 20, 6;

Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees and branch lengths, Discrete Math., 282, 2004, 89-94.
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214-222.

Cf. A000108, A001006, A005717, A102003.

G:=1/2/(t*z^2+z)*(-z^2+z+1+t*z^2-sqrt(-5*z^2-6*t*z^3-2*z+2*z^3-3*t^2*z^4-2*t*z^2+2*t*z^4+1+z^4)): Gserz:=simplify(series(G,z=0,16)): P[0]:=1: for n from 1 to 14 do P[n]:=sort(expand(coeff(Gserz,z^n))) od:for n from 0 to 14 do seq(coeff(t*P[n], t^k),k=1..1+floor(n/2)) od;

G.f. G = G(t,z) satisfies z(1+tz)G^2-(1+z-z^2+tz^2)G+1+z-z^2+tz^2=0.

A127905 Construct triangle in which n-th row is obtained by expanding (1+x+x^3)^n and take the next-to-central column.

Original entry on oeis.org

0, 1, 2, 3, 8, 25, 66, 168, 456, 1269, 3490, 9581, 26544, 73944, 206220, 576045, 1613264, 4527661, 12725946, 35818135, 100950440, 284869263, 804726934, 2275500998, 6440230392, 18242735800, 51714552656

Offset: 0

Paul Barry, Feb 05 2007

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A005717.

[0] cat [n*(&+[Binomial(n-1,3*k)*Binomial(3*k,k)/(2*k+1): k in [0..Floor((n-1)/3)]]): n in [1..30]]; // G. C. Greubel, Apr 30 2018

A127905 := proc(n)
    n*add(binomial(n-1,3*k)*binomial(3*k,k)/(2*k+1),k=0..floor((n-1)/3)) ;
end proc: # R. J. Mathar, Feb 23 2015

Table[n*Sum[Binomial[n-1,3*k]*Binomial[3*k,k]/(2*k+1), {k, 0, Floor[(n -1)/3]}], {n, 0, 50}] (* G. C. Greubel, Apr 30 2018 *)

a(n)=if(n<0, 0, polcoeff((1+x+x^3)^n, n-1));

a(n)=if(n<0, 0, n++; n*polcoeff(serreverse(x/(1+x+x^3)+x*O(x^n)), n))

a(n) = n*A071879(n-1).
a(n) = n*Sum_{k=0..floor((n-1)/3)} C(n-1,3*k)*C(3*k,k)/(2*k+1).
a(n) = Sum_{k=0..floor((n-1)/3)} (3*k+1)*C(n,3*k+1)*C(3*k,k)/(2k+1).
a(n) = Sum_{k=0..n-1} Sum_{j=0..floor(k/3)} C(k,3*j)*C(3*j+1,j).
Conjecture: 2*(2*n+1)*(n-1)^2*a(n) -2*n*(6*n^2-12*n+5)*a(n-1) +6*n*(n-1)*(2*n-3)*a(n-2) -31*n*(n-1)*(n-2)*a(n-3)=0. - R. J. Mathar, Feb 23 2015
a(n) ~ (1 + 3/2^(2/3))^(n + 1/2) / sqrt(12*Pi*n). - Vaclav Kotesovec, May 01 2018

Edited by Charles R Greathouse IV, Oct 28 2009

A135413 Number of at most 4-way branching ordered (i.e., plane) trees.

Original entry on oeis.org

1, 2, 6, 20, 70, 246, 875, 3144, 11385, 41470, 151778, 557712, 2056210, 7602700, 28180050, 104677280, 389571983, 1452293766, 5422187130, 20271296100, 75878518695, 284339792110, 1066585128810, 4004566131000, 15048213795600

Offset: 1

Andrey Bovykin (indiscernibles(AT)googlemail.com), Mar 01 2008

Obtained by Lagrange inversion of the generating function for at most k-way branching trees.

Solve z = T/(1+T+...T^k) when k = 4. I.e., the n-th term is the coefficient of x^(n-1) in the expansion of (1+x+x^2+x^3+x^4)^n.

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 250 terms from G. C. Greubel)

For k=2 this is A005717, for k=3 this is A005726.

A135413 := proc(n) local ogf,i ; ogf := 1 ; for i from 1 to n do ogf := taylor(ogf*(1+x+x^2+x^3+x^4),x=0,n) ; od: coeftayl(ogf,x=0,n-1) ; end: seq(A135413(n),n=1..30) ; # R. J. Mathar, Apr 21 2008

Join[{1}, Table[Coefficient[(1 + x + x^2 + x^3 + x^4)^n, x,(n - 1)], {n,2,25}]] (* G. C. Greubel, Oct 13 2016 *)

a(n):=sum((-1)^i*binomial(n,i)*binomial(2*n-5*i-2,n-5*i-1),i,0,(n-1)/5); /* Vladimir Kruchinin, Mar 28 2019 */

a(n) = polcoef((1+x+x^2+x^3+x^4)^n, n-1, x); \\ Michel Marcus, Mar 28 2019

a(n) = [ x^(n-1) ] (1+x+x^2+x^3+x^4)^n.

a(n) = Sum_{i=0..floor((n-1)/5)} (-1)^i * C(n,i) * C(2*n-5*i-2,n-5*i-1). - Vladimir Kruchinin, Mar 28 2019

More terms from R. J. Mathar, Apr 21 2008

A335349 a(n) counts anti-chains of size three in "0,1,2" Motzkin trees on n edges.

Original entry on oeis.org

2, 16, 98, 500, 2308, 9920, 40522, 159212, 606790, 2256544, 8224202, 29473012, 104124044, 363374560, 1254711038, 4292365876, 14564351510, 49059814576, 164186524940, 546276316120, 1807990549352, 5955265349696, 19530431537488, 63795464433440, 207623760855106, 673440401953856

Offset: 4

Petros Hadjicostas, Jun 03 2020

nonn

"0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers A001006.

A005717(n+1) is the total number of vertices (= anti-chains of size 1) in all "0,1,2" trees with n edges, while A178834(n) is the total number of anti-chains of size 2 in all "0,1,2" trees on n edges.

			Out of the A001006(4) = 9 Motzkin rooted trees, there are only two that have anti-chains of size 3 (i.e., 3-sets of pairwise incomparable nodes), and each one has only one such an anti-chain. Thus, a(4) = 1 + 1 = 2.
In the first Motzkin tree below with 4 edges, {E, C, D} is an anti-chain of size 3. In the second one, {G, I, K} is an anti-chain of size 3.
        A                          F
       / \                        / \
      /   \                      /   \
     B     E                    G     H
    / \                              / \
   /   \                            /   \
  C     D                          I     K

Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008; see Definition 42 (p. 30), Theorem 44 (p. 33), and Table 2.4 (p. 39).

Cf. A000108, A001006, A002426, A005717, A178834.

M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2);
T(z) = 1/sqrt(1 - 2*z - 3*z^2);
my(z='z+O('z^30)); Vec(2*z^4*T(z)^5*M(z)^3)

G.f. is A000108(r-1) * z^(2*r-2) * T(z)^(2*r-1) * M(z)^r = 2 * z^4 * T(z)^5 * M(z)^3 (with r = 3), where M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2)) / (2*z^2) is the g.f. of the Motzkin numbers A001006 and T(z) = 1 / sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers A002426.

A335355 a(n) counts anti-chains of size four in "0,1,2" Motzkin trees on n edges.

Original entry on oeis.org

5, 55, 420, 2600, 14175, 70665, 329800, 1462680, 6228945, 25661875, 102847560, 402706500, 1545715325, 5831511195, 21671504880, 79475234200, 288043346370, 1033030388790, 3669961024940, 12927078062500, 45182780785500, 156811313843420, 540722493900480, 1853503409060160

Offset: 6

Petros Hadjicostas, Jun 03 2020

nonn

"0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers A001006.
A005717(n+1) is the total number of vertices (= anti-chains of size 1) in all "0,1,2" trees with n edges, A178834(n) is the total number of anti-chains of size 2 in all "0,1,2" trees on n edges, and A335349(n) is the total number of anti-chains of size 3 in all "0,1,2" trees on n edges.
It would be interesting to examine whether there is an interpretation of this sequence and sequences A178834 and A335349 in terms of Motzkin paths. (Salaam (2008) worked with different families of rooted trees, but not with Motzkin paths.)

			For n=6, we list below all a(6) = 5 four-element anti-chains in Motzkin rooted trees with 6 edges:
              A               A                    A
             / \             / \                  / \
            /   \           /   \                /   \
           B     C         B     C              B     C
          / \   / \       / \                  / \
         /   \ /   \     /   \                /   \
        D    E F   G    D     E              D     E
        {D, E, F, G}         / \            / \
                            /   \          /   \
                           F     G        F     G
                        {C, D, F, G}         {C, E, F, G}
              A                                A
             / \                              / \
            /   \                            /   \
           B     C                          B     C
                / \                              / \
               /   \                            /   \
              D     E                          D     E
             / \                                    / \
            /   \                                  /   \
           F     G                                F     G
          {B, E, F, G}                        {B, D, F, G}

Martin Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics, 18(2) (1997), 195-210. [The author counts anti-chains for some kinds of rooted trees but not for Motzkin rooted trees.]
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008; see Definition 42 (p. 30), Theorem 44 (p. 33), and Table 2.4 (p. 39).

Cf. A000108, A001006, A002426, A005717, A178834, A335349.

default(seriesprecision, 50);
M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2);
T(z) = 1/sqrt(1 - 2*z - 3*z^2);
for(n=0, 30, print1(polcoef(5*z^6*T(z)^7*M(z)^4, n, z), ", "))

G.f.: A000108(r-1) * z^(2*r-2) * T(z)^(2*r-1) * M(z)^r = 5 * z^6 * T(z)^7 * M(z)^4 (with r = 4), where M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2)) / (2*z^2) is the g.f. of the Motzkin numbers A001006 and T(z) = 1 / sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers A002426.

cp's OEIS Frontend

A239101 Riordan array read by rows, corresponding to array in A180562.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A273020 a(n) = Sum_{k=0..n} C(n,k)*((-1)^n*(C(k,n-k)-C(k,n-k-1))+C(n-k,k+1)).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A292628 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of e.g.f. exp(k*x)*BesselI(1,2*x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A383583 a(n) = Sum_{k=0..floor(n/3)} binomial(n-2*k-1,k) * binomial(k,n-3*k).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A383584 a(n) = Sum_{k=0..floor(n/4)} binomial(n-3*k-1,k) * binomial(k,n-4*k).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A102004 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and having k branches of even length (n>=0, 0<=k<=floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A127905 Construct triangle in which n-th row is obtained by expanding (1+x+x^3)^n and take the next-to-central column.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A273020 a(n) = Sum_{k=0..n} C(n,k)((-1)^n(C(k,n-k)-C(k,n-k-1))+C(n-k,k+1)).

A292628 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of e.g.f. exp(kx)BesselI(1,2*x).

A383583 a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k-1,k) binomial(k,n-3*k).

A383584 a(n) = Sum_{k=0..floor(n/4)} binomial(n-3k-1,k) binomial(k,n-4*k).