OFFSET
3,1
COMMENTS
This sequence enumerates parking functions with lucky third spot (where a lucky spot is one which is parked in by a car which prefers that spot).
FORMULA
a(n) = (2/3)*(n+1)^(n-1) - (1/3)*(2*n-1)*(n-2)^(n-2).
EXAMPLE
For clarity, we write parentheses around parking functions. For n = 3, the a(3) = 9 solutions are the parking functions of length 3 with a lucky third spot: (1,1,3),(1,2,3),(1,3,1),(1,3,2),(2,1,3),(2,3,1),(3,1,1),(3,1,2),(3,2,1). There are 7 parking functions of length 3 which do not have a lucky third spot: (1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1). For all of these, the car which parks in the third spot did not prefer the third spot; these parking functions do not contribute to our count.
MATHEMATICA
a[n_]:=(2/3)*(n+1)^(n-1)-(1/3)*(2n-1)*(n-2)^(n-2); Array[a, 18, 3] (* Stefano Spezia, Jun 26 2024 *)
PROG
(Python)
def A372843(n): return (((n+1)**(n-1)<<1)-((n<<1)-1)*(n-2)**(n-2))//3 # Chai Wah Wu, Jun 26 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Kimberly P. Hadaway, Jun 26 2024
STATUS
approved