A362744 Number of parking functions of size n avoiding the patterns 312 and 321.
1, 1, 3, 13, 63, 324, 1736, 9589, 54223, 312369, 1826847, 10818156, 64737684, 390877456, 2378312780, 14568360645, 89766137967, 556008951667, 3459976045201, 21621154097573, 135619427912599, 853590782088272, 5389272616262656, 34123058549079788, 216621704634708868
Offset: 0
Keywords
Examples
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.
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.
Programs
-
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
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)
Extensions
a(13)-a(24) from Alois P. Heinz, May 02 2023