A323229 -id:A323229 - cp's OEIS frontend

A212382 Number A(n,k) of Dyck n-paths all of whose ascents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 5, 1, 1, 1, 1, 2, 14, 1, 1, 1, 1, 1, 5, 42, 1, 1, 1, 1, 1, 2, 12, 132, 1, 1, 1, 1, 1, 1, 6, 30, 429, 1, 1, 1, 1, 1, 1, 2, 16, 79, 1430, 1, 1, 1, 1, 1, 1, 1, 7, 37, 213, 4862, 1, 1, 1, 1, 1, 1, 1, 2, 22, 83, 584, 16796, 1

Offset: 0

Alois P. Heinz, May 12 2012

Lengths of descents are unrestricted.

For p>0 is column p asymptotic to a(n) ~ s^2 / (n^(3/2) * r^(n-1/2) * sqrt(2*Pi*p*(s-1)*(1+s/(1+p*(s-1))))), where r and s are real roots (0 < r < 1) of the system of equations r = p*(s-1)^2 / (s*(1-p+p*s)), (r*s)^p = (s-1-r*s)/(s-1). - Vaclav Kotesovec, Jul 16 2014

			A(0,k) = 1: the empty path.
A(3,0) = 1: UDUDUD.
A(3,1) = 5: UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD.
A(3,2) = 2: UDUDUD, UUUDDD.
A(5,3) = 6: UDUDUDUDUD, UDUUUUDDDD, UUUUDDDDUD, UUUUDDDUDD, UUUUDDUDDD, UUUUDUDDDD.
Square array A(n,k) begins:
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   2,  1,  1,  1,  1,  1,  1, ...
  1,   5,  2,  1,  1,  1,  1,  1, ...
  1,  14,  5,  2,  1,  1,  1,  1, ...
  1,  42, 12,  6,  2,  1,  1,  1, ...
  1, 132, 30, 16,  7,  2,  1,  1, ...
  1, 429, 79, 37, 22,  8,  2,  1, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Vaclav Kotesovec, Asymptotic of subsequences of A212382

Columns k=0-10 give: A000012, A000108, A101785, A212383, A212384, A212385, A212386, A212387, A212388, A212389, A212390.

A(2n,n) gives A323229.

b:= proc(x, y, k, u) option remember;
      `if`(x<0 or y `if`(k=0, 1, b(n, n, k, true)):
seq(seq(A(n, d-n), n=0..d), d=0..15);
# second Maple program
A:= (n, k)-> `if`(k=0, 1, coeff(series(RootOf(
               A||k=1+x*A||k/(1-(x*A||k)^k), A||k), x, n+1), x, n)):
seq(seq(A(n, d-n), n=0..d), d=0..15);

b[x_, y_, k_, u_] := b[x, y, k, u] = If[x<0 || yJean-François Alcover, Jan 15 2014, translated from first Maple program *)

G.f. of column k>0 satisfies: A_k(x) = 1+x*A_k(x)/(1-(x*A_k(x))^k), g.f. of column k=0: A_0(x) = 1/(1-x).

G.f. of column k>0 is series_reversion(B(x))/x where B(x) = x/(1 + x + x^(k+1) + x^(2*k+1) + x^(3*k+1) + ... ) = x/(1+x/(1-x^k)); for Dyck paths with allowed ascent lengths {u_1, u_2, ...} use B(x) = x/( 1 + sum(k>=1, x^{u_k} ) ). - Joerg Arndt, Apr 23 2016

A260878 Number of set partitions of {1, 2, ..., 2*n} with sizes in {[n, n], [2n]}.

Original entry on oeis.org

2, 2, 4, 11, 36, 127, 463, 1717, 6436, 24311, 92379, 352717, 1352079, 5200301, 20058301, 77558761, 300540196, 1166803111, 4537567651, 17672631901, 68923264411, 269128937221, 1052049481861, 4116715363801, 16123801841551, 63205303218877, 247959266474053

Offset: 0

Peter Luschny, Aug 02 2015

Third column in A260876.

			The set partitions counted by a(3) = 11 are: {{1, 2, 3, 4, 5, 6}},
{{1, 2, 4}, {3, 5, 6}}, {{1, 2, 3}, {4, 5, 6}}, {{1, 3, 4}, {2, 5, 6}},
{{1, 3, 5}, {2, 4, 6}}, {{1, 4, 5}, {2, 3, 6}}, {{1, 5, 6}, {2, 3, 4}},
{{1, 4, 6}, {2, 3, 5}}, {{1, 3, 6}, {2, 4, 5}}, {{1, 2, 6}, {3, 4, 5}},
{{1, 2, 5}, {3, 4, 6}}.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Hans Salié, Über die Koeffizienten der Blasiusschen Reihe, Math. Nachr. 1955, (14, 4-6), 241--248.

a(n) = A112849(n) for n >= 2. - Alois P. Heinz, Aug 06 2015
a(n) = A052473(n+2) - 1.
a(n) = A088218(n) + 1.
a(n) = (-1)^n*A110556(n) + 1.
a(n+1) - a(n) = A097613(n+1) for n > 0.
Cf. A260876, A001700.
Cf. A323230 (d=0), this sequence (d=1), A323229 (d=2).

a := proc(n) option remember;
if n < 2 then [2, 2][n+1] else ((4*n - 2)*a(n-1) - 3*n + 2)/n fi end:
seq(a(n), n=0..26); # Or:
egf := n -> exp(exp(x)*(1 - (GAMMA(n,x)/GAMMA(n)))):
a := n -> `if`(n<2, 2, (2*n)!*coeff(series(egf(n), x, 2*n+1), x, 2*n)):
seq(a(n), n=0..26); # Peter Luschny, Aug 02 2019

Table[Binomial[2 n - 1, n] + 1, {n, 0, 26}] (* or *)
CoefficientList[Series[(4 x^2 - 13 x + 3 + Sqrt[(1 - 4 x) (x - 1)^2])/(2 (4 x - 1) (x - 1)), {x, 0, 26}], x] (* Michael De Vlieger, Feb 26 2017 *)

Sage
```
print([A260876(n,2) for n in (0..30)])
```

# Alternative:
def A260878():
    a, f, s, n = 2, 2, 1, 1
    yield a
    while True:
        yield a
        f += 4; s += 3; n += 1
        a = (f*a - s)/n
a = A260878()
print([next(a) for n in range(27)]) # Peter Luschny, Aug 02 2019

G.f.: (4*x^2 - 13*x + 3 + sqrt((1 - 4*x)*(x - 1)^2))/(2*(4*x - 1)*(x - 1)). - Alois P. Heinz, Aug 06 2015
a(n) = Binomial(2*n-1, n) + 1. - Vladimir Kruchinin, Feb 26 2017
The generating function G(x) satisfies the differential equation x^3 + 2*x = (4*x^4 - 9*x^3 + 6*x^2 - x)*diff(G(x), x) + (2*x^3 - 4*x^2 + 2*x)*G(x). - Peter Luschny, Feb 12 2019
From Peter Luschny, Aug 02 2019: (Start)
a(n) = ((4*n - 2)*a(n-1) - 3*n + 2)/n for n >= 2.
a(n) = (2*n)! * [x^(2*n)] exp(exp(x)*(1 - (Gamma(n,x)/Gamma(n)))) for n >= 2.
a(n) ~ 4^n/sqrt(4*Pi*n). More precise asymptotic estimates are:
1 + (4^n/sqrt(n*Pi)) * (1/2 - 1/(16*n) * (1 - 1/(16*n))), and
1 + 4^n*(2 - 2/N^2 + 21/N^4 - 671/N^6) / sqrt(2*N*Pi) with N = 8*n + 2.
Let b(n) = binomial(2*(n-1), n-1) + 1 = A323230(n) for n >= 0. Then by Salié:
p divides a(p+k) - b(k+1) if p is a prime > k and 0 <= k <= 4.
Conjecture: p divides a(p+5) - b(6) if p is a prime > b(6).
If p is a prime divisor of n then a(n) == a(n/p) (mod p) (by Salié, theorem 2).
(End)
From Peter Bala, Apr 20 2024: (Start)
a(n) = Sum_{k = 0..n} (-1)^k * 3*n/(2*n + k) * binomial(2*n+k, n-k) for n >= 1.
a(n) = Sum_{k = 0..n} (-1)^k * 3*n/(n + 2*k) * binomial(2*n+k-1, n-k) for n >= 1.
(-1)^n * a(n) equals the n-th order Taylor polynomial (centered at 0) of 1/c(x)^(3*n) evaluated at x = 1, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. of the Catalan numbers A000108. (End)

A379822 Triangle read by rows: T(n, k) is the number of walks of length n on the Z X Z grid with unit steps in all four directions (NSWE) starting at (0, 0), and ending on the vertical line x = 0 if k = 0, or on the line x = k or x = -(n + 1 - k) if k > 0.

Original entry on oeis.org

1, 2, 2, 6, 5, 5, 20, 16, 12, 16, 70, 57, 36, 36, 57, 252, 211, 130, 90, 130, 211, 924, 793, 507, 286, 286, 507, 793, 3432, 3004, 2016, 1092, 728, 1092, 2016, 3004, 12870, 11441, 8024, 4488, 2380, 2380, 4488, 8024, 11441, 48620, 43759, 31842, 18717, 9384, 6120, 9384, 18717, 31842, 43759

Offset: 0

Peter Luschny, Jan 16 2025

			  [0] [    1]
  [1] [    2,     2]
  [2] [    6,     5,     5]
  [3] [   20,    16,    12,    16]
  [4] [   70,    57,    36,    36,   57]
  [5] [  252,   211,   130,    90,  130,  211]
  [6] [  924,   793,   507,   286,  286,  507,  793]
  [7] [ 3432,  3004,  2016,  1092,  728, 1092, 2016,  3004]
  [8] [12870, 11441,  8024,  4488, 2380, 2380, 4488,  8024, 11441]
  [9] [48620, 43759, 31842, 18717, 9384, 6120, 9384, 18717, 31842, 43759]
.
For n = 3 we get the walks depending on the x-coordinate of the endpoint:
W(x= 3) = {WWW},
W(x= 2) = {NWW,WWN,WNW,SWW,WSW,WWS},
W(x= 1) = {NNW,NWN,WNN,NSW,NWS,SWN,SNW,WWE,WEW,EWW,WNS,WSN,SWS,SSW,WSS},
W(x= 0) = {NNN,NNS,NSN,NWE,NEW,SNN,EWN,WNE,WEN,ENW,SNS,SSN,SWE,SEW,WSE,WES,ESW,EWS,NSS,SSS},
W(x=-1) = {NNE,ENN,NEN,NSE,NES,SNE,SEN,WEE,ENS,ESN,EWE,EEW,SSE,SES,ESS},
W(x=-2) = {NEE,SEE,ENE,ESE,EEN,EES},
W(x=-3) = {EEE}.
T(3, 0) = card(W(x=0)) = 20, T(3, 1) = card(W(x=1)) + card(W(x=-3)) = 16,
T(3, 2) = card(W(x=2)) + card(W(x=-2)) = 12, T(3, 3) = card(W(x=3)) + card(W(x=-1)) = 16.

Paolo Xausa, Table of n, a(n) for n = 0..11475 (rows 0..150 of triangle, flattened).
Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Philippe Flajolet, Institut Henri Poincaré, March 28, 2013.
Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009; Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AK, (FPSAC 2009).
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Related triangles: A052174 (first quadrant), A378067 (upper plane), this triangle (whole plane).

Cf. A000984 (column 0), A323229 (column 1 and main diagonal), A000302 (row sums), A068551 (row sum without column 0), A283799 (row minimum).

T := (n, k) -> binomial(2*n, n - k) + binomial(2*n, k - 1):
seq(print(seq(T(n, k), k = 0..n)), n = 0..9);

A379822[n_, k_] := Binomial[2*n, n - k] + Binomial[2*n, k - 1];
Table[A379822[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, May 29 2025 *)

from dataclasses import dataclass
@dataclass
class Walk:
    s: str = ""
    x: int = 0
    y: int = 0
def Trow(n: int) -> list[int]:
    W = [Walk()]
    row = [0] * (n + 1)
    for w in W:
        if len(w.s) == n:
            row[w.x] += 1
        else:
            for s in "NSWE":
                x = y = 0
                match s:
                    case "W": x =  1
                    case "E": x = -1
                    case "N": y =  1
                    case "S": y = -1
                    case _  : pass
                W.append(Walk(w.s + s, w.x + x, w.y + y))
    return row
for n in range(10): print(Trow(n))

T(n, k) = binomial(2*n, n - k) + binomial(2*n, k - 1).

Sum_{k=1..n} T(n, k) = A068551(n).

A323231 A(n, k) = [x^k] (1/(1-x) + x/(1-x)^n), square array read by descending antidiagonals for n, k >= 0.

Original entry on oeis.org

1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 2, 4, 4, 2, 1, 1, 2, 5, 7, 5, 2, 1, 1, 2, 6, 11, 11, 6, 2, 1, 1, 2, 7, 16, 21, 16, 7, 2, 1, 1, 2, 8, 22, 36, 36, 22, 8, 2, 1, 1, 2, 9, 29, 57, 71, 57, 29, 9, 2, 1, 1, 2, 10, 37, 85, 127, 127, 85, 37, 10, 2, 1

Offset: 0

Peter Luschny, Feb 10 2019

			Array starts:
[0] 1, 2,  1,  1,   1,   1,    1,    1,    1,     1,     1, ...
[1] 1, 2,  2,  2,   2,   2,    2,    2,    2,     2,     2, ... A040000
[2] 1, 2,  3,  4,   5,   6,    7,    8,    9,    10,    11, ... A000027
[3] 1, 2,  4,  7,  11,  16,   22,   29,   37,    46,    56, ... A000124
[4] 1, 2,  5, 11,  21,  36,   57,   85,  121,   166,   221, ... A050407
[5] 1, 2,  6, 16,  36,  71,  127,  211,  331,   496,   716, ... A145126
[6] 1, 2,  7, 22,  57, 127,  253,  463,  793,  1288,  2003, ... A323228
[7] 1, 2,  8, 29,  85, 211,  463,  925, 1717,  3004,  5006, ...
[8] 1, 2,  9, 37, 121, 331,  793, 1717, 3433,  6436, 11441, ...
[9] 1, 2, 10, 46, 166, 496, 1288, 3004, 6436, 12871, 24311, ...
.
Read as a triangle (by descending antidiagonals):
                                     1
                                  2,   1
                                1,   2,   1
                             1,   2,   2,   1
                           1,   2,   3,   2,   1
                        1,   2,   4,   4,   2,   1
                      1,   2,   5,   7,   5,   2,  1
                    1,  2,   6,  11,  11,   6,   2,  1
                  1,  2,   7,  16,  21,  16,   7,  2,  1
                1,  2,  8,  22,  36,  36,  22,   8,  2,  1
              1,  2,  9,  29,  57,  71,  57,  29,  9,  2,  1
.
A(0, 1) = C(-1, 0) + 1 = 2 because C(-1, 0) = 1. A(1, 0) = C(-1, -1) + 1 = 1 because C(-1, -1) = 0. Warning: Some computer algebra programs (for example Maple and Mathematica) return C(n, n) = 1 for n < 0. This contradicts the definition given by Graham et al. (see reference). On the other hand this definition preserves symmetry.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 154.

G. C. Greubel, Antidiagonals n = 0..50, flattened

Differs from A323211 only in the second term.
Rows include: A040000, A000027, A000124, A050407, A145126, A323228.
Diagonals A(n, n+d): A323230 (d=0), A260878 (d=1), A323229 (d=2).
Antidiagonal sums are A323227(n) if n!=1.
Cf. A007318 (Pascal's triangle).

using AbstractAlgebra
function Arow(n, len)
    R, x = PowerSeriesRing(ZZ, len+2, "x")
    gf = inv(1-x) + divexact(x, (1-x)^n)
    [coeff(gf, k) for k in 0:len-1] end
for n in 0:9 println(Arow(n, 11)) end

Binomial := (n, k) -> `if`(n < 0 and n = k, 0, binomial(n,k)):
A := (n, k) -> Binomial(n + k - 2, k - 1) + 1:
seq(lprint(seq(A(n, k), k=0..10)), n=0..10);

T[n_, k_]:= If[k==0, 1 + Boole[n==1], If[k==n, 1, Binomial[n-2, k-1] + 1]];
Table[T[n, k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Dec 27 2021 *)

def Arow(n):
    R. = PowerSeriesRing(ZZ, 20)
    gf = 1/(1-x) + x/(1-x)^n
    return gf.padded_list(10)
for n in (0..9): print(Arow(n))

A(n, k) = binomial(n + k - 2, k - 1) + 1. Note that binomial(n, n) = 0 if n < 0.
A(n, k) = A(k, n) with the exception A(1,0) != A(0,1).
A(n, n) = binomial(2*n-2, n-1) + 1 = A323230(n).
From G. C. Greubel, Dec 27 2021: (Start)
T(n, k) = binomial(n-2, k-1) + 1 with T(n, 0) = 1 + [n=1], T(n, n) = 1.
T(2*n, n) = A323230(n).
Sum_{k=0..n} T(n,k) = n + 1 + 2^(n-2) - [n=0]/4 + [n=1]/2. (End)

cp's OEIS Frontend

A212382 Number A(n,k) of Dyck n-paths all of whose ascents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260878 Number of set partitions of {1, 2, ..., 2*n} with sizes in {[n, n], [2n]}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Sage

Formula

A379822 Triangle read by rows: T(n, k) is the number of walks of length n on the Z X Z grid with unit steps in all four directions (NSWE) starting at (0, 0), and ending on the vertical line x = 0 if k = 0, or on the line x = k or x = -(n + 1 - k) if k > 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A323231 A(n, k) = [x^k] (1/(1-x) + x/(1-x)^n), square array read by descending antidiagonals for n, k >= 0.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Julia

Maple

Mathematica

Sage

Formula