A332389 Number A(n,w) of circular Dyck paths with n entries, and width at most w.

1, 1, 2, 1, 4, 3, 1, 8, 7, 4, 1, 16, 18, 10, 5, 1, 32, 47, 28, 13, 6, 1, 64, 123, 82, 38, 16, 7, 1, 128, 322, 244, 117, 48, 19, 8, 1, 256, 843, 730, 370, 152, 58, 22, 9, 1, 512, 2207, 2188, 1186, 496, 187, 68, 25, 10, 1, 1024, 5778, 6562, 3827, 1648, 622, 222, 78, 28, 11

Offset

1,3

Comments

A(n,w) is the number of circular Dyck paths of size n, and width at most w.

This is also the number of circular area lists, a_1, a_2, ..., a_n such that 0 <= a_i <= w-1, and a_{i+1} < a_i + 1, for all 1 <= i <= n, and the index i is taken modulo n.

The values of w are given by the row index.

A(n,w) is given by summing binomial(2*n - 1, n - 1 - (w+2) k) - binomial(2*n - 1, n + j + (w+2)*k) over k=1..w and k over all integers.

Links

Table of n, a(n) for n=1..66.

Per Alexandersson, Svante Linusson and Samu Potka, The cyclic sieving phenomenon on circular Dyck paths, arXiv:1903.01327 [math.CO], 2019.

Per Alexandersson, Svante Linusson and Samu Potka, The cyclic sieving phenomenon on circular Dyck paths, Electronic Journal of Combinatorics 26, No.4 (2019).

Formula

A(n,w) = Sum_{k=-2*(n+2)..2*(n+2)} Sum_{j=1..w} binomial(2n-1, n-1-(w+2)*k) - binomial(2*n-1, n + j + (w+2)*k).

Example

The table begins as
1,    2,    3,    4,    5, ...
1,    4,    7,    10,   13, ...
1,    8,    18,   28,   38, ...
1,    16,   47,   82,   117, ...
1,    32,   123,  244,  370, ...
...
A(5,3)=123 and a few of the corresponding circular area lists are 00000, 10000,...,12210,...,12222, 22222.

Mathematica

CircularDyckPaths[n_, w_] := With[{d = w + 2},
   Sum[Binomial[2 n - 1, n - 1 - d s] -
     Binomial[2 n - 1, n + j + d s]
    , {j, w},
    {s, -2 (n + 2), 2 (n + 2)}]
   ];
Table[
CircularDyckPaths[n, w]
, {n, 1, 10}, {w, 1, 10}]

Crossrefs

A194460 is the diagonal.

Sequence in context: A276562 A055248 A103316 * A140069 A105851 A106195

Adjacent sequences: A332386 A332387 A332388 * A332390 A332391 A332392

Keyword

nonn,tabl

Author

Per W. Alexandersson, Feb 10 2020

Status

approved