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

Links

Table of n, a(n) for n=0..25.

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

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

Example

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

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

Prog

(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

Crossrefs

Cf. A000108, A028364, A362596, A362597.

Sequence in context: A224914 A227810 A368971 * A125187 A151190 A151191

Adjacent sequences: A362592 A362593 A362594 * A362596 A362597 A362598

Keyword

nonn,easy

Author

Lara Pudwell, Apr 27 2023

Status

approved