login
Number of parking functions of size n avoiding the pattern 123.
2

%I #33 Jan 11 2024 09:20:00

%S 1,1,3,11,48,232,1207,6631,37998,225182,1371560,8546760,54294880,

%T 350658336,2297296991,15239785151,102218278626,692361482818,

%U 4730891905450,32581995322522,226000929559056,1577824515023456,11080975421752488,78244477268207656

%N Number of parking functions of size n avoiding the pattern 123.

%H Seiichi Manyama, <a href="/A362741/b362741.txt">Table of n, a(n) for n = 0..1000</a>

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

%H Dun Qiu, <a href="https://mathweb.ucsd.edu/~duqiu/files/PP16.pdf">Patterns in Ordered Set Partitions and Parking Functions</a>.

%F a(n) = Sum_{k=ceiling(n/2)..n} A000108(k)*binomial(n,k)*binomial(k,n-k)/(n-k+1).

%F a(n) mod 2 = 1 <=> n in { A075427 } U {0}. - _Alois P. Heinz_, May 01 2023

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

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

%p a:= proc(n) option remember; `if`(n<2, 1, (8*(3*n+4)*(n-1)^2*

%p a(n-2)+(21*n^3+25*n^2-2*n-8)*a(n-1))/((3*n+1)*(n+2)^2))

%p end:

%p seq(a(n), n=0..24); # _Alois P. Heinz_, May 01 2023

%Y Cf. A000108, A075427, A362595, A362596, A362597, A362744.

%K nonn,easy

%O 0,3

%A _Lara Pudwell_, May 01 2023