A055219 -id:A055219 - cp's OEIS frontend

A091958 Triangle read by rows: T(n,k)=number of ordered trees with n edges and k branch nodes at odd height.

1, 1, 2, 4, 1, 9, 5, 21, 21, 51, 78, 3, 127, 274, 28, 323, 927, 180, 835, 3061, 954, 12, 2188, 9933, 4510, 165, 5798, 31824, 19734, 1430, 15511, 100972, 81684, 9790, 55, 41835, 317942, 324246, 57876, 1001, 113634, 995088, 1245762, 309036, 10920

Offset: 0

Emeric Deutsch, Mar 13 2004

T(3n,n) = binomial(3n,n)/(2n+1) = A001764(n); T(n,0) = A001006(n) (the Motzkin numbers); T(n,1) = A055219(n-3) (n>=3; most probably); Row sums are the Catalan numbers (A000108).
T(n,k) = number of ordered trees on n edges with k vertices of outdegree at least 3; T(n,k) = number of ordered trees on n edges with k vertices V such that V's rightmost descendant leaf is at distance exactly 3 from V. - David Callan, Oct 24 2004
T(n,k) is the number of Dyck n-paths containing k UUUDs. For example, T(6,2) = 3 because UUUDUUUDDDDD, UUUDDUUUDDDD, UUUDDDUUUDDD each contains 2 UUUDs. - David Callan, Nov 04 2004

			T(3,1) = 1 because the only tree having 3 edges and 1 branch node at an odd level is the tree having the shape of the letter Y.
Triangle begins:
1;
1;
2;
4,       1;
9,       5;
21,     21;
51,     78,    3;
127,   274,   28;
323,   927,  180;
835,  3061,  954,  12;
2188, 9933, 4510, 165;

Alois P. Heinz, Rows n = 0..250, flattened
E. Deutsch, A bijection on ordered trees and its consequences, J. Comb. Theory, A, 90, 210-215, 2000.
A. Kuznetsov, I. Pak, A. Postnikov, Trees associated with the Motzkin numbers, J. Comb. Theory, A, 76, 145-147, 1996.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A001764, A001006, A055219, A243752.

Topmost entries in each column form A001764=( binomial(3n, n)/(2n+1) )A025174=(%20binomial(3n+2,%20n)%20)">(n>=0), next to topmost entries form A025174=( binomial(3n+2, n) )(n>=0), next lower entries are given by ( (n+2)binomial(3n+4, n) )_(n>=0).

T := (n,k)->binomial((n+1),k)*sum((-1)^j*binomial(n+1-k,j)*binomial(2*n-3*k-3*j,n),j=0..floor(n/3)-k)/(n+1): seq(seq(T(n,k),k=0..floor(n/3)),n=0..18);
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, [2, 3, 4, 4][t])
      +b(x-1, y-1, [1, 1, 1, 1][t])*`if`(t=4, z, 1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Jun 10 2014

Clear[a]; a[n_, k_]/;k>n/3 || k<0 := 0; a[n_, 0]/;0<=n<=1 := 1; a[n_, 0]/;n>=2 := a[n, 0] = ((2*n + 1)*a[n-1, 0] + 3*(n - 1)*a[n-2, 0])/(n + 2); a[n_, k_]/;1<=k<=n/3 && n>=2 := a[n, k] = ( (12 - 9*k + 3*n)*a[n-2, k-2] - (12 - 18*k + 3*n)*a[ n-2, k-1] - 9*k*a[ n-2, k] + (4 - 6*k + 4*n)*a[n-1, k-1] + 6*k*a[n-1, k] - (2 - k + n)*a[n, k-1] )/k; Table[a[n, k], {n, 0, 16}, {k, 0, n/3}] (Callan)
T[n_, k_] := (2*n-3*k)!*HypergeometricPFQ[{k-n-1, k-n/3, 1/3+k-n/3, 2/3+k-n/3}, {k-2*n/3, 1/3+k-2*n/3, 2/3+k-2*n/3}, 1]/(k!*(n-k+1)!*(n-3*k)!); Table[T[n, k], {n, 0, 15}, {k, 0, n/3}] // Flatten (* Jean-François Alcover, Mar 31 2015 *)

T(n,k) = binomial((n+1), k)*sum((-1)^j*binomial(n+1-k,j)*binomial(2n-3k-3j, n), j=0..floor(n/3)-k)/(n+1). G.f.: G=G(t,z) satisfies (t-1)z^3 G^3 + zG^2 - G + 1 = 0.

A108863 Number of Dyck paths containing exactly one UUUD.

Original entry on oeis.org

0, 0, 0, 1, 5, 21, 78, 274, 927, 3061, 9933, 31824, 100972, 317942, 995088, 3099105, 9612735, 29715525, 91595391, 281643480, 864189486, 2646805668, 8093543439, 24713953515, 75370741506, 229604257846, 698754428388, 2124616182139

Offset: 0

David Callan, Jul 25 2005

nonn

a(n) = number of Dyck n-paths containing exactly one UUUD.

Conjecture: this is the Motzkin transform of the sequence of three zeros followed by A001651. - R. J. Mathar, Dec 11 2008

			a(4) = 5 because UUUUDDDD, UUUDUDDD, UUUDDUDD, UDUUUDDD, UUUDDDUD
each contain one UUUD.

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

Cf. same as A055219 except for offset and is column k=1 of A091958. Dyck paths containing no UUUD are counted by the Motzkin numbers (A001006).

Column k=8 of A243827.

CoefficientList[Series[(x-1+(1-2*x)*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2))/(x*(1-3*x)*(1+x*(1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2))),{x,0,20}],x] (* Vaclav Kotesovec, Mar 22 2014 *)

G.f. (x-1+(1-2*x)M)/(x(1-3*x)(1+x*M)) = Sum_{n>=0}a(n)x^n where M = (1-x-(1-2*x-3*x^2)^(1/2))/(2*x^2) is the gf for Motzkin numbers (A001006); satisfies z^3 = (1 + z)(1 - 3z)( (1 - 3z + z^2)G + z^2(1 - 3z)G^2 ).
Recurrence: (n-3)*(n+2)*a(n) = (n+1)*(5*n-14)*a(n-1) - 3*(n-2)*(n-1)*a(n-2) - 9*(n-2)*(n-1)*a(n-3). - Vaclav Kotesovec, Mar 22 2014
a(n) ~ 3^n/2 * (1-5*sqrt(3)/(2*sqrt(Pi*n))). - Vaclav Kotesovec, Mar 22 2014

cp's OEIS Frontend

A091958 Triangle read by rows: T(n,k)=number of ordered trees with n edges and k branch nodes at odd height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula