A036765 -id:A036765 - cp's OEIS frontend

A348202 Number of nonnegative lattice paths from (0,0) to (n,0) using steps in {(1,-4), (1,-1), (1,0), (1,1)}.

1, 1, 2, 4, 9, 22, 57, 155, 435, 1249, 3645, 10770, 32143, 96747, 293359, 895373, 2748803, 8483035, 26302248, 81896176, 255967640, 802790415, 2525691721, 7968972542, 25209580699, 79942927651, 254077293876, 809192984902, 2582113984084, 8254273128869

Offset: 0

Alois P. Heinz, Oct 06 2021

Alois P. Heinz, Table of n, a(n) for n = 0..1907
Alois P. Heinz, Animation of a(7) = 155 paths
Wikipedia, Counting lattice paths

Cf. A000108, A001006, A025235, A036765, A333069, A333105, A337067.

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, add(b(x-1, y-j), j=[-4, -1, 0, 1])))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..31);

b[x_, y_] := b[x, y] = If[y < 0 || y > x, 0, If[x == 0, 1, Sum[b[x - 1, y - j], {j, {-4, -1, 0, 1}}]]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Dec 28 2022, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = 3.3640233336410979391691803264403704977... is the root of the equation 256*d^5 - 1280*d^4 + 960*d^3 + 2267*d^2 - 1324*d - 4112 = 0 and c = 0.710307351107763693658610320440791667652705027171696102847138... - Vaclav Kotesovec, Oct 24 2021

A378426 Expansion of (1/x) * Series_Reversion( x / (1 + x + x^2 * (1 + x)^2) ).

Original entry on oeis.org

1, 1, 2, 6, 18, 56, 184, 624, 2161, 7621, 27283, 98869, 361967, 1336843, 4974763, 18634683, 70207751, 265874119, 1011475368, 3863846328, 14814818017, 56994831109, 219941836172, 851138940402, 3302281633591, 12842844277471, 50056915575566, 195503017533502

Offset: 0

Seiichi Manyama, Nov 25 2024

nonn

Index entries for reversions of series

Cf. A036765, A378425.

Cf. A378405.

my(N=30, x='x+O('x^N)); Vec(serreverse(x/(1+x+x^2*(1+x)^2))/x)

a(n) = sum(k=0, n\2, binomial(n+1, k)*binomial(n+k+1, n-2*k))/(n+1);

G.f.: exp( Sum_{k>=1} A378405(k) * x^k/k ).
a(n) = (1/(n+1)) * [x^n] (1 + x + x^2 * (1 + x)^2)^(n+1).
a(n) = (1/(n+1)) * Sum_{k=0..floor(n/2)} binomial(n+1,k) * binomial(n+k+1,n-2*k).

A382060 Number of rooted ordered trees with n nodes such that the degree of each node is less than or equal to its depth plus one.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 10, 27, 77, 231, 719, 2302, 7541, 25177, 85405, 293635, 1021272, 3587674, 12713796, 45402113, 163244197, 590529759, 2147915920, 7851127319, 28826079193, 106268313333, 393218951710, 1459969448090, 5437679646441, 20311366912839, 76072367645347, 285623120079865, 1074888308119285

Offset: 0

John Tyler Rascoe, Mar 14 2025

nonn

The root vertex is depth d=0 and is to have <= d+1 = 1 children so these are "planted" trees.

			a(5) = 4 counts:
                               depth:
   o     o       o       o       0
   |     |       |       |
   o     o       o       o       1
   |     |      / \     / \
   o     o     o   o   o   o     2
   |    / \    |           |
   o   o   o   o           o     3
   |
   o                             4

John Tyler Rascoe, Python program.
Kevin Ryde, PARI/GP program

Cf. A000081, A000108, A000957, A036765, A288942, A358586, A358590, A380761.

PARI
```
\\ see links
```
Python
```
# see links
```

A262082 Array of coefficients A(n,k) of the formal power series P(n,x) read by upwards antidiagonals, where P(n,x) = Sum_{k>=0} A(n,k)x^k = 1 + xP(n,x)^(1n) + x^2P(n,x)^(2n) + x^3P(n,x)^(3*n) for n >= 0.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 5, 0, 1, 1, 4, 12, 13, 0, 1, 1, 5, 22, 54, 36, 0, 1, 1, 6, 35, 139, 262, 104, 0, 1, 1, 7, 51, 284, 953, 1337, 309, 0, 1, 1, 8, 70, 505, 2509, 6894, 7072, 939, 0, 1, 1, 9, 92, 818, 5455, 23426, 51796, 38426, 2905, 0, 1, 1, 10

Offset: 0

Werner Schulte, Sep 10 2015

The terms define the array A(n,k):
  n\k:  0  1   2   3    4     5      6      7       8     9  10  ...
    0:  1  1   1   1    0     0      0      0       0     0   0  ...
    1:  1  1   2   5   13    36    104    309     939  2905  ...
    2:  1  1   3  12   54   262   1337   7072   38426  ...
    3:  1  1   4  22  139   953   6894  51796  400269  ...
    4:  1  1   5  35  284  2509  23426  ...
    5:  1  1   6  51  505  5455  62336  ...
    6:  1  1   7  70  818  ...
    7:  1  1   8  92  ...
    8:  1  1   9  ...
    9:  1  1  10  ...
   10:  1  1  ...
   11:  1  ...
  etc.
  For row 1 see A036765, for row 2 see A186241, and for row 3 see A200731.
Conjecture 1: The A(n,k), here n > 0, are the number of lattice paths, if
  (a) length of path is k*n (for the k-th term of row n),
  (b) allowed steps are (1,-1), (1,-1+n), (1,-1+2*n), and (1,-1+3*n),
  (c) you start at (0,0), end at (k*n,0), and
  (d) never cross the x-axis.
Conjecture 2: The coefficients B(m,n,k) of the P(n,x)^m (see the formula below), m > 0 and n > 0, are the number of lattice paths, if
  (a) length of path is k*n+m-1 (k-th coefficient of P(n,x)^m),
  (b) allowed steps are (1,-1), (1,-1+n), (1,-1+2*n), and (1,-1+3*n),
  (c) you start at (0,m-1), end at (k*n+m-1,0), and
  (d) never cross the x-axis.

			The terms of the array A(n,k) read by upwards antidiagonals define the triangle T(n,m) = A(n-m,m) for 0 <= m <= n, i.e.,
n\m 0  1   2   3    4     5     6     7    8  9 ...
0:  1
1:  1  1
2:  1  1   1
3:  1  1   2   1
4:  1  1   3   5    0
5:  1  1   4  12   13     0
6:  1  1   5  22   54    36     0
7:  1  1   6  35  139   262   104     0
8:  1  1   7  51  284   953  1337   309    0
9:  1  1   8  70  505  2509  6894  7072  939  0
etc. [reformatted by _Wolfdieter Lang_, Oct 15 2015]

Cf. A036765, A186241, A200731, A261440.

A(n,k) = 1/(n*k+1) * Sum_{j=0..k} (-2)^j*binomial(n*k+1,j)* binomial(3*n*k+3-2*j,k-j) for n >= 0, and k >= 0. (conjectured)
A(n,0) = A(n,1) = 1, n >= 0;
  A(n,2) = n+1, n >= 0;
  A(n,3) = (3*n^2+5*n+2)/2, n >= 0;
  A(n,4) = (8*n^3+18*n^2+13*n)/3, n >= 0;
  A(n,5) = (125*n^4+350*n^3+355*n^2+34*n)/24, n >= 0.
The g.f. P(n,x) of row n of the array A(n,k) satisfy:
  P(n,x) = P(n-1,x*P(n,x)), n > 0;
  P(n,x) = P(n-2,x*P(n,x)^2), n > 1;
  etc.
  P(n,x) = P(0,x*P(n,x)^n), n >= 0.
The coefficients B(m,n,k) of the P(n,x)^m are:
  B(m,n,k) = m/(n*k+m) * Sum_{j=0..k} (-2)^j*binomial(n*k+m,j)* binomial(3*n*k+3*m-2*j,k-j) for m > 0, n > 0, and k >= 0. (conjectured)
P(n,x) = exp(Sum_{k>=1} 1/(n*k)*(Sum_{j=0..k} (-2)^j*binomial(n*k,j)* binomial(3*n*k-2*j,k-j))) for n > 0 (conjectured); (see for n=1: A036765, for n=2: A186241, and for n=3: A200731).
P(n,x/(1+x+x^2+x^3)^n) = 1+x+x^2+x^3 for n >= 0. - Werner Schulte, Nov 20 2015

A369439 Expansion of (1/x) * Series_Reversion( x / ((1+x)^2 * (1+x^2)) ).

Original entry on oeis.org

1, 2, 6, 22, 89, 382, 1708, 7870, 37108, 178184, 868318, 4283402, 21347902, 107330004, 543707480, 2772469998, 14219396908, 73303128344, 379621891640, 1974078923416, 10303600000553, 53960438323438, 283461807342876, 1493252678987602, 7886649917261724

Offset: 0

Seiichi Manyama, Jan 23 2024

nonn

Index entries for reversions of series

Cf. A036765.

my(N=30, x='x+O('x^N)); Vec(serreverse(x/((1+x)^2*(1+x^2)))/x)

a(n, s=2, t=1, u=2) = sum(k=0, n\s, binomial(t*(n+1), k)*binomial(u*(n+1), n-s*k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/2)} binomial(n+1,k) * binomial(2*n+2,n-2*k).

A369444 Expansion of (1/x) * Series_Reversion( x / ((1+x) * (1+x^4)) ).

Original entry on oeis.org

1, 1, 1, 1, 2, 7, 22, 57, 131, 298, 738, 2003, 5600, 15380, 41224, 109769, 296009, 813315, 2261647, 6305930, 17554044, 48851034, 136350556, 382408995, 1077164245, 3042452536, 8606495236, 24377127256, 69159381856, 196600128592, 559990599808, 1597797525833

Offset: 0

Seiichi Manyama, Jan 23 2024

nonn

Index entries for reversions of series

Cf. A036765, A198951.

my(N=40, x='x+O('x^N)); Vec(serreverse(x/((1+x)*(1+x^4)))/x)

a(n, s=4, t=1, u=1) = sum(k=0, n\s, binomial(t*(n+1), k)*binomial(u*(n+1), n-s*k))/(n+1);

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/4)} binomial(n+1,k) * binomial(n+1,n-4*k).

A384937 Number for rooted ordered trees with edge weights summing to n, where edge weights are all greater than zero, and the sequences of edge weights in all downward paths are weakly increasing.

Original entry on oeis.org

1, 1, 3, 9, 30, 103, 372, 1379, 5248, 20356, 80252, 320581, 1295018, 5280967, 21711163, 89890559, 374478935, 1568585095, 6602283315, 27910296899, 118448905668, 504466997897, 2155412350793, 9236401247438, 39686616306747, 170946789568804, 738024717474360

Offset: 0

John Tyler Rascoe, Jun 12 2025

nonn

			The following tree with sum of edge weights 13 contains downward paths of edge weights (1), (2,3,4), and (2,3,3) all of which are weakly increasing. So this tree is counted under a(13) = 5280967.
           o
        2 / \ 1
         o   o
      3 / 	
       o
    4 / \ 3	
     o   o

Cf. A000108, A000169, A000957, A001764, A036765, A384747, A384748.

w(j,k,N) = {if(k>N,1, 1/(1 - sum(i=j,N, x^i * w(i,k+1,N-i+1))))}
Ax(N) = {Vec(w(1,1,N)+ O('x^(N+1)))}
Ax(10)

G.f.: G_1(x) where G_k(x) = 1/(1 - Sum_{i>=k} x^i * G_i(x)).

A384938 Number for rooted ordered trees with edge weights summing to n, where edge weights are all greater than zero, and the sequences of edge weights in all downward paths are strictly increasing.

Original entry on oeis.org

1, 1, 2, 5, 11, 26, 61, 142, 334, 785, 1845, 4339, 10211, 24030, 56560, 133143, 313433, 737906, 1737275, 4090206, 9630067, 22673482, 53383917, 125691264, 295938451, 696785116, 1640579144, 3862745470, 9094847357, 21413863699, 50419073794, 118712060012, 279508439419

Offset: 0

John Tyler Rascoe, Jun 13 2025

nonn

			The following tree with sum of edge weights 15 contains downward paths of edge weights (1), (2,3,4), and (2,3,5) all of which are weakly increasing. So this tree is counted under a(13) = 133143.
           o
        2 / \ 1
         o   o
      3 / 	
       o
    4 / \ 5	
     o   o

Cf. A000108, A000169, A000957, A001764, A036765, A384747, A384748.

w(j,k,N) = {if(k>N,1, 1/(1 - sum(i=j+1,N, x^i * w(i,k+1,N-i+1))))}
Bx(N) = {my(x='x+O('x^(N+1))); Vec(w(0,1,N)+ O('x^(N+1)))}
Bx(10)

G.f.: G_0(x) where G_k(x) = 1/(1 - Sum_{i>k} x^i * G_i(x)).

cp's OEIS Frontend

A348202 Number of nonnegative lattice paths from (0,0) to (n,0) using steps in {(1,-4), (1,-1), (1,0), (1,1)}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A378426 Expansion of (1/x) * Series_Reversion( x / (1 + x + x^2 * (1 + x)^2) ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A382060 Number of rooted ordered trees with n nodes such that the degree of each node is less than or equal to its depth plus one.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

A262082 Array of coefficients A(n,k) of the formal power series P(n,x) read by upwards antidiagonals, where P(n,x) = Sum_{k>=0} A(n,k)*x^k = 1 + x*P(n,x)^(1*n) + x^2*P(n,x)^(2*n) + x^3*P(n,x)^(3*n) for n >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A369439 Expansion of (1/x) * Series_Reversion( x / ((1+x)^2 * (1+x^2)) ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A369444 Expansion of (1/x) * Series_Reversion( x / ((1+x) * (1+x^4)) ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A384937 Number for rooted ordered trees with edge weights summing to n, where edge weights are all greater than zero, and the sequences of edge weights in all downward paths are weakly increasing.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A384938 Number for rooted ordered trees with edge weights summing to n, where edge weights are all greater than zero, and the sequences of edge weights in all downward paths are strictly increasing.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A262082 Array of coefficients A(n,k) of the formal power series P(n,x) read by upwards antidiagonals, where P(n,x) = Sum_{k>=0} A(n,k)x^k = 1 + xP(n,x)^(1n) + x^2P(n,x)^(2n) + x^3P(n,x)^(3*n) for n >= 0.