A340591 -id:A340591 - cp's OEIS frontend

A335570 Number A(n,k) of n-step k-dimensional nonnegative lattice walks starting at the origin and using steps that increment all components or decrement one component by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 7, 6, 1, 1, 1, 5, 13, 17, 10, 1, 1, 1, 6, 21, 40, 47, 20, 1, 1, 1, 7, 31, 81, 136, 125, 35, 1, 1, 1, 8, 43, 146, 325, 496, 333, 70, 1, 1, 1, 9, 57, 241, 686, 1433, 1753, 939, 126, 1, 1, 1, 10, 73, 372, 1315, 3476, 6473, 6256, 2597, 252, 1

Offset: 0

Alois P. Heinz, Jan 26 2021

			A(2,2) = 3: [(0,0),(1,1),(2,2)], [(0,0),(1,1),(0,1)], [(0,0),(1,1),(1,0)].
Square array A(n,k) begins:
  1,  1,   1,    1,    1,     1,     1,      1, ...
  1,  1,   1,    1,    1,     1,     1,      1, ...
  1,  2,   3,    4,    5,     6,     7,      8, ...
  1,  3,   7,   13,   21,    31,    43,     57, ...
  1,  6,  17,   40,   81,   146,   241,    372, ...
  1, 10,  47,  136,  325,   686,  1315,   2332, ...
  1, 20, 125,  496, 1433,  3476,  7525,  14960, ...
  1, 35, 333, 1753, 6473, 18711, 46165, 102173, ...
  ...

Alois P. Heinz, Antidiagonals n = 0..60, flattened

Columns k=0-10 give: A000012, A001405, A151265, A149424, A346225, A346226, A346227, A346228, A346229, A346230, A346231.
Rows n=0+1,2-3 give: A000012, A000027(k+1), A002061(k+1).
Main diagonal gives A335588.
Cf. A340591.

b:= proc(n, l) option remember; `if`(n=0, 1, b(n-1, map(x-> x+1, l))+add(
     `if`(l[i]>0, b(n-1, sort(subsop(i=l[i]-1, l))), 0), i=1..nops(l)))
    end:
A:= (n, k)-> b(n, [0$k]):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[n_, l_] := b[n, l] = If[n == 0, 1, b[n - 1, l + 1] + Sum[If[l[[i]] > 0, b[n - 1, Sort[ReplacePart[l, i -> l[[i]] - 1]]], 0], {i, 1, Length[l]}]];
A[n_, k_] := b[n, Table[0, {k}]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jan 29 2021, after Alois P. Heinz *)

A(n,k) == 1 (mod k) for k >= 2.

A006335 a(n) = 4^n(3n)!/((n+1)!(2n+1)!).

Original entry on oeis.org

1, 2, 16, 192, 2816, 46592, 835584, 15876096, 315031552, 6466437120, 136383037440, 2941129850880, 64614360416256, 1442028424527872, 32619677465182208, 746569714888605696, 17262927525017812992, 402801642250415636480, 9474719710174783733760, 224477974671833337692160

Offset: 0

N. J. A. Sloane

Number of planar lattice walks of length 3n starting and ending at (0,0), remaining in the first quadrant and using only NE,W,S steps.
Equals row sums of triangle A140136. - Michel Marcus, Nov 16 2014
Number of linear extensions of the poset V x [n], where V is the 3-element poset with one least element and two incomparable elements: see Kreweras and Niederhausen (1981) and Hopkins and Rubey (2020) references. - Noam Zeilberger, May 28 2020

			G.f. = 1 + 2*x + 16*x^2 + 192*x^3 + 2816*x^4+ 46592*x^5 + 835584*x^6 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 0..700
Andrei Asinowski, Cyril Banderier, and Sarah J. Selkirk, From Kreweras to Gessel: A walk through patterns in the quarter plane, Séminaire Lotharingien de Combinatoire, Proc. 35th Conf. Formal Power Series and Alg. Comb. (Davis, 2023) Vol. 89B, Art. #30.
Olivier Bernardi, Bijective counting of Kreweras walks and loopless triangulations, Journal of Combinatorial Theory, Series A 114:5 (2007), 931-956.
M. Bousquet-Mélou, Walks in the quarter plane: Kreweras' algebraic model, arXiv:math/0401067 [math.CO], 2004-2006.
M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, arXiv:0810.4387 [math.CO], 2008.
Sam Hopkins and Martin Rubey, Promotion of Kreweras words, arXiv:2005.14031 [math.CO], 2020.
G. Kreweras, Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, 6 (1965), circa p. 82.
G. Kreweras and H. Niederhausen, Solution of an enumerative problem connected with lattice paths, European J. Combin., 2 (1981), 55-60.

Equals 2^(n-1) * A000309(n-1) for n>1.
Cf. A098272. First row of array A098273.
Column of A176129, A214631, A214722, A340591.

[4^n*Factorial(3*n)/(Factorial(n+1)*Factorial(2*n+1)) : n in [0..20]]; // Wesley Ivan Hurt, Nov 16 2014

A006335:=n->4^n*(3*n)!/((n+1)!*(2*n+1)!): seq(A006335(n), n=0..20); # Wesley Ivan Hurt, Nov 16 2014

aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, j, -1 + n] + aux[i, -1 + j, -1 + n] + aux[1 + i, 1 + j, -1 + n]]; Table[aux[0, 0, 3 n], {n, 0, 25}] (* Manuel Kauers, Nov 18 2008 *)
Table[(4^n (3 n)! / ((n + 1)! (2 n + 1)!)), {n, 0, 200}] (* Vincenzo Librandi, Nov 17 2014 *)

{a(n) = if( n<0, 0, 4^n * (3*n)! / ((n+1)! * (2*n+1)!))}; /* Michael Somos, Jan 23 2003 */

def a(n):
    return (4**n * binomial(3 * n, 2 * n)) // ((n + 1) * (2 * n + 1))
# F. Chapoton, Jun 01 2020

G.f.: (1/(12*x)) * (hypergeom([ -2/3, -1/3],[1/2],27*x)-1). - Mark van Hoeij, Nov 02 2009
a(n+1) = 6*(3*n+2)*(3*n+1)*a(n)/((2+n)*(2*n+3)). - Robert Israel, Nov 17 2014
a(n) ~ 3^(3*n + 1/2) / (4*sqrt(Pi)*n^(5/2)). - Vaclav Kotesovec, Mar 26 2016
E.g.f.: 2F2(1/3,2/3; 3/2,2; 27*x). - Ilya Gutkovskiy, Jan 25 2017

Edited by N. J. A. Sloane, Dec 20 2008 at the suggestion of R. J. Mathar

A055546 a(n) = (-1)^(n+1) * 2^n * n!^2.

Original entry on oeis.org

-1, 2, -16, 288, -9216, 460800, -33177600, 3251404800, -416179814400, 67421129932800, -13484225986560000, 3263182688747520000, -939796614359285760000, 317651255653438586880000, -124519292216147926056960000, 56033681497266566725632000000

Offset: 0

Eric W. Weisstein

sign

Coefficient of the Cayley-Menger determinant of order n.
A roller coaster has n rows of seats, each of which has room for two people.  |a(n)| is the number of ways n men and n women can be seated with a man and a woman in each row. - Geoffrey Critzer, Dec 17 2011
The o.g.f. of 1/a(n) is -BesselI(0,i*sqrt(2*x)), with i the imaginary unit. See Abramowitz-Stegun (reference and link under A008277), p. 375, 9.6.10. - Wolfdieter Lang, Jan 10 2012
|a(n)|/2 is the number of integers k such that the digits of k and 2*k, written in base 2*n, are permutations of 0, 1, ..., 2*n-1. - Yifan Xie, Apr 12 2025

Andrew Howroyd, Table of n, a(n) for n = 0..100
Paul C. Kainen, Construction numbers: How to build a graph?, arXiv:2302.13186 [math.CO], 2023.
Usman A. Khan, Soummya Kar and Jose M. F. Moura, A novel geometric approach towards a linear theory for sensor localization, 2013.
Alan L. Mackay, On the regular heptagon, J. Math. Chemistry, vol. 21, 1997, 197-209.
Eric Weisstein's World of Mathematics, Cayley-Menger Determinant.

Cf. A000079, A001044, A019669, A334381, A334383.

Row of A340591 (in absolute values).

Mathematica
```
Table[(-1)^(n+1)2^n n!^2, {n, 0, 20}]
```

a(n)={(-1)^(n+1) * 2^n * n!^2} \\ Andrew Howroyd, Nov 07 2019

E.g.f.: -arcsinh(x/sqrt(2))^2. - Vladeta Jovovic, Aug 30 2004
Sum_{n>=0} |a(n)|/(2*n+1)! = Pi/2. - Daniel Suteu, Feb 06 2017
a(n) = (-1)^(n+1) * A000079(n) * A001044(n). - Terry D. Grant, May 21 2017
From Amiram Eldar, Nov 18 2020: (Start)
Sum_{n>=0} 1/a(n) = (-1) * A334383.
Sum_{n>=0} (-1)^(n+1)/a(n) = A334381. (End)

Terms a(14) and beyond from Andrew Howroyd, Nov 07 2019

A340590 Number of n*(n+1)-step n-dimensional nonnegative closed lattice walks starting at the origin and using steps that increment all components or decrement one component by 1.

Original entry on oeis.org

1, 1, 16, 24444, 8204167296, 1052109889288796160, 78607706455594117933558272000, 4825997038234002956322487606996722432307200, 325844502690869718672482402463320899403011435565608069632000, 31176247959648026790291638390172796940342899651173947284143811081979726010777600

Offset: 0

Alois P. Heinz, Jan 12 2021

			a(2) = 16:
  [(0,0),(1,1),(0,1),(0,0),(1,1),(0,1),(0,0)],
  [(0,0),(1,1),(0,1),(0,0),(1,1),(1,0),(0,0)],
  [(0,0),(1,1),(0,1),(1,2),(0,2),(0,1),(0,0)],
  [(0,0),(1,1),(0,1),(1,2),(1,1),(0,1),(0,0)],
  [(0,0),(1,1),(0,1),(1,2),(1,1),(1,0),(0,0)],
  [(0,0),(1,1),(1,0),(0,0),(1,1),(0,1),(0,0)],
  [(0,0),(1,1),(1,0),(0,0),(1,1),(1,0),(0,0)],
  [(0,0),(1,1),(1,0),(2,1),(1,1),(0,1),(0,0)],
  [(0,0),(1,1),(1,0),(2,1),(1,1),(1,0),(0,0)],
  [(0,0),(1,1),(1,0),(2,1),(2,0),(1,0),(0,0)],
  [(0,0),(1,1),(2,2),(1,2),(0,2),(0,1),(0,0)],
  [(0,0),(1,1),(2,2),(1,2),(1,1),(0,1),(0,0)],
  [(0,0),(1,1),(2,2),(1,2),(1,1),(1,0),(0,0)],
  [(0,0),(1,1),(2,2),(2,1),(1,1),(0,1),(0,0)],
  [(0,0),(1,1),(2,2),(2,1),(1,1),(1,0),(0,0)],
  [(0,0),(1,1),(2,2),(2,1),(2,0),(1,0),(0,0)].

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

Main diagonal of A340591.

Cf. A002378, A034841.

b:= proc(n, l) option remember; `if`(n=0, 1, (k-> add(
     `if`(l[i]>0, b(n-1, sort(subsop(i=l[i]-1, l))), 0), i=1..k)+
     `if`(add(i, i=l)+k x+1, l)), 0))(nops(l)))
    end:
a:= n-> b(n*(n+1), [0$n]):
seq(a(n), n=0..9);

b[n_, l_] := b[n, l] = If[n == 0, 1, Function[k, Sum[
    If[l[[i]]>0, b[n-1, Sort[ReplacePart[l, i -> l[[i]]-1]]], 0], {i, 1, k}] +
    If[Sum[i, {i, l}] + k < n, b[n - 1, Map[#+1&, l]], 0]][Length[l]]];
a[n_] := b[n(n+1), Table[0, {n}]];
a /@ Range[0, 9] (* Jean-François Alcover, Jan 26 2021, after Alois P. Heinz *)

a(n) = A340591(n,n).

A340540 Number of walks of length 4n in the first octant using steps (1,1,1), (-1,0,0), (0,-1,0), and (0,0,-1) that start and end at the origin.

Original entry on oeis.org

1, 6, 288, 24444, 2738592, 361998432, 53414223552, 8525232846072, 1443209364298944, 255769050813120576, 47020653859202576640, 8907614785269428079168, 1730208409741026141405696, 343266632435192859791576064, 69350551439109880798294334208

Offset: 0

Daniel Carter, Jan 10 2021

There are no such walks with length that is not a multiple of 4.
a(n) is also the number of arrangements of n copies each of "a", "b", "c", and "d" such that no prefix has more b's, c's, or d's than a's.
The analogous problem in dimensions 1 and 2 are given respectively by A000108 (the Catalan numbers) and A006335.
No closed form is known. In fact, it is not known whether this sequence is D-finite (see Bacher et al.).

Alois P. Heinz, Table of n, a(n) for n = 0..150
Axel Bacher, Manuel Kauers, and Rika Yatchak, Continued Classification of 3D Lattice Walks in the Positive Octant, arXiv:1511.05763 [math.CO], 2015.

Cf. A000108, A006335, A149424.

Column k=3 of A340591.

b:= proc(n, l) option remember; `if`(n=0, 1, `if`(add(i, i=l)+3 x+1, l)), 0) +add(`if`(l[i]>0,
      b(n-1, sort(subsop(i=l[i]-1, l))), 0), i=1..3))
    end:
a:= n-> b(4*n, [0$3]):
seq(a(n), n=0..15);  # Alois P. Heinz, Jan 12 2021

b[n_, l_] := b[n, l] = If[n == 0, 1, If[Total[l] + 3 < n,
  b[n-1, l+1]], 0] + Sum[If[l[[i]] > 0,
  b[n-1, Sort[ReplacePart[l, i -> l[[i]]-1]]], 0], {i, 1, 3}] /. Null -> 0;
a[n_] := b[4n, {0, 0, 0}];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jul 10 2021, after Alois P. Heinz *)

import itertools as it
i = 0
while 1:
    counts = {(a,b,c):0 for a,b,c in it.product(range(i+1), repeat=3)}
    counts[0,0,0] = 1
    for _ in range(4*i):
        update = {(a,b,c):0 for a,b,c in it.product(range(i+1), repeat=3)}
        for x,y,z in counts:
            if counts[x,y,z] != 0:
                for coord in [(x+1,y+1,z+1), (x-1,y,z), (x,y-1,z), (x,y,z-1)]:
                    if coord in update:
                        update[coord] += counts[x,y,z]
        counts = update
    print(i, counts[0,0,0])
    i += 1

cp's OEIS Frontend

A335570 Number A(n,k) of n-step k-dimensional nonnegative lattice walks starting at the origin and using steps that increment all components or decrement one component by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A006335 a(n) = 4^n*(3*n)!/((n+1)!*(2*n+1)!).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A055546 a(n) = (-1)^(n+1) * 2^n * n!^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A340590 Number of n*(n+1)-step n-dimensional nonnegative closed lattice walks starting at the origin and using steps that increment all components or decrement one component by 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A340540 Number of walks of length 4n in the first octant using steps (1,1,1), (-1,0,0), (0,-1,0), and (0,0,-1) that start and end at the origin.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

A006335 a(n) = 4^n(3n)!/((n+1)!(2n+1)!).