|
%I #32 Apr 13 2024 09:15:55
%S 1,1,3,13,63,324,1736,9589,54223,312369,1826847,10818156,64737684,
%T 390877456,2378312780,14568360645,89766137967,556008951667,
%U 3459976045201,21621154097573,135619427912599,853590782088272,5389272616262656,34123058549079788,216621704634708868
%N Number of parking functions of size n avoiding the patterns 312 and 321.
%H Alois P. Heinz, <a href="/A362744/b362744.txt">Table of n, a(n) for n = 0..1211</a>
%H Ayomikun Adeniran and Lara Pudwell, <a href="https://doi.org/10.54550/ECA2023V3S3R17">Pattern avoidance in parking functions</a>, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
%H Jun Yan, <a href="http://arxiv.org/2404.07958">Results on pattern avoidance in parking functions</a>, arXiv preprint arXiv:2404.07958 [math.CO], 2024. See Theorem 3.4.
%F 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.
%F 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.
%F a(n) = Sum_{d in D(n)} Product_{i=1..|w(d)|-1} (w(d)_i+1).
%F a(n) ~ 23 * 3^(3*n + 3/2) / (25 * sqrt(Pi) * 2^(2*n + 3) * n^(3/2)). - _Vaclav Kotesovec_, May 02 2023
%F From _Jun Yan_, Apr 13 2024: (Start)
%F 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)).
%F G.f.: ((1 - x)*A(x) + 1)/(2 - x), where A(x) is the g.f. of A006013. (End)
%e 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},{}.
%e When n = 3 there are 5 Dyck paths:
%e w(NNNEEE) = [3], contributing 1 to the sum;
%e w(NNENEE) = [2,1], contributing 2+1 = 3 to the sum;
%e w(NNEENE) = [2,1], contributing 2+1 = 3 to the sum;
%e w(NENNEE) = [1,2], contributing 1+1 = 2 to the sum;
%e w(NENENE) = [1,1,1], contributing (1+1)(1+1) = 4 to the sum.
%e Therefore, a(3) = 1+3+3+2+4 = 13.
%p b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
%p `if`(x=y, 1, b(x-1, y-1, 0)*(t+1)+b(x-1, y+1, t+1)))
%p end:
%p a:= n-> b(2*n, 0$2):
%p seq(a(n), n=0..24); # _Alois P. Heinz_, May 02 2023
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<2, 1, (2*(667*n^4-1439*n^3+656*n^2
%p +146*n-96)*a(n-1)-3*(3*n-4)*(3*n-2)*(23*n^2-6*n-5)*a(n-2))/
%p (4*(2*n+1)*(n+1)*(23*n^2-52*n+24)))
%p end:
%p seq(a(n), n=0..24); # _Alois P. Heinz_, May 02 2023
%Y Cf. A000108, A006013, A362595, A362596, A362597, A362741.
%K nonn
%O 0,3
%A _Lara Pudwell_, May 01 2023
%E a(13)-a(24) from _Alois P. Heinz_, May 02 2023
|
