A368234 Number of nondeterministic Dyck excursions of length 2*n.

1, 4, 28, 224, 1888, 16320, 143040, 1264128, 11230720, 100124672, 894785536, 8010072064, 71794294784, 644079468544, 5782109208576, 51934915067904, 466666751655936, 4194593964294144, 37711993926844416, 339119962067042304, 3049961818869989376, 27434013235435536384

Offset

0,2

Comments

In nondeterministic walks (N-walks) the steps are sets and called N-steps. N-walks start at 0 and are concatenations of such N-steps such that all possible extensions are explored in parallel. The nondeterministic Dyck step set is { {-1}, {1}, {-1,1} }. Such an N-walk is called an N-excursion if it contains at least one trajectory that is a classical excursion, i.e., never crosses the x-axis, and starts and ends at 0 (for more details see the de Panafieu-Wallner article).

Links

Table of n, a(n) for n=0..21.

Élie de Panafieu and Michael Wallner, Combinatorics of nondeterministic walks, arXiv:2311.03234 [math.CO], 2023.

Formula

G.f.: (1-8*x-(1-12*x)*sqrt(1-8*x))/(8*x*(1-9*x)).

Example

The a(1)=4 N-bridges of length 2 are
      /         /
/\,  /\,  /\,  /\
          \    \/
           \    \

Crossrefs

Cf. A151281 (Nondeterministic Dyck meanders), A368164 (Nondeterministic Dyck bridges), A000244 (Nondeterministic Dyck walks).

Sequence in context: A005810 A371755 A121203 * A192620 A180708 A370187

Adjacent sequences: A368231 A368232 A368233 * A368235 A368236 A368237

Keyword

nonn

Author

Michael Wallner, Dec 18 2023

Status

approved