A135339 -id:A135339 - cp's OEIS frontend

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

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

A135333 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k DUDU's starting at level 1.

Original entry on oeis.org

1, 1, 2, 4, 1, 11, 2, 1, 32, 7, 2, 1, 99, 22, 8, 2, 1, 318, 73, 26, 9, 2, 1, 1051, 246, 90, 30, 10, 2, 1, 3550, 844, 312, 108, 34, 11, 2, 1, 12200, 2936, 1096, 384, 127, 38, 12, 2, 1, 42520, 10334, 3886, 1379, 462, 147, 42, 13, 2, 1, 149930, 36736, 13897, 4978, 1694

Offset: 0

N. J. A. Sloane, Dec 07 2007

Each of rows 0, 1 and 2 contains one entry. Row n contains n-1 entries (n >= 2). Row sums are the Catalan numbers (A000108). Column 0 yields A135339. - Emeric Deutsch, Dec 13 2007

			Triangle begins:
1
1
2
4 1
11 2 1
32 7 2 1
99 22 8 2 1
318 73 26 9 2 1
1051 246 90 30 10 2 1
...
T(4,1)=2 because we have U(DUDU)UDD and UUD(DUDU)D; T(4,2)=1 because we have U(DU[DU)DU]D (the DUDU's starting at level 1 are shown between parentheses).

Alois P. Heinz, Rows n = 0..150, flattened
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A000108, A135339.

G:=1+z*C+z^2*C^3/(1+(1-t)*z*C): C:=((1-sqrt(1-4*z))*1/2)/z: Gser:=simplify(series(G,z=0,17)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) end do: 1; 1; for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 13 2007
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
      `if`(y0, b(x-1, y-1, `if`(y=1, [2, 1, 4, 1][t], 1)), 0)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..14);  # Alois P. Heinz, Sep 28 2015

b[x_, y_, t_] := b[x, y, t] = Expand[If[x == 0, 1, If[y < x, b[x - 1, y + 1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1], 0] + If[y > 0, b[x - 1, y - 1, If[y == 1, {2, 1, 4, 1}[[t]], 1]], 0]]]; T[n_] := Function [p, Table[ Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Feb 14 2016, after Alois P. Heinz *)

G.f.: 1+zC+z^2*C^3/[1+(1-t)zC], where C=[1-sqrt(1-4z)]/(2z) is the g.f. of the Catalan numbers (A000108). T(n,k) = d(0,k)*c(n-1)+Sum[(-1)^(j-k)*(j+3)binomial(j,k)binomial(2n-j-2,n),j=k..n-2]/(n+1), where c(m) = binomial(2m,m)/(m+1) = A000108(m) is a Catalan number and d(0,k) is the Kronecker symbol. - Emeric Deutsch, Dec 13 2007

Edited and extended by Emeric Deutsch, Dec 13 2007

A350584 Triangle read by rows, T(n, k) = [x^k] ((2x^3 - 3x^2 - x + 1)/(1 - x)^(n + 2)), for n >= 1 and 0 <= k < n.

Original entry on oeis.org

1, 1, 3, 1, 4, 7, 1, 5, 12, 19, 1, 6, 18, 37, 56, 1, 7, 25, 62, 118, 174, 1, 8, 33, 95, 213, 387, 561, 1, 9, 42, 137, 350, 737, 1298, 1859, 1, 10, 52, 189, 539, 1276, 2574, 4433, 6292, 1, 11, 63, 252, 791, 2067, 4641, 9074, 15366, 21658

Offset: 1

Peter Luschny, Mar 27 2022

			Triangle starts:
[1] [1]
[2] [1,  3]
[3] [1,  4,  7]
[4] [1,  5, 12,  19]
[5] [1,  6, 18,  37,  56]
[6] [1,  7, 25,  62, 118,  174]
[7] [1,  8, 33,  95, 213,  387,  561]
[8] [1,  9, 42, 137, 350,  737, 1298, 1859]
[9] [1, 10, 52, 189, 539, 1276, 2574, 4433, 6292]

A280891 (row sums), A135339 (alternating row sums), A005807 or A071716 (main diagonal).

# Compare the analogue algorithm for the Bell triangle in A046937.
A350584Triangle := proc(len) local A, P, T, n; A := [2]; P := [1]; T := [[1]];
for n from 1 to len-1 do P := ListTools:-PartialSums([op(P), A[-1]]);
A := P; T := [op(T), P] od; T end:
A350584Triangle(10): ListTools:-Flatten(%);
# Alternative:
ogf := n -> (2*x^3 - 3*x^2 - x + 1)/(1 - x)^(n + 2):
ser := n -> series(ogf(n), x, n):
row := n -> seq(coeff(ser(n), x, k), k = 0..n-1):
seq(row(n), n = 1..10);

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Python

Sage

Formula

A135333 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k DUDU's starting at level 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A350584 Triangle read by rows, T(n, k) = [x^k] ((2*x^3 - 3*x^2 - x + 1)/(1 - x)^(n + 2)), for n >= 1 and 0 <= k < n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A169589 A number triangle with repeated columns of triangle in A039599.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A350584 Triangle read by rows, T(n, k) = [x^k] ((2x^3 - 3x^2 - x + 1)/(1 - x)^(n + 2)), for n >= 1 and 0 <= k < n.