A362741 Number of parking functions of size n avoiding the pattern 123.
1, 1, 3, 11, 48, 232, 1207, 6631, 37998, 225182, 1371560, 8546760, 54294880, 350658336, 2297296991, 15239785151, 102218278626, 692361482818, 4730891905450, 32581995322522, 226000929559056, 1577824515023456, 11080975421752488, 78244477268207656
Offset: 0
Examples
For n=3 the a(3)=11 parking functions, given in block notation, are {1},{3},{2}; {1,3},{},{2}; {1,3},{2},{}; {2},{1},{3}; {2},{1,3},{}; {2},{3},{1}; {2,3},{},{1}; {2,3},{1},{}; {3},{1},{2}; {3},{1,2},{}; {3},{2},{1}.
Links
- Seiichi Manyama, Table of n, a(n) for n = 0..1000
- Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
- Dun Qiu, Patterns in Ordered Set Partitions and Parking Functions.
Programs
-
Maple
a:= proc(n) option remember; `if`(n<2, 1, (8*(3*n+4)*(n-1)^2* a(n-2)+(21*n^3+25*n^2-2*n-8)*a(n-1))/((3*n+1)*(n+2)^2)) end: seq(a(n), n=0..24); # Alois P. Heinz, May 01 2023
Formula
a(n) = Sum_{k=ceiling(n/2)..n} A000108(k)*binomial(n,k)*binomial(k,n-k)/(n-k+1).
a(n) mod 2 = 1 <=> n in { A075427 } U {0}. - Alois P. Heinz, May 01 2023
D-finite with recurrence (n+2)^2*a(n) -n*(3*n+2)*a(n-1) +4*(-9*n^2+17*n-6)*a(n-2) -32*(n-2)^2*a(n-3)=0. - R. J. Mathar, Jan 11 2024