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

%I #20 Jan 11 2024 09:10:04

%S 1,1,3,13,60,275,1238,5480,23922,103267,441798,1876366,7921488,

%T 33275758,139194812,580180598,2410827422,9990993443,41308185542,

%U 170439003998,701953309592,2886284314298,11850433719572,48591008205608,199002198798980,814117064956430

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

%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.

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

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

%F 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).

%F 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

%e 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},{}.

%o (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

%o (Python)

%o from math import comb

%o 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

%Y Cf. A000108, A028364, A028365, A362597.

%K nonn,easy

%O 0,3

%A _Lara Pudwell_, Apr 27 2023