A362595 Number of parking functions of size n avoiding the patterns 132 and 321.

1, 1, 3, 12, 52, 229, 1006, 4387, 18978, 81489, 347614, 1474436, 6223328, 26156242, 109528108, 457167817, 1902808318, 7899987577, 32725812958, 135297527872, 558357811048, 2300564293942, 9465003608548, 38889193275142, 159591154157092, 654190748282074

Offset: 0

Author

Lara Pudwell, Apr 27 2023

Keywords

• nonn
• easy

Examples

			For n=3 the a(3)=12 parking functions, given in block notation, are {1},{2},{3}; {1,2},{},{3}; {1,2},{3},{}; {1},{2,3},{}; {1,2,3},{},{}; {2},{1},{3}; {2},{1,3},{}; {2},{3},{1}; {2,3},{},{1}; {2,3},{1},{}; {3},{1},{2}; {3},{1,2},{}.
		

Links

• Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.

Crossrefs

Cf. A000108, A028364, A362596, A362597.

Programs

Maple

A362595 := proc(n)
    if n = 0 then
        1;
    else
        (n^2+n+4)*A000108(n)/4 -4^(n-1)/2 ;
    end if;
end proc:
seq(A362595(n),n=0..60) ; # R. J. Mathar, Jan 11 2024

PARI

a(n)=if(n==0, 1, (n^2 + n + 4)*binomial(2*n,n)/(4*(n+1)) - 4^n/8) \\ Andrew Howroyd, Apr 27 2023

Python

from math import comb
def A362595(n): return ((n*(n+1)+4)*comb(n<<1,n)//(n+1)>>2)-(1<<(n<<1)-3) if n>1 else 1 # Chai Wah Wu, Apr 27 2023

Formula

For n>=1, a(n) = (n^2 + n + 4)/4*A000108(n) - 4^(n - 1)/2.

For n>=1, a(n) = A000108(n) + Sum_{m=1..n} (n-m)*A028364(n-1,m-1).

G.f.: 1+((7*x^2 - 6*x + 1)*sqrt(1 - 4*x) - 15*x^2 + 8*x - 1)/(2*(1 - 4*x)^(3/2)*x).

D-finite with recurrence (n+1)*a(n) +2*(-8*n+1)*a(n-1) +(95*n-117)*a(n-2) +2*(-124*n+291)*a(n-3) +120*(2*n-7)*a(n-4)=0. - R. J. Mathar, Jan 11 2024