cp's OEIS Frontend

A362744 Number of parking functions of size n avoiding the patterns 312 and 321.

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