A203717 -id:A203717 - cp's OEIS frontend

A291680 Number T(n,k) of permutations p of [n] such that in 0p the largest up-jump equals k and no down-jump is larger than 2; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 9, 8, 4, 0, 1, 25, 36, 20, 10, 0, 1, 71, 156, 108, 58, 26, 0, 1, 205, 666, 586, 340, 170, 74, 0, 1, 607, 2860, 3098, 2014, 1078, 528, 218, 0, 1, 1833, 12336, 16230, 11888, 6772, 3550, 1672, 672, 0, 1, 5635, 53518, 85150, 69274, 42366, 23284, 11840, 5454, 2126

Offset: 0

Alois P. Heinz, Aug 29 2017

An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here.

			T(4,1) = 1: 1234.
T(4,2) = 9: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2413, 2431.
T(4,3) = 8: 1423, 1432, 3124, 3142, 3214, 3241, 3412, 3421.
T(4,4) = 4: 4213, 4231, 4312, 4321.
T(5,5) = 10: 53124, 53142, 53214, 53241, 53412, 53421, 54213, 54231, 54312, 54321.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   3,    2;
  0, 1,   9,    8,    4;
  0, 1,  25,   36,   20,   10;
  0, 1,  71,  156,  108,   58,   26;
  0, 1, 205,  666,  586,  340,  170,  74;
  0, 1, 607, 2860, 3098, 2014, 1078, 528, 218;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A057427, A291683, A321110, A321111, A321112, A321113, A321114, A321115, A321116, A321117.
T(2n,n) gives A320290.
Cf. A203717, A206464, A264868.

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(2, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
T:= (n, k)-> b(0, n, k)-`if`(k=0, 0, b(0, n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

b[u_, o_, k_] := b[u, o, k] = If[u+o == 0, 1, Sum[b[u-j, o+j-1, k], {j, 1, Min[2, u]}] + Sum[b[u+j-1, o-j, k], {j, 1, Min[k, o]}]];
T[n_, k_] := b[0, n, k] - If[k == 0, 0, b[0, n, k-1]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 29 2019, after Alois P. Heinz *)

from sympy.core.cache import cacheit
@cacheit
def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(2, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])
def T(n, k): return b(0, n, k) - (0 if k==0 else b(0, n, k - 1))
for n in range(13): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Aug 30 2017

T(n,n) = A206464(n-1) for n>0.

Sum_{k=0..n} T(n,k) = A264868(n+1).

A288942 Number A(n,k) of ordered rooted trees with n non-root nodes and all outdegrees <= k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 9, 1, 0, 1, 1, 2, 5, 13, 21, 1, 0, 1, 1, 2, 5, 14, 36, 51, 1, 0, 1, 1, 2, 5, 14, 41, 104, 127, 1, 0, 1, 1, 2, 5, 14, 42, 125, 309, 323, 1, 0, 1, 1, 2, 5, 14, 42, 131, 393, 939, 835, 1, 0

Offset: 0

Alois P. Heinz, Sep 01 2017

Also the number of Dyck paths of semilength n with all ascent lengths <= k. A(4,2) = 9: /\/\/\/\, //\\/\/\, /\//\\/\, /\/\//\\, //\/\\/\, //\/\/\\, /\//\/\\, //\\//\\, //\//\\\.

Also the number of permutations p of [n] such that in 0p all up-jumps are <= k and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. A(4,2) = 9: 1234, 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2431.

			A(4,2) = 9:
.
.   o    o      o      o      o      o       o      o       o
.   |    |      |      |     / \    / \     / \    / \     / \
.   o    o      o      o    o   o  o   o   o   o  o   o   o   o
.   |    |     / \    / \   |          |  ( )        ( )  |   |
.   o    o    o   o  o   o  o          o  o o        o o  o   o
.   |   / \   |          |  |          |
.   o  o   o  o          o  o          o
.   |
.   o
.
Square array A(n,k) begins:
  1, 1,   1,   1,    1,    1,    1,    1,    1, ...
  0, 1,   1,   1,    1,    1,    1,    1,    1, ...
  0, 1,   2,   2,    2,    2,    2,    2,    2, ...
  0, 1,   4,   5,    5,    5,    5,    5,    5, ...
  0, 1,   9,  13,   14,   14,   14,   14,   14, ...
  0, 1,  21,  36,   41,   42,   42,   42,   42, ...
  0, 1,  51, 104,  125,  131,  132,  132,  132, ...
  0, 1, 127, 309,  393,  421,  428,  429,  429, ...
  0, 1, 323, 939, 1265, 1385, 1421, 1429, 1430, ...

Alois P. Heinz, Rows n = 0..140, flattened
N. Hein and J. Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015
Index entries for sequences related to rooted trees

Columns k=0..10 give: A000007, A000012, A001006, A036765, A036766, A036767, A036768, A036769, A291823, A291824, A291825.
Main diagonal (and upper diagonals) give A000108.
First lower diagonal gives A001453.
Cf. A203717.

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(1, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
A:= (n, k)-> b(0, n, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[u_, o_, k_] := b[u, o, k] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, k], {j, 1, Min[1, u]}] + Sum[b[u + j - 1, o - j, k], {j, 1, Min[k, o]}]];
A[n_, k_] := b[0, n, k];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Oct 27 2017, translated from Maple *)

T(n,k)=polcoeff(serreverse(x*(1-x)/(1-x*x^k) + O(x^2*x^n)), n+1);
for(n=0, 10, for(k=0, 10, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 29 2017

A(n,k) = Sum_{j=0..k} A203717(n,j).
G.f. of column k: G(x)/x where G(x) is the reversion of x*(1-x)/(1-x^(k+1)). - Andrew Howroyd, Nov 30 2017
G.f. g_k(x) of column k satisfies: g_k(x) = Sum_{j=0..k} (x*g_k(x))^j. - Alois P. Heinz, May 05 2019
A(n,k) = Sum_{j=0..n/(k+1)} (-1)^j/(n+1) * binomial(n+1,j) * binomial(2*n-j*(k+1),n). [Hein Eq (10)] - R. J. Mathar, Oct 14 2022; corrected by Tijn Caspar de Leeuw, Jul 07 2024

A140662 Number of possible column states for self-avoiding polygons in a slit of width n.

Original entry on oeis.org

1, 3, 8, 20, 50, 126, 322, 834, 2187, 5797, 15510, 41834, 113633, 310571, 853466, 2356778, 6536381, 18199283, 50852018, 142547558, 400763222, 1129760414, 3192727796, 9043402500, 25669818475, 73007772801, 208023278208, 593742784828, 1697385471210, 4859761676390

Offset: 1

R. J. Mathar, Jul 11 2008

Number of Dyck (n+1)-paths whose maximum ascent length is 2. - David Scambler, Aug 22 2012

Number of (n+1)-Motzkin-paths with at least one up-step (see A001006 and the Python program). - Peter Luschny, Dec 03 2024

			The 20 Motzkin-paths of length 5 with at least one up-step are: UUDDF, UUDFD, UUFDD, UDUDF, UDUFD, UDFUD, UDFFF, UFUDD, UFDUD, UFDFF, UFFDF, UFFFD, FUUDD, FUDUD, FUDFF, FUFDF, FUFFD, FFUDF, FFUFD, FFFUD.

J. Alvarez, E.J. Janse van Rensburg et al. Self-avoiding walks and polygons in slits.
Xiaomei Chen, Counting humps and peaks in Motzkin paths with height k, arXiv:2412.00668 [math.CO], 2024. See p. 7.
Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 148.

Cf. A055151, A080159, A088617, A107131, A097610.
Cf. A001006.
Column k=2 of A203717 (shifted).

a := n -> n*(n + 1)*hypergeom([1, -n/2 + 1, 1/2 - n/2], [2, 3], 4)/2:
seq(simplify(a(n)), n = 1..30);  # Peter Luschny, Dec 03 2024

# A generator of the Motzkin-paths with at least one up-step.
C = str.count
def aGen(n: int): # -> Generator[str, Any, list[str]]
    a = [""]
    for w in a:
        if len(w) == n + 1:
            if (C(w, "U") > 0 and C(w, "U") == C(w, "D")): yield w
        else:
            for j in "UDF":
                u = w + j
                if C(u, "U") >= C(u, "D"): a += [u]
    return a
for n in range(1, 6):
    SAP = [w for w in aGen(n)]
    print(len(SAP), ":", SAP)  # Peter Luschny, Dec 03 2024

a(n) = Sum_{m=1..[(n+1)/2]} (n+1)!/((n+1-2m)!m!(m+1)!).
a(n) = A001006(n + 1) - 1. [Corrected by Peter Luschny, Dec 03 2024]
D-finite with recurrence (n+3)*a(n) + (-4*n-7)*a(n-1) + (2*n+3)*a(n-2) + (4*n-5)*a(n-3) + 3*(-n+2)*a(n-4) = 0. - R. J. Mathar, Nov 01 2021
From Peter Luschny, Dec 03 2024: (Start)
a(n) = (1/2)*n*(n + 1)*hypergeom([1, -n/2 + 1, 1/2 - n/2], [2, 3], 4).
a(n) = n!*[x^n]((exp(x)*(-x^3 + 2*(2*x - 3)*x*BesselI(0,2*x) + (x*(5*x - 4) + 6)*BesselI(1, 2* x)))/x^3). (End)

A291662 Number of ordered rooted trees with 2n non-root nodes such that the maximal outdegree equals n.

Original entry on oeis.org

1, 1, 8, 53, 326, 1997, 12370, 77513, 490306, 3124541, 20030000, 129024469, 834451788, 5414950283, 35240152706, 229911617041, 1503232609082, 9847379391133, 64617565719052, 424655979547781, 2794563003870310, 18412956934908669, 121455445321173578

Offset: 0

Alois P. Heinz, Aug 28 2017

nonn

a(n) is also the number of permutations p of [2n] such that in 0p the largest up-jump equals n and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. a(2) = 8: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2431.

			a(2) = 8:
.
.    o      o      o      o      o       o      o       o
.    |      |      |     / \    / \     / \    / \     / \
.    o      o      o    o   o  o   o   o   o  o   o   o   o
.    |     / \    / \   |          |  ( )        ( )  |   |
.    o    o   o  o   o  o          o  o o        o o  o   o
.   / \   |          |  |          |
.  o   o  o          o  o          o

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

Cf. A203717.

Bisection (even part) of A303259.

b[n_, t_, k_] := b[n, t, k] = If[n == 0, 1, If[t > 0, Sum[b[j - 1, k, k]* b[n - j, t - 1, k], {j, 1, n}], b[n - 1, k, k]]];
T[n_, k_] := b[n, k - 1, k - 1] - If[k == 1, 0, b[n, k - 2, k - 2]];
a[n_] := T[2n, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 29 2019, after Alois P. Heinz in A203717 *)

from sympy.core.cache import cacheit
@cacheit
def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(1, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])
def a(n): return b(0, 2*n, n) - (0 if n==0 else b(0, 2*n, n - 1))
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 30 2017

a(n) = A203717(2n,n).

a(n) ~ (27/4)^n / sqrt(3*Pi*n). - Vaclav Kotesovec, May 02 2018

A303259 Number of ordered rooted trees with n non-root nodes such that the maximal outdegree equals ceiling(n/2).

Original entry on oeis.org

1, 1, 1, 3, 8, 15, 53, 84, 326, 495, 1997, 3003, 12370, 18564, 77513, 116280, 490306, 735471, 3124541, 4686825, 20030000, 30045015, 129024469, 193536720, 834451788, 1251677700, 5414950283, 8122425444, 35240152706, 52860229080, 229911617041, 344867425584

Offset: 0

Alois P. Heinz, Apr 20 2018

nonn

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

Bisections give: A291662 (even part), A005809 (odd part).

Cf. A203717.

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(1, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
a:= n-> `if`(n=0, 1, (j-> b(0, n, j)-b(0, n, j-1))(ceil(n/2))):
seq(a(n), n=0..35);

b[u_, o_, k_] := b[u, o, k] = If[u + o == 0, 1,
     Sum[b[u - j, o + j - 1, k], {j, 1, Min[1, u]}] +
     Sum[b[u + j - 1, o - j, k], {j, 1, Min[k, o]}]];
a[n_] := If[n == 0, 1, With[{j = Ceiling[n/2]}, b[0, n, j]-b[0, n, j-1]]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Mar 19 2022, after Alois P. Heinz *)

a(n) = A203717(n,ceiling(n/2)).

A303271 Number of ordered rooted trees with n non-root nodes such that the maximal outdegree equals three.

Original entry on oeis.org

1, 4, 15, 53, 182, 616, 2070, 6930, 23166, 77429, 258973, 867230, 2908633, 9772556, 32896088, 110949072, 374934201, 1269505482, 4306750577, 14638006449, 49843505965, 170021694271, 580954640775, 1988357053020, 6816047416230, 23400699072231, 80455436055699

Offset: 3

Alois P. Heinz, Apr 20 2018

nonn

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

Column k=3 of A203717.

Cf. A001006, A036765.

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(1, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
a:= n-> b(0, n, 3)-b(0, n, 2):
seq(a(n), n=3..35);

a(n) = A036765(n) - A001006(n).

cp's OEIS Frontend

A291680 Number T(n,k) of permutations p of [n] such that in 0p the largest up-jump equals k and no down-jump is larger than 2; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A288942 Number A(n,k) of ordered rooted trees with n non-root nodes and all outdegrees <= k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A140662 Number of possible column states for self-avoiding polygons in a slit of width n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A291662 Number of ordered rooted trees with 2n non-root nodes such that the maximal outdegree equals n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A303259 Number of ordered rooted trees with n non-root nodes such that the maximal outdegree equals ceiling(n/2).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A303271 Number of ordered rooted trees with n non-root nodes such that the maximal outdegree equals three.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula