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

%I #16 Jan 11 2024 09:16:10

%S 1,1,3,12,52,229,1006,4387,18978,81489,347614,1474436,6223328,

%T 26156242,109528108,457167817,1902808318,7899987577,32725812958,

%U 135297527872,558357811048,2300564293942,9465003608548,38889193275142,159591154157092,654190748282074

%N Number of parking functions of size n avoiding the patterns 132 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 + n + 4)/4*A000108(n) - 4^(n - 1)/2.

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

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

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

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

%p A362595 := proc(n)

%p if n = 0 then

%p 1;

%p else

%p (n^2+n+4)*A000108(n)/4 -4^(n-1)/2 ;

%p end if;

%p end proc:

%p seq(A362595(n),n=0..60) ; # _R. J. Mathar_, Jan 11 2024

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

%o (Python)

%o from math import comb

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

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

%K nonn,easy

%O 0,3

%A _Lara Pudwell_, Apr 27 2023