A102407 -id:A102407 - cp's OEIS frontend

A102405 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n having k ascents of length 1 that start at an odd level.

1, 1, 2, 4, 1, 10, 3, 1, 26, 12, 3, 1, 72, 41, 15, 3, 1, 206, 143, 58, 18, 3, 1, 606, 492, 231, 76, 21, 3, 1, 1820, 1693, 891, 335, 95, 24, 3, 1, 5558, 5823, 3403, 1411, 455, 115, 27, 3, 1, 17206, 20040, 12870, 5848, 2061, 591, 136, 30, 3, 1, 53872, 69033, 48318, 23858, 9143, 2850, 743, 158, 33, 3, 1

Offset: 0

Emeric Deutsch, Jan 06 2005

T(n,k) is number of Łukasiewicz paths of length n having k level steps at an odd level. 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)=1 because we have only UHD with exactly one level step at an odd level; here U=(1,1), H=(1,0) and D=(1,-1). Row n has n-1 terms (n>=2). Row sums are the Catalan numbers (A000108). Column 0 yields A102407.

T(n,k) is the number of Dyck paths of semilength n with k DUDU's. - I. Tasoulas (jtas(AT)unipi.gr), Feb 19 2006

			T(4,1) = 3 because we have UDUUD(U)DD, UUD(U)DDUD and UUUDD(U)DD, where U=(1,1), D=(1,-1) and the ascents of length 1 that start at an odd level are shown between parentheses.
Triangle starts:
00 :    1;
01 :    1;
02 :    2;
03 :    4,    1;
04 :   10,    3,    1;
05 :   26,   12,    3,    1;
06 :   72,   41,   15,    3,   1;
07 :  206,  143,   58,   18,   3,   1;
08 :  606,  492,  231,   76,  21,   3,  1;
09 : 1820, 1693,  891,  335,  95,  24,  3, 1;
10 : 5558, 5823, 3403, 1411, 455, 115, 27, 3, 1;

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.
Index entries for sequences related to Łukasiewicz

Cf. A000108, A094507 (the same for UDUD), A102404, A102407, A263173.

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, 2, 4, 2][t])
      +b(x-1, y+1, [1, 3, 1, 3][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 02 2014

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

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

A384613 Number of rooted ordered trees with n non-root nodes such that all leaf nodes can be k different colors where k is the degree of their parent node.

Original entry on oeis.org

1, 1, 5, 36, 340, 4019, 57696, 982146, 19419042, 438068191, 11106513798, 312555754796, 9663786464541, 325515760762637, 11861723942987878, 464834173383876612, 19490387161582849600, 870582781070074780946, 41266849779858887379029, 2068827708558025551348644

Offset: 0

John Tyler Rascoe, Jun 04 2025

nonn

			a(2) = 5 counts:
   o      o        o        o        o
   |     / \      / \      / \      / \
   o   (1) (1)  (1) (2)  (2) (1)  (2) (2)
   |
  (1)

Cf. A000108, A002212, A007318, A102407, A258173.

G(k,N) = if(k>N, 1, 1+ sum(i=1,N, (x*(G(k+1,N-i+1)+i-1))^i))
G_x(N) = {my(x='x+O('x^N)); Vec(G(1,N)+ O('x^(N+1)))}

G.f.: G(x) satisfies G(x) = Sum_{i>=0} (x*(G(x) + i - 1))^i.

A102406 Number of Dyck paths of semilength n having no ascents of length 1 that start at an even level.

Original entry on oeis.org

1, 0, 1, 2, 5, 14, 39, 114, 339, 1028, 3163, 9852, 31005, 98436, 314901, 1014070, 3284657, 10694314, 34979667, 114887846, 378750951, 1252865288, 4157150327, 13832926200, 46148704121, 154327715592, 517236429545, 1737102081962, 5845077156189, 19702791805126

Offset: 0

Emeric Deutsch, Jan 06 2005

nonn

Number of Łukasiewicz paths of length n having no level steps at an even level. 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: a(3)=2 because we have UHD and U(2)DD, where U=(1,1), H=(1,0), D=(1,-1) and U(2)=(1,2). a(n)=A102404(n,0).

Number of Dyck n-paths with no descent of length 1 following an ascent of length 1. [David Scambler, May 11 2012]

			a(3) = 2 because we have UUDUDD and UUUDDD, having no ascents of length 1 that start at an even level.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for sequences related to Łukasiewicz

Cf. A102404, A102407.

R:=PowerSeriesRing(Rationals(), 30);
Coefficients(R!( (1+x+x^2 -Sqrt(1-2*x-5*x^2-2*x^3+x^4))/(2*x*(1+x)^2) )); // G. C. Greubel, Oct 31 2024

G:=(1+z+z^2-sqrt(1-2*z-5*z^2-2*z^3+z^4))/2/z/(1+z)^2: Gser:=series(G,z=0,32): 1,seq(coeff(Gser,z^n),n=1..29);

CoefficientList[Series[(1+x+x^2 -Sqrt[1-2*x-5*x^2-2*x^3+x^4])/(2*x*(1+x)^2), {x,0,40}], x] (* G. C. Greubel, Oct 31 2024 *)

def A102406_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x+x^2 -sqrt(1-2*x-5*x^2-2*x^3+x^4))/(2*x*(1+x)^2) ).list()
A102406_list(30) # G. C. Greubel, Oct 31 2024

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

(n+1)*a(n) -(n-3)*a(n-1) -(7*n-9)*a(n-2) -(7*n-12)*a(n-3) -n*a(n-4) +(n-4)*a(n-5) = 0. - R. J. Mathar, Jan 04 2017

A356832 Number of permutations p of [n] such that at most one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i < n and n = 0 or p(n) < 3.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 72, 206, 608, 1834, 5636, 17578, 55516, 177192, 570700, 1852572, 6055080, 19910730, 65823752, 218654100, 729459552, 2443051214, 8210993364, 27685671844, 93625082140, 317470233150, 1079183930828, 3676951654520, 12554734605496, 42952566314236

Offset: 0

Alois P. Heinz, Aug 30 2022

nonn

			a(0) = 1: (), the empty permutation.
a(1) = 1: 1.
a(2) = 2: 12, 21.
a(3) = 4: 132, 231, 312, 321.
a(4) = 10: 1342, 1432, 2431, 3142, 3412, 3421, 4132, 4231, 4312, 4321.
a(5) = 26: 13542, 14532, 15342, 15432, 24531, 25431, 31542, 35142, 35412, 35421, 41532, 42531, 45132, 45231, 45312, 45321, 51342, 51432, 52431, 53142, 53412, 53421, 54132, 54231, 54312, 54321.

Alois P. Heinz, Table of n, a(n) for n = 0..1802

Column k=0 and also main diagonal of A356692.

Cf. A000142, A102407, A216837, A291683.

b:= proc(u, o) option remember; `if`(u+o=0, 1,
      add(b(sort([o-j, u+j-1])[]), j=1..min(2, o))+
      add(b(sort([u-j, o+j-1])[]), j=1..min(2, u)))
    end:
a:= n-> b(0, n):
seq(a(n), n=0..30);
# second Maple program:
b:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, add(b(n-1, j), j=k-2..k+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..30);

a(n) = A356692(n,0) = A356692(n,n).
a(n) = 1 + A291683(n).
a(n) >= A102407(n) with equality only for n <= 7.

A337991 Triangle read by rows: T(n,m) = Sum_{i=1..n} C(n,i-m)C(n+m-i,i-1)C(n+m-i,m)/n, with T(0,0)=1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 5, 4, 1, 4, 13, 15, 7, 1, 9, 35, 52, 36, 11, 1, 21, 96, 175, 160, 75, 16, 1, 51, 267, 576, 655, 415, 141, 22, 1, 127, 750, 1869, 2541, 2030, 952, 245, 29, 1, 323, 2123, 6000, 9492, 9156, 5488, 1988, 400, 37, 1, 835, 6046, 19107, 34476, 38976, 28476, 13356, 3852, 621, 46, 1

Offset: 0

Vladimir Kruchinin, Oct 06 2020

			Triangle begins as:
   1;
   1,   1;
   1,   2,   1;
   2,   5,   4,   1;
   4,  13,  15,   7,   1;
   9,  35,  52,  36,  11,   1;
  21,  96, 175, 160,  75,  16,  1;
  51, 267, 576, 655, 415, 141, 22,  1;
  ...

G. C. Greubel, Rows n = 0..100 of the triangle, flattened

Cf. A001006, A005773, A086246, A132894.
Diagonals include: A000124, A006008.
Sums include: A000007 (signed row), A019590 (signed diagonal), A025227 (row), A102407 (diagonal).

B:=Binomial;
A337991:= func< n,k | n eq 0 select 1 else (1/n)*(&+[B(n, j-k)*B(n+k-j, j-1)*B(n+k-j, k): j in [1..n]]) >;
[A337991(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 31 2024

T[0, 0] = 1; T[n_, m_] := Sum[Binomial[n, i - m] * Binomial[n + m - i, i - 1] * Binomial[n + m - i, m]/n, {i, 1, n}]; Table[T[n, m], {n, 0, 10}, {m, 0, n}] // Flatten (* Amiram Eldar, Oct 06 2020 *)

T(n,m):=if m=n then 1 else if n=0 then 0 else sum(binomial(n,i-m)*binomial(n+m-i,i-1)*binomial(n+m-i,m),i,1,n)/n;

def A337991(n,k):
    b=binomial
    if n==0: return 1
    else: return (1/n)*sum(b(n, j-k)*b(n+k-j, j-1)*b(n+k-j, k) for j in range(1,n+1))
# SageMath
flatten([[A337991(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Oct 31 2024

G.f.: ( 1 - x*(y-1)- sqrt(x^2*(y^2-2*y-3) - 2*x*(y+1) + 1) )/(2*x).
From G. C. Greubel, Oct 31 2024: (Start)
T(n, k) = binomial(n, 1-k)*binomial(n+k-1, k)*Hypergeometric3F2([1-n, (1 -n -k)/2, (2-n-k)/2], [2-k, 1-n-k], 4), with T(0, 0) = 1.
T(n, 0) = A086246(n+1).
T(n, n-1) = A000124(n-1), n >= 1.
T(n, n-2) = A006008(n-1), n >= 2.
T(n, n-3) = (1/72)*(n^4 -6*n^3 +47*n^2 -114*n +144)*binomial(n-1,2), n >= 3.
T(n, n-4) = (1/480)*(n-2)*(n^4 -8*n^3 +99*n^2 -332*n +960)*binomial(n-1,3), n >= 4.
Sum_{k=0..n} T(n, k) = A025227(n+1).
Sum_{k=0..n} (-1)^k*T(n, k) = A000007(n).
Sum_{k=0..floor(n/2)} T(n-k, k) = A102407(n).
Sum_{k=0..floor(n/2)} (-1)^k*T(n-k, k) = A019590(n+1). (End)

cp's OEIS Frontend

A102405 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n having k ascents of length 1 that start at an odd level.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A384613 Number of rooted ordered trees with n non-root nodes such that all leaf nodes can be k different colors where k is the degree of their parent node.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A102406 Number of Dyck paths of semilength n having no ascents of length 1 that start at an even level.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A356832 Number of permutations p of [n] such that at most one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i < n and n = 0 or p(n) < 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A337991 Triangle read by rows: T(n,m) = Sum_{i=1..n} C(n,i-m)*C(n+m-i,i-1)*C(n+m-i,m)/n, with T(0,0)=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

Python

Formula

A337991 Triangle read by rows: T(n,m) = Sum_{i=1..n} C(n,i-m)C(n+m-i,i-1)C(n+m-i,m)/n, with T(0,0)=1.