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

Author

Lara Pudwell, Apr 27 2023

Keywords

• nonn
• easy

Examples

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

Links

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

Crossrefs

Cf. A028365, A362596.

Programs

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

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

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