A166300 -id:A166300 - cp's OEIS frontend

A175136 Triangle T(n,k) read by rows: number of LCO forests of size n with k leaves, 1 <= k <= n.

1, 1, 1, 2, 2, 1, 4, 6, 3, 1, 8, 17, 12, 4, 1, 16, 46, 44, 20, 5, 1, 32, 120, 150, 90, 30, 6, 1, 64, 304, 482, 370, 160, 42, 7, 1, 128, 752, 1476, 1412, 770, 259, 56, 8, 1, 256, 1824, 4344, 5068, 3402, 1428, 392, 72, 9, 1, 512, 4352, 12368, 17285, 14000, 7168, 2436

Offset: 1

R. J. Mathar, Feb 21 2010

From Johannes W. Meijer, May 06 2011: (Start)
The Row1, Kn11, Kn12, Kn13, Kn21, Kn22, Kn23, Kn3, Kn4 and Ca1 triangle sums link A175136 with several sequences, see the crossrefs. For the definitions of these triangle sums see A180662.
It is remarkable that the coefficients of the right hand columns of A175136, and subsequently those of triangle A175136, can be generated with the aid of the row coefficients of A091894. For the fourth, fifth and sixth right hand columns see A162148, A190048 and A190049. The a(n) formulas of the right hand columns lead to an explicit formula for the T(n,k), see the formulas and the second Maple program. (End)
Triangle T(n,k), 1 <= k <= n, read by rows, given by (0,1,1,0,1,1,0,1,1,0,1,1,0,1,...) DELTA (1,0,0,1,0,0,1,0,0,1,0,0,1,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 29 2011.
T(n,k) is the number of noncrossing partitions of n containing k runs, where a block forms a run if it consists of an interval of integers. For example, T(4,2)=6 counts 1/234, 12/34, 123/4, 1/24/3, 13/2/4, 14/2/3. - David Callan, Oct 14 2012

			Triangle starts
    1;
    1,    1;
    2,    2,    1;
    4,    6,    3,    1;
    8,   17,   12,    4,    1;
   16,   46,   44,   20,    5,    1;
   32,  120,  150,   90,   30,    6,    1;
   64,  304,  482,  370,  160,   42,    7,    1;
  128,  752, 1476, 1412,  770,  259,   56,    8,    1;
Triangle (0,1,1,0,1,1,0,...) DELTA (1,0,0,1,0,0,1,...) begins:
  1;
  0,  1;
  0,  1,  1;
  0,  2,  2,  1;
  0,  4,  6,  3,  1;
  0,  8, 17, 12,  4,  1; ... - _Philippe Deléham_, Oct 29 2011

David Callan, A bijection on Dyck paths and its cycle structure, El. J. Combinat. 14 (2007) # R28.
David Callan, On Ascent, Repetition and Descent Sequences, arXiv:1911.02209 [math.CO], 2019.
David Callan and Emeric Deutsch, The Run Transform, arXiv:1112.3639 [math.CO], 2011.
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Nonleft peaks in Dyck paths: a combinatorial approach, Discrete Math., 337 (2014), 97-105.

Triangle columns: A000012, A000027, A002378, A162148, A190048, A190049, A011782, A190050, A190051.
Triangle sums (see the comments): A000108 (Row1), A005043 (Related to Kn11, Kn12, Kn13 and Kn4), A007477 (Related to Kn21, Kn22, Kn23 and Kn3), A099251 (Kn4), A166300 (Ca1). - Johannes W. Meijer, May 06 2011
Cf. A000108 (row sums), A196182

lco := proc(siz,leav) (1-(1-4*x*(1-x)/(1-x*y))^(1/2))/2/x ; coeftayl(%,x=0,siz ) ; coeftayl(%,y=0,leav ) ; end proc: seq(seq(lco(n,k),k=1..n),n=1..9) ;
T := proc(n, k): add(A091894(n-k, k1)*binomial(n-k1-1, n-k), k1=0..floor((n-k)/2)) end: A091894 := proc(n, k): if n=0 and k=0 then 1 elif n=0 then 0 else 2^(n-2*k-1)* binomial(n-1, 2*k) * binomial(2*k, k)/(k+1) fi end: seq(seq(T(n, k), k=1..n), n=1..10); # Johannes W. Meijer, May 06 2011, revised Nov 23 2012

A091894[n_, k_] := 2^(n - 2*k - 1)*Binomial[n - 1, 2*k]*(Binomial[2*k, k]/(k + 1)); t[n_, k_] := Sum[A091894[n - k, k1]*Binomial [n - k1 - 1, n - k], {k1, 0, (n - k)/2}]; t[n_, n_] = 1; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten(* Jean-François Alcover, Jun 13 2013, after Johannes W. Meijer *)

G.f.: (1-(1-4*x*(1-x)/(1-x*y))^(1/2))/(2*x).

T(n,k) = Sum_{k1=0..floor((n-k)/2)} A091894(n-k, k1)*binomial(n-k1-1, n-k), 1 <= k <= n. - Johannes W. Meijer, May 06 2011

Variable names changed by Johannes W. Meijer, May 06 2011

A166299 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having k UUDD's starting at level 0.

Original entry on oeis.org

1, 0, 0, 1, 1, 0, 1, 0, 1, 2, 2, 0, 5, 2, 0, 1, 10, 4, 3, 0, 22, 11, 3, 0, 1, 50, 22, 6, 4, 0, 113, 49, 18, 4, 0, 1, 260, 114, 36, 8, 5, 0, 605, 260, 81, 26, 5, 0, 1, 1418, 604, 193, 52, 10, 6, 0, 3350, 1419, 444, 118, 35, 6, 0, 1, 7967, 3350, 1041, 288, 70, 12, 7, 0, 19055, 7966

Offset: 0

Emeric Deutsch, Nov 07 2009

Sum of entries in row n is the secondary structure number A004148(n-1) (n>=2).
Number of entries in row n is 1 + floor(n/2).
T(n,0)=A166300(n).
Sum(k*T(n,k), k>=0)=A075125(n+2).

			T(7,2)=3 because we have (UUDD)(UUDD)UUUDDD, (UUDD)UUUDDD(UUDD), and UUUDDD(UUDD)(UUDD) (the UUDD's starting at level 0 are shown between parentheses).
Triangle starts:
1;
0;
0,1;
1,0;
1,0,1;
2,2,0;
5,2,0,1;
10,4,3,0;

Cf. A004148, A166300, A075125

G := 2/(1+z+z^2+sqrt((1+z+z^2)*(1-3*z+z^2))-2*t*z^2): Gser := simplify(series(G, z = 0, 18)): for n from 0 to 16 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 16 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

G.f.=G(t,z)=1/(1 + z - zg - tz^2), where g=g(z) satisfies g=1 + zg(g - 1 + z).
G.f. of column k is z^{2k}/(1 + z - zg)^{k+1} (k>=0).
G(t,z)=2/[1+z+z^2+sqrt((1+z+z^2)(1-3z+z^2)-2tz^2)].

A247299 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having a total of k h- and H-steps at level 0.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 2, 1, 3, 1, 2, 4, 3, 3, 4, 1, 5, 6, 9, 5, 6, 5, 1, 10, 15, 15, 16, 9, 10, 6, 1, 22, 33, 33, 32, 26, 16, 15, 7, 1, 50, 71, 78, 66, 60, 41, 27, 21, 8, 1, 113, 163, 171, 158, 125, 103, 64, 43, 28, 9, 1, 260, 374, 391, 360, 295, 225, 167, 99, 65, 36, 10, 1

Offset: 0

Emeric Deutsch, Sep 17 2014

B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2, u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps.
Row n contains n+1 entries.
Sum of entries in row n is A004148(n+1) (the 2ndary structure numbers).
T(n,0) = A166300(n).
Sum(k*T(n,k), k=0..n) = A247300(n)

			Row 3 is 1,0,2,1 because B(3) = {ud, hH, Hh, hhh}.
Triangle starts:
1;
0,1;
0,1,1;
1,0,2,1;
1,2,1,3,1;
2,4,3,3,4,1;

Alois P. Heinz, Rows n = 0..140, flattened
M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Cf. A004148, A166300, A247300,

eqg := g = 1+z*g+z^2*g+z^3*g^2: g := RootOf(eqg, g): G := 1/(1-t*z-t*z^2-z^3*g): Gser := simplify(series(G, z = 0, 16)): for n from 0 to 13 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 13 do seq(coeff(P[n], t, k), k = 0 .. n) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y) option remember; `if`(y<0 or y>n or n<0, 0,
      `if`(n=0, 1, expand(`if`(y=0, x, 1)*(b(n-1, y)+
      b(n-2, y)) +b(n-2, y+1) +b(n-1, y-1))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..14);  # Alois P. Heinz, Sep 17 2014

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

G.f. G = 1/(1 - t*z - t*z^2 - z^3*g), where g is given by g = 1 + z*g + z^2*g + z^3*g^2.

A188444 Expansion of (1+x)(1+x+x^2)(1-x+x^2-4*x+x^4-x^5+x^6)/(1+x^4)^3.

Original entry on oeis.org

1, 1, 1, -3, -9, -9, -6, 10, 25, 25, 15, -21, -49, -49, -28, 36, 81, 81, 45, -55, -121, -121, -66, 78, 169, 169, 91, -105, -225, -225, -120, 136, 289, 289, 153, -171, -361, -361, -190, 210, 441, 441, 231, -253, -529, -529, -276, 300, 625, 625, 325

Offset: 0

Paul Barry, Mar 31 2011

a(n+1) is the Hankel transform of A166300(n+3) (diagonal sums of the triangle A100754).

Index entries for linear recurrences with constant coefficients, signature (0,0,0,-3,0,0,0,-3,0,0,0,-1).

G.f.: (1+x+x^2-3*x^3-6*x^4-6*x^5-3*x^6+x^7+x^8+x^9)/(1+x^4)^3.

a(n) = -3*a(n-4) - 3*a(n-8) - a(n-12). - Wesley Ivan Hurt, Mar 17 2023

A350114 Number of Deutsch paths with peaks at odd height.

Original entry on oeis.org

1, 0, 1, 0, 2, 2, 6, 11, 26, 56, 129, 294, 684, 1599, 3774, 8961, 21411, 51421, 124081, 300667, 731337, 1785010, 4370431, 10731270, 26419202, 65198847, 161262046, 399692001, 992559011, 2469265633, 6153306125, 15357906136, 38388056063, 96086525311, 240821963528

Offset: 0

David Callan, Dec 14 2021

a(n) is the number of closed Deutsch paths of n steps with all peaks at odd height. A Deutsch path is a lattice path of up-steps (1,1) and down-steps (1,-j), j>=1, starting at the origin that never goes below the x-axis, and it is closed if it ends on the x-axis.

A166300 counts closed Deutsch paths with all peaks at even height.

			a(5) = 2  counts UUU12, UUU21, where  U denotes an up-step and a down-step is denoted by its length, and a(6) = 6 counts UUUUU5, UUU1U3, UUU111, UUU3U1, U1UUU3, U1U1U1.

Helmut Prodinger, Deutsch paths and their enumeration, preprint, arXiv:2003.01918 [math.CO], 2020.

Cf. A166300.

CoefficientList[Series[(1 + x + x^2 - Sqrt[(1 - 3 x + x^2) (1 + x + x^2)])/(2 x + 2 x^2), {x, 0, 20}], x]

With F = 1 + x^2 + 2*x^4 + 2*x^5+ ... the g.f. for Deutsch paths with all peaks at odd height and G = 1 + x^3 + x^4 + 2*x^5+ ... the g.f. for Deutsch paths with all peaks at even height, a count based on the decomposition of paths according to the size j of the first down-step (1,-j) that returns the path to ground level yields the pair of simultaneous equations
   F = 1 + (x^2*F*G + x^3*(F-1)*F*G)/(1 - x^2*F*G),
   G = 1 + (x^2*(F-1)*G  + x^3*F*G^2)/(1 - x^2*F*G).
G.f.:  (1 + x + x^2 - sqrt[(1 - 3*x + x^2)*(1 + x + x^2)])/(2*x*(1 + x)).
D-finite with recurrence (n+1)*a(n) +(-n+2)*a(n-1) +3*(-n+1)*a(n-2) +3*(-n+3)*a(n-3) +(-n+2)*a(n-4) +(n-5)*a(n-5)=0. - R. J. Mathar, Mar 06 2022

cp's OEIS Frontend

A175136 Triangle T(n,k) read by rows: number of LCO forests of size n with k leaves, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A166299 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having k UUDD's starting at level 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A247299 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having a total of k h- and H-steps at level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A188444 Expansion of (1+x)*(1+x+x^2)*(1-x+x^2-4*x+x^4-x^5+x^6)/(1+x^4)^3.

Views

Author

Keywords

Comments

Links

Formula

A350114 Number of Deutsch paths with peaks at odd height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A188444 Expansion of (1+x)(1+x+x^2)(1-x+x^2-4*x+x^4-x^5+x^6)/(1+x^4)^3.