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,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

Cf. A000108, A006013, A362595, A362596, A362597, A362741.

Sequence in context: A026715 A001850 A130525 * A350519 A243280 A000259

Adjacent sequences: A362741 A362742 A362743 * A362745 A362746 A362747

Keyword

nonn

Author

Lara Pudwell, May 01 2023

Extensions

a(13)-a(24) from Alois P. Heinz, May 02 2023

Status

approved