A362744 - OEIS

%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