\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