A362596 Number of parking functions of size n avoiding the patterns 213 and 321.

1, 1, 3, 13, 60, 275, 1238, 5480, 23922, 103267, 441798, 1876366, 7921488, 33275758, 139194812, 580180598, 2410827422, 9990993443, 41308185542, 170439003998, 701953309592, 2886284314298, 11850433719572, 48591008205608, 199002198798980, 814117064956430

Offset: 0

Author

Lara Pudwell, Apr 27 2023

Keywords

• nonn
• easy

Examples

			For n=3 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},{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, A028365, A362597.

Programs

PARI

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

Python

from math import comb
def A362596(n): return ((n*(n-3)+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 - 3*n + 4)/4*A000108(n) + 4^(n - 1)/2.

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

G.f.: 1+((9*x^2 - 10*x + 2)*sqrt(1 - 4*x) - 23*x^2 + 14*x - 2)/(2*(1 - 4*x)^(3/2)*x).

D-finite with recurrence 2*(n+1)*a(n) +2*(-15*n+1)*a(n-1) +(167*n-193)*a(n-2) +2*(-204*n+467)*a(n-3) +184*(2*n-7)*a(n-4)=0. - R. J. Mathar, Jan 11 2024