Search for: All records

Classical parking functions are defined as the parking preferences for $$n$$ cars driving (from west to east) down a one-way street containing parking spaces labeled from $$1$$ to $$n$$ (from west to east). Cars drive down the street toward their preferred spot and park there if the spot is available. Otherwise, the car continues driving down the street and takes the first available parking space, if such a space exists. If all cars can park using this parking rule, we call the $$n$$-tuple containing the cars' parking preferences a parking function.   In this paper, we introduce a generalization of the parking rule allowing cars whose preferred space is taken to first proceed up to $$k$$ spaces west of their preferred spot to park before proceeding east if all of those $$k$$ spaces are occupied. We call parking preferences which allow all cars to park under this new parking rule $$k$$-Naples parking functions of length $$n$$. This generalization gives a natural interpolation between classical parking functions, the case when $k=0$, and all $$n$$-tuples of positive integers $$1$$ to $$n$$, the case when $$k\geq n-1$$. Our main result provides a recursive formula for counting $$k$$-Naples parking functions of length $$n$$. We also give a characterization for the $k=1$ case by introducing a new function that maps $$1$$-Naples parking functions to classical parking functions, i.e. $$0$$-Naples parking functions. Lastly, we present a bijection between $$k$$-Naples parking functions of length $$n$$ whose entries are in weakly decreasing order and a family of signature Dyck paths. 

Until recently, the only known method of finding the roots of polynomials over prime power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm, obstructing the use of greatest common divisors. Fix a prime integer p and f in (Z/pnZ)[x] any nonzero polynomial of degree d whose coefficients are not all divisible by p. For the case n=2, we prove a new efficient algorithm to count the roots of f in Z/p2Z within time (d+size(f)+log p),2+o(1), based on a formula conjectured by Cheng, Gao, Rojas, and Wan.