A368164 Number of nondeterministic Dyck bridges of length 2*n.

1, 7, 63, 583, 5407, 50007, 460815, 4231815, 38745279, 353832631, 3224323183, 29328492519, 266364307231, 2416023142423, 21890268365007, 198151683934023, 1792260214473087, 16199857938091383, 146342491104098607, 1321339563995562663, 11925412051760977887, 107590261672922633943

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-bridge if it contains at least one trajectory that is a classical bridge, i.e., 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-6*t)/(sqrt(1-8*t)*(1-9*t)).

From Joseph M. Shunia, May 09 2024: (Start)

a(n) = A089022(n) + Sum_{k=0..n-1} binomial(2*n, k)*2^(2*n-k).

a(n) = A000244(2*n) - Sum_{k=n+1..2*n} binomial(2*n, k)*2^(2*n-k+1). (End)

Example

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

Crossrefs

Cf. A151281 (nondeterministic Dyck meanders), A368234 (nondeterministic Dyck excursions), A000244 (nondeterministic Dyck walks).

Sequence in context: A155132 A270472 A266426 * A345078 A233743 A015684

Adjacent sequences: A368161 A368162 A368163 * A368165 A368166 A368167

Keyword

nonn

Author

Michael Wallner, Dec 14 2023

Status

approved