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
É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
KEYWORD
nonn
AUTHOR
Michael Wallner, Dec 14 2023
STATUS
approved