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

Author

Per W. Alexandersson, Feb 10 2020

Keywords

• nonn
• tabl

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.

Examples

			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.
		

Links

• 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).

Crossrefs

A194460 is the diagonal.

Programs

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}]

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).