A362597 Number of parking functions of size n avoiding the patterns 213 and 312.

1, 1, 3, 12, 54, 259, 1293, 6634, 34716, 184389, 990711, 5372088, 29347794, 161317671, 891313569, 4946324886, 27552980088, 153982124809, 862997075691, 4848839608228, 27304369787694, 154059320699211, 870796075968693, 4929937918315522, 27950989413184404

Offset

0,3

Links

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

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

Formula

For n>=1, a(n) = Sum_{k=0..n-1} Sum_{i=0..k} binomial(n - 1, i)*(k + 1)*binomial(2*n - 2 - k, n - 1 - k)/n.

D-finite with recurrence (n+1)*a(n) +3*(-4*n+1)*a(n-1) +(34*n-45)*a(n-2) +3*(4*n-17)*a(n-3) +3*(-n+4)*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},{},{}; {1},{3},{2}; {1,3},{},{2}; {1,3},{2},{}; {2},{3},{1}; {2,3},{},{1}; {2,3},{1},{}; {3},{2},{1}.

Maple

A362597 := proc(n)
    if n = 0 then
        1;
    else
        add(add(binomial(n - 1, i)*(k + 1)*binomial(2*n - 2 - k, n - 1 - k)/n, i=0..k), k=0..n-1) ;
    end if;
end proc:
seq(A362597(n), n=0..60) ; # R. J. Mathar, Jan 11 2024

Prog

(PARI) a(n)={0^n + sum(k=0, n-1, sum(i=0, k, binomial(n - 1, i)*(k + 1)*binomial(2*n - 2 - k, n - 1 - k)/n))} \\ Andrew Howroyd, Apr 27 2023

Crossrefs

Cf. A028365, A362596.

Sequence in context: A151208 A055835 A366118 * A125188 A054666 A006026

Adjacent sequences: A362594 A362595 A362596 * A362598 A362599 A362600

Keyword

nonn,easy

Author

Lara Pudwell, Apr 27 2023

Status

approved