OFFSET
0,3
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1211
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Jun Yan, Results on pattern avoidance in parking functions, arXiv preprint arXiv:2404.07958 [math.CO], 2024. See Theorem 3.4.
FORMULA
Consider a Dyck path of semilength n to be a path from (0,0) to (n,n) consisting of N=(0,1) steps and E=(1,0) steps, staying weakly above y=x and let D(n) be the set of all such paths.
For any Dyck path d, let w(d) be the word of positive integers that records the lengths of the maximal consecutive strings of N-steps in d, let w(d)_i be the i-th entry of w(d), and let |w(d)| be the length of d.
a(n) = Sum_{d in D(n)} Product_{i=1..|w(d)|-1} (w(d)_i+1).
a(n) ~ 23 * 3^(3*n + 3/2) / (25 * sqrt(Pi) * 2^(2*n + 3) * n^(3/2)). - Vaclav Kotesovec, May 02 2023
From Jun Yan, Apr 13 2024: (Start)
a(n) = binomial(3*n + 1, n)/(n + 1) - Sum_{k=0..n-1} binomial(3*n - 3*k + 1, n - k) / (2^(k + 1)*(n - k + 1)).
G.f.: ((1 - x)*A(x) + 1)/(2 - x), where A(x) is the g.f. of A006013. (End)
EXAMPLE
The a(3) = 13 parking functions, given in block notation, are {1},{2},{3}; {1,2},{},{3}; {1,2},{3},{}; {1},{2,3},{}; {1,2,3},{},{}; {1},{3},{2}; {1,3},{},{2}; {1,3},{2},{}; {2},{1},{3}; {2},{1,3},{}; {2},{3},{1}; {2,3},{},{1}; {2,3},{1},{}.
When n = 3 there are 5 Dyck paths:
w(NNNEEE) = [3], contributing 1 to the sum;
w(NNENEE) = [2,1], contributing 2+1 = 3 to the sum;
w(NNEENE) = [2,1], contributing 2+1 = 3 to the sum;
w(NENNEE) = [1,2], contributing 1+1 = 2 to the sum;
w(NENENE) = [1,1,1], contributing (1+1)(1+1) = 4 to the sum.
Therefore, a(3) = 1+3+3+2+4 = 13.
MAPLE
b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
`if`(x=y, 1, b(x-1, y-1, 0)*(t+1)+b(x-1, y+1, t+1)))
end:
a:= n-> b(2*n, 0$2):
seq(a(n), n=0..24); # Alois P. Heinz, May 02 2023
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 1, (2*(667*n^4-1439*n^3+656*n^2
+146*n-96)*a(n-1)-3*(3*n-4)*(3*n-2)*(23*n^2-6*n-5)*a(n-2))/
(4*(2*n+1)*(n+1)*(23*n^2-52*n+24)))
end:
seq(a(n), n=0..24); # Alois P. Heinz, May 02 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
Lara Pudwell, May 01 2023
EXTENSIONS
a(13)-a(24) from Alois P. Heinz, May 02 2023
STATUS
approved