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

%I #7 Dec 18 2023 08:32:06

%S 1,4,28,224,1888,16320,143040,1264128,11230720,100124672,894785536,

%T 8010072064,71794294784,644079468544,5782109208576,51934915067904,

%U 466666751655936,4194593964294144,37711993926844416,339119962067042304,3049961818869989376,27434013235435536384

%N Number of nondeterministic Dyck excursions of length 2*n.

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

%H Élie de Panafieu and Michael Wallner, <a href="https://arxiv.org/abs/2311.03234">Combinatorics of nondeterministic walks</a>, arXiv:2311.03234 [math.CO], 2023.

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

%e The a(1)=4 N-bridges of length 2 are

%e / /

%e /\, /\, /\, /\

%e \ \/

%e \ \

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

%K nonn

%O 0,2

%A _Michael Wallner_, Dec 18 2023