\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Subset Parking Functions
}
\vskip 1cm
\large
Sam Spiro\\
Department of Mathematics\\
University of California, San Diego\\
9500 Gilman Dr. \\
La Jolla, CA 92093\\
USA\\
\href{mailto:sspiro@ucsd.edu}{\tt sspiro@ucsd.edu}
\end{center}
\vskip .2 in
\renewcommand{\l}{\left}
\renewcommand{\r}{\right}
\newcommand{\sm}{\setminus}
\newcommand{\sub}{\subseteq}
\newcommand{\asc}{\mr{asc}}
\def\inv{\mr{inv}}
\newcommand{\Eul}{\genfrac{\langle}{\rangle}{0pt}{}}
\renewcommand{\c}[1]{\mathcal{#1}}
\newcommand{\mr}[1]{\mathrm{#1}}
\newcommand{\SP}{\mr{SPF}}
\newcommand{\kSP}{\SP_k}
\newcommand{\OPF}{\mr{OPF}}
\newcommand{\IPF}{\mr{IPF}}
\newcommand{\PF}{\mr{PF}}
\begin{abstract}
A parking function $(c_1,\ldots,c_n)$ can be viewed as having $n$ cars trying to park on a one-way street with $n$ parking spots from left to right, where car $i$ tries to park in spot $c_i$, and otherwise it parks in the leftmost available spot after $c_i$. Another way to view this is that each car has a set $C_i$ of ``acceptable'' parking spots, namely $C_i=[c_i,n]$, and that each car tries to park in the leftmost available spot that it finds acceptable.
Motivated by this, we define a subset parking function $(C_1,\ldots,C_n)$, with each $C_i$ a subset of $\{1,\ldots,n\}$, by having the $i$th car try to park in the leftmost available element of $C_i$. We further generalize this idea by restricting our sets to be of size $k$, intervals, and intervals of length $k$. In each of these cases we provide formulas for the number of such parking functions.
\end{abstract}
\section{Introduction}
Parking functions are well-studied objects in combinatorics, and are often defined in the following way. Imagine that there are $n$ parking spots labeled 1 though $n$ on a one way street. There are $n$ cars, also labeled 1 through $n$, that wish to park in these spots, and each has a preferred parking spot $c_i$. When it is car $i$'s turn to park, it goes to its preferred spot $c_i$ and parks there if it is empty. Otherwise, it tries to park in the next available spot that is after $c_i$. The tuple $(c_1,\ldots,c_n)$ is said to be a parking function if every car succeeds in parking.
For example, $(2,2,2)$ is not a parking function, as car 1 parks in slot 2; car 2 tries to park in slot 2 but can not and goes to the next available slot 3; and car 3 tries to park in slot 2 but can not, and there are no slots after this that are available. On the other hand, $(2,1,1)$ is a parking function as car 1 parks in slot 2; car 2 parks in slot 1; and car 3 tries to park in slot 1 but can not, so it goes to the next available slot 3. We will say that the parking function $(2,1,1)$ has outcome $213$, which describes how one would see the cars parked if one were to walk from slot 1 to slot $3$.
Parking functions have many interesting combinatorial properties. For example, a necessary and sufficient condition for $(c_1,\ldots,c_n)$ to be a parking function is, after rearranging the $c_i$ in increasing order as $b_1\le b_2\le \cdots\le b_n$, we have $b_i\le i$ for all $i$. In particular, this shows that any permutations of the entries of a parking function is also a parking function. One can also prove that the number of parking functions $\PF(n)$ satisfies \begin{equation}\label{E-Park}
\PF(n)=(n+1)^{n-1}.
\end{equation}
Parking functions have connections to many other areas of combinatorics, such as hyperplane arrangements \cite{Stan79} and the lattice of non-crossing partitions \cite{Stan80}. We refer the reader to the survey of Yan \cite{CY} for an elegant proof of \eqref{E-Park} and a more in depth study of parking functions.
Many generalizations and variants of parking functions have been studied, such as $\mathbf{x}$-parking functions \cite{Yx} and $G$-parking functions \cite{PS}. These examples generalize the $b_i\le i$ characterization of parking functions. One can also generalize the parking analogy. An example of this is to allow cars to park a few spaces before their preferred spot if this is already taken, which has been studied recently \cite{Naples}.
In this paper we also consider a variant of parking function that is obtained by modifying the parking rule. To motivate the idea, we observe that a parking function $(c_1,\ldots,c_n)$ can be viewed as each car choosing a set $C_i=[c_i,n]$ of ``acceptable'' parking spaces, with each car parking in the leftmost available spot which is acceptable to them. One can generalize this idea by allowing each $C_i$ to be an arbitrary set.
To this end, let $[n]:=\{1,2,\ldots,n\}$ and let $\c{S}_n$ denote the set of permutations of size $n$ written in one line notation. Given $n$ non-empty subsets $C_i\sub [n]$ and a permutation $\pi\in \c{S}_n$, we will say that $\c{C}=(C_1,\ldots,C_n)$ is a subset parking function with outcome $\pi$ if for all $1\le i\le n$, having $\pi_j=i$ implies $j$ is the smallest element of $C_i\sm\{\pi_{i'}^{-1}:i'*0$.
\begin{theorem}\label{T-k}
For any integer $n\ge 1$, $\pi\in \c{S}_n$, and $1\le k\le n$,
\[\kSP(n,\pi)=\prod_{i=1}^{n} {n-\inv_{i}(\pi)-1\choose k-1},\]
\[\kSP(n)=\prod_{i=0}^{n-1}\l({n\choose k}-{i\choose k}\r).\]
\end{theorem}
We next consider the case that each $C_i$ is an interval, and we call such parking functions interval parking functions. Let $\IPF(n)$ and $\IPF(n,\pi)$ be the total number of interval parking functions and the number of interval parking functions with outcome $\pi$, respectively.
To state our full result, given a permutation $\pi$ we define $a_i(\pi)$ to be the largest $j$ with $1\le j\le i$ such that $\pi_i\ge \{\pi_{i},\pi_{i-1},\ldots,\pi_{i-j+1}\}$. For example, $a_i(\pi)\ge 2$ if and only if $\pi_i>\pi_{i-1}$. As another example, for $\pi=31524$, we have $a_i(\pi)$ equal to 1, 1, 3, 1, 2 as $i$ ranges from 1 to 5. Finally, define $\PF(n,\pi)$ to be the number of (classical) parking functions with outcome $\pi$.
\begin{theorem}\label{T-I}
For any $n\ge 1$ and $\pi\in \c{S}_n$,
\[\IPF(n,\pi)=n!\cdot \PF(n,\pi)=n! \prod_{i=1}^n a_i(\pi),\]
\[\IPF(n)=n!\cdot \PF(n)=n!\cdot (n+1)^{n-1}.\]
\end{theorem}
Other properties of interval parking functions are currently being investigated by Christensen, DeMuse, Martin, and Yin \cite{CDM}.
The last variant we consider are $k$-interval parking functions, which are interval parking functions where each $C_i$ is an interval containing $k$ elements. We let $\IPF_k(n)$ denote the number of $k$-interval parking functions and $\IPF_k(n,\pi)$ the number of those with outcome $\pi$. Define $\c{S}_n^k$ to be the set of permutations $\pi$ of order $n$ with $\pi_n>\pi_{n-1}>\cdots >\pi_{n-k+1}$.
\begin{theorem}\label{T-kI}
Let $k$ and $n$ be integers with $1\le k\le n$ and let $\pi\in \c{S}_n$. If $\pi\notin \c{S}_n^{k}$, then $\IPF_k(n,\pi)=0$. Otherwise,\[\IPF_k(n,\pi)=\prod_{i=1}^{n-k} \min\{a_i(\pi),k\}\cdot \prod_{i=n-k+1}^{n}\min\{n-i-k+a_{i}(\pi)+1,n-i+1\}.\]
\end{theorem}
This formula is rather complicated, but for certain $k$ it is manageable. For example, when $k=1$ each term in the product is 1. We conclude that $\IPF_1(n,\pi)=1$ for all $\pi$, and hence $\IPF_1(n)=n!$. When $k=n$, we have $\IPF_n(n,\pi)=1$ when $\pi=12\cdots n$ (since in general $a_1(\pi)=1$ and $a_{n-i}(\pi)\le n-i$), and otherwise $\IPF_n(n,\pi)=0$, so $\IPF_n(n)=1$. Both of these results can also be verified directly. The formulas for $k=n-1$ and $k=2$ are also quite nice.
\begin{corollary}\label{C-n-1}
If $n\ge 2$ and $\pi\in S^{n-1}_n$ with $\pi_1=j$, then
\[\IPF_{n-1}(n,\pi)=\begin{cases}
2^{n-j-1}, & \text{if } j\ne n;\\
1, & \text{if } j=n.
\end{cases}\]
Moreover, \[\IPF_{n-1}(n)=2^{n-1}.\]
\end{corollary}
To state the formula for $k=2$, we define the ascent number $\asc(\pi)$ of a permutation $\pi$ to be the number of $i$ with $2\le i\le n$ and $\pi_{i-1}<\pi_i$. Define the Eulerian number $\Eul{n}{k}$ to be the number of permutations $\pi\in \c{S}_n$ with $\asc(\pi)=k$.
\begin{corollary}\label{C-2}
If $n\ge 2$ and $\pi\in S^2_n$, then \[\IPF_2(n,\pi)=2^{\asc(\pi)-1}.\]
Moreover,
\[\IPF_2(n)=\sum_{k=1}^{n-1} (n-k)\Eul{n-1}{k-1}2^{k-1}.\]
\end{corollary}
\section{Subset results}\label{S-Sub}
We first prove enumeration results for a generalization of subset parking functions where each car is given a list of allowed subset sizes. To this end, given $\c{L}=(L_1,\ldots,L_n)$ with $L_i\sub [n]$, we define $\SP(n,\c{L})$ to be the number of subset parking functions where $|C_i|\in L_i$, and we will call this an $\c{L}$-parking function. Our first goal will be to enumerate $\SP(n,\c{L})$.
To do this, we define the notion of a partial parking function, which intuitively describes where the first $m$ cars have parked. Let $\c{S}_{m,n}$ denote the set of strings $\pi=\pi_1\cdots \pi_n$ where for all $1\le i\le m$ there exists a unique index $j$ with $\pi_j=i$ and such that every other letter is an auxillary letter $*$. Note that $\c{S}_{n,n}$ is simply the set of permutations. For $i\le m$ we let $\pi_i^{-1}$ denote the unique index $j$ with $\pi_j=i$.
We say that $(C_1,\ldots,C_m)$ with each $C_i$ a non-empty subset of $[n]$ is a partial $\c{L}$-parking function with outcome $\pi\in \c{S}_{m,n}$ if for all $1\le i\le m$, $|C_i|\in L_i$ and $\pi_i^{-1}=j$ implies $j$ is the smallest element of $C_i\sm\{\pi_{i'}^{-1}:i'**\cdots>\pi_{n-k+1}$. Observe that $k$-interval parking functions are exactly $\c{K}$-interval parking functions with $K_i=\{k\}$ for all $i$, so a formula for $\IPF_k(n,\pi)$ is given by Theorem~\ref{T-TechI}. It remains to rewrite this formula into the desired form.
If $\pi\notin \c{S}_n^k$, then there exists some $i$ with $0\le i\le k-2$ and $\pi_{n-i}<\pi_{n-i-1}$. This implies $a_{n-i}(\pi)=11$ we have $a_i(\pi)=i$ if $\pi_i>j$ and $a_i(\pi)=i-1$ otherwise. Thus $j=n$ implies that $a_i(\pi)=i-1$ for all $i\ge 2$, and otherwise there are exactly $n-1-j$ different $i$ with $2\le i\le n-1$ and $a_i(\pi)=i$. We conclude the first result. For the second result,
\[
\IPF_{n-1}(n)=\sum_{\pi \in \c{S}_n^{n-1}} \IPF_{n-1}(n,\pi)=1+\sum_{j=1}^{n-1} 2^{n-j-1}=2^{n-1}.
\]
\end{proof}
In principle this same technique can be used to compute $\IPF_{n-k}(n,\pi)$ and $\IPF_{n-k}(n)$ for any fixed $k$, though the case analysis and computations become rather complicated. We note that one can prove $\IPF_{n-1}(n)=2^{n-1}$ more directly by observing that $(C_1,\ldots,C_n)$ will be an $(n-1)$-interval parking function if and only if $C_n=[2,n]$ and $C_i$ is $[1,n-1]$ or $[2,n]$ for all other $i$.
Before proving Corollary~\ref{C-2}, we give an enumeration result for permutations in $\c{S}_n^2$ with a given number of ascents. We adopt the convention $\Eul{0}{k}=0$ for $k>0$, $\Eul{0}{0}=1$, and $\Eul{n}{-1}=0$.
\begin{lemma}\label{L-Count}
For all $n$ and $k$ with $n\ge 1$ and $0\le k\le n-1$, let $\c{S}_{n,k}^+$ be the set of permutations of size $n$ which have $\pi_{n-1}<\pi_n$ and which have exactly $k$ ascents. If $P(n,k):=|\c{S}_{n,k}^+|$, then \[P(n,k)=(n-k)\Eul{n-1}{k-1}.\]
\end{lemma}
We note that this result is implicitly proven in \cite{S}, but for completeness we include the full proof here. To prove this, we recall the following recurrence for Eulerian numbers, which is valid for all $n,k\ge 1$ \cite{Con}.
\begin{align}\label{E-Eulerian}
\Eul{n}{k}=(k+1)\Eul{n-1}{k}+(n-k)\Eul{n-1}{k-1}.
\end{align}
\begin{proof}
The result is true for $k=0$, so assume that we have proven the result up to $k\ge 1$. For any fixed $k$ the result is true for $n=1$, so assume the result has been proven up to $n\ge 2$.
To help us prove the result, we define $\c{S}_{n,k}^-$ to be the set of permutations which have $\pi_{n-1}>\pi_n$ and which have exactly $k$ ascents. Define $M(n,k):=|\c{S}_{n,k}^-|$. By construction we have
\begin{equation}\label{E-MP}
P(n,k)+M(n,k)=\Eul{n}{k}.
\end{equation}
Define the map $\phi:\c{S}_{n,k}^+\to \c{S}_{n-1}$ by sending $\pi \in \c{S}_{n,k}^+$ to the word obtained by removing the letter $1$ from $\pi$ and then decreasing the value of each letter by 1. For example, $\phi(32514)=2143$. We wish to determine the image of $\phi$. Let $\pi$ be a permutation in $\c{S}_{n,k}^+$, and let $i$ denote the position of $1$ in $\pi$. Note that $i\ne n$ since $\pi$ ends with an ascent. If $\pi_{i-1}<\pi_{i+1}$ with $1**\pi_{i+1}$ with $1**\pi_n$, then $\phi(\pi)\in \c{S}_{n-1,k-1}^-$.
It remains to show how many times each element of the image is mapped to by $\phi$. If $\pi\in \c{S}_{n-1,k}^+$, then $1$ can be inserted into $\pi$ in $k$ ways to obtain an element of $\c{S}_{n,k}^+$ (it can be placed between any of the $k$ ascents $\pi_i<\pi_{i+1}$). If $\pi\in \c{S}_{n-1,k-1}^+$, then 1 can be inserted into $\pi$ in $n-k$ ways (it can be placed at the beginning of $\pi$ or between any of the $n-1-k$ descents $\pi_i>\pi_{i+1}$). If $\pi\in \c{S}_{n-1,k}^-$, then $1$ must be inserted in between $\pi_{n-1}>\pi_n$ in order to have the word end with an ascent. With this and the inductive hypothesis, we conclude that
\begin{align}
P(n,k)&=kP(n-1,k)+(n-k)P(n-1,k-1)+M(n-1,k-1)\nonumber\\
&=k(n-k-1)\Eul{n-2}{k-1}+(n-k)^2\Eul{n-2}{k-2}+M(n-1,k-1).\label{E-AEul}
\end{align}
By using \eqref{E-MP}, the inductive hypothesis, and \eqref{E-Eulerian}; we find \begin{align*}M(n-1,k-1)&=\Eul{n-1}{k-1}-P(n-1,k-1)\\ &=\Eul{n-1}{k-1}-(n-k)\Eul{n-2}{k-2}\ \\ &=k\Eul{n-2}{k-1}.\end{align*}
Plugging this into \eqref{E-AEul} and using \eqref{E-Eulerian} gives \[P(n,k)=(n-k)\l(k\Eul{n-2}{k-1}+(n-k)\Eul{n-2}{k-2}\r)=(n-k)\Eul{n-1}{k-1},\]
as desired.
\end{proof}
\begin{proof}[Proof of Corollary~\ref{C-2}]
By Theorem~\ref{T-k} we have, after evaluating terms which are automatically 1,
\[\IPF_2(n,\pi)=\prod_{i=2}^{n-1} \min\{a_i(\pi),2\}.\]
Note that $a_i(\pi)\ge 2$ if and only if $\pi_{i-1}<\pi_i$. There are exactly $\asc(\pi)-1$ different $i$ with $2\le in-i+a_i(\pi)$ we have $b_i(\pi,k)=0$, so the rest of the sum is \begin{align}\sum_{k=n-i+1}^{n-i+a_i(\pi)} b_i(\pi,k)&=(n-i+a_i(\pi)+1)a_i(\pi)-\sum_{k=n-i+1}^{n-i+a_i(\pi)} \max\{a_i(\pi),k\}\nonumber\\ &=(n-i+a_i(\pi)+1)a_i(\pi)-\sum_{k=n-i+1}^{n-i+a_i(\pi)} k,\label{E-B21}\end{align}
where we used our assumption $a_i(\pi)\le n-i*