%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{32}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{amssymb}
\usepackage{epsfig,tikz}
\usepackage{graphicx}
\usepackage{comment}
\usepackage{asymptote}

\usepackage{mathtools}
\def\multichoose#1#2{\left<\genfrac{}{}{0pt}{}{#1}{#2}\right>}

\newcommand{\Mbar}{\overline{M}}

\newcommand{\bR}{\mathbb{R}}
\newcommand{\bA}{\mathbb{A}}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\sL}{\mathcal{L}}
\newcommand{\sF}{\mathcal{F}}
\newcommand{\sU}{\mathcal{U}}
\newcommand{\sE}{\mathcal{E}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\Qbar}{\bar{\bQ}}

\DeclareMathOperator{\trop}{trop}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\PGL}{PGL}

\newcommand{\St}{\operatorname{St}}
\newcommand{\Comp}{\mathrm{Comp}}
\newcommand{\CPF}{\mathrm{CPF}}
\newcommand{\Good}{\mathrm{GPF}}
\newcommand{\Bad}{\mathrm{BPF}}
\newcommand{\Noncorner}{\mathrm{GPF}_\bullet}
\newcommand{\Corner}{\mathrm{BPF}_\bullet}
\newcommand{\ins}{\iota}
\newcommand{\rem}{\nu}
\newcommand{\col}{c}
\newcommand{\dom}{d}
\newcommand{\rev}{\mathrm{rev}}

\newcommand{\defn}{\textbf}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{corollary}[thm]{Corollary}


\theoremstyle{definition}
\newtheorem{ex}[thm]{Exercise}
\newtheorem{example}[thm]{Example}
\newtheorem{defi}[thm]{Definition}
\newtheorem{q}[thm]{Question}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem*{f}{Fact}
\newtheorem{remark}[thm]{Remark}


%% define your title in the usual way
\title[$\Mbar_{0,n}$ and Parking Functions]{Projective Embeddings of $\Mbar_{0,n}$ and Parking Functions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Renzo Cavalieri, Maria Gillespie, and Leonid Monin]{Renzo Cavalieri\thanks{\href{mailto:renzo@math.colostate.edu}{renzo@math.colostate.edu}. Partially supported by Simons Collaboration Grant 420720.}\addressmark{1}, 
\and Maria Gillespie\thanks{\href{mailto:Maria.Gillespie@colostate.edu}{Maria.Gillespie@colostate.edu.}}\addressmark{2}, 
\and Leonid Monin\thanks{\href{mailto:leonid.monin@bristol.ac.uk}{leonid.monin@bristol.ac.uk}.  Partially supported by  EPSRC Early Career Fellowship EP/R023379/1.}\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Colorado State University, Fort Collins, CO, USA \\ \addressmark{2}Department of Mathematics, Colorado State University, Fort Collins, CO, USA \\
\addressmark{3}Department of Mathematics, University of Bristol, Bristol, UK}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{The moduli space $\Mbar_{0,n}$ %of stable curves with $n$ marked points 
    may be  embedded into the product of projective spaces $\bP^1\times \bP^2\times \cdots \times \bP^{n-3}$, using a combination of the Kapranov map $\Mbar_{0,n}\to \mathbb{P}^{n-3}$ and the forgetful maps $\pi_i:\Mbar_{0,i}\to \Mbar_{0,i-1}$.  We give an explicit combinatorial formula for the multidegree of this embedding in terms of certain parking functions.  
    
   This combinatorial interpretation  provides a recursive formula for the generating function of the multidegree.  We further show that the total degree of the embedding (thought of as the projectivization of its cone in $\bA^2\times \bA^3\cdots \times \bA^{n-2}$) is equal to $(2(n-3)-1)!!=(2n-7)(2n-9) \cdots(5)(3)(1)$.  As a consequence, we also obtain a new combinatorial interpretation for the odd double factorial.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Parking functions, stable curves, multidegree}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\addbibresource{fpsac.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

\section{Introduction}

The moduli space of stable, $n$-marked, rational curves $\Mbar_{0,n}$ is a poster child for the field of combinatorial algebraic geometry.
It is a smooth,  projective variety and a fine and proper moduli space. It may be obtained from $\mathbb{P}^{n-3}$ by a combinatorially prescribed sequence of blow-ups along smooth loci. It is also a tropical compactification, meaning  that it can be realized as  the closure of a very affine variety inside a toric variety. The stratification induced by the boundary of the toric variety coincides with the natural stratification by homeomorphism classes of the objects parameterized; strata are  indexed by stable trees with $n$-marked leaves, and the graph algebra of stable trees completely controls the intersection theory of $\Mbar_{0,n}$, meaning that one may combinatorially define a multiplication on stable trees in such a way that the natural assignment of a tree with the (closure of the) stratum it indexes defines a surjective ring homomorphism to the Chow ring of $\Mbar_{0,n}$ (\cite{Ka2, Ka1,keel1992}).  

This work provides another instance of the rich interaction between algebraic geometry and combinatorics brought about by $\Mbar_{0,n}$.  Our central focus is the closed embedding $$\phi:\Mbar_{0,n}\to \bP^1\times \bP^2\times \cdots \times \bP^{n-3}$$  arising from the recent work of Keel and Tevelev \cite{KeT}.  
We study the degrees of the embedding from both a geometric and combinatorial perspective. We now state succinctly our two main results and then discuss them.

\begin{thm}\label{thm:main-1}
Let $n\geq{3}$  and $\mathbf{k} = \{k_1, \ldots, k_{n-3}\}$ be an ordered list of non-negative integers with $\sum k_i = n-3$. Then:
\begin{equation}
    \deg_\mathbf{k}(\phi(\Mbar_{0,n})) = 
    \int_{\Mbar_{0,n}} \prod_{i=1}^{n-3}{\omega_{3+i}^{k_i}} = 
  \multichoose{n-3}{\rev(\mathbf{k})}=
    |\CPF(n-3,\rev(\mathbf{k}))|.
\end{equation}
\end{thm}

\begin{thm}\label{thm:main-2}
    Denote by $C$ the affine cone over $\phi(\Mbar_{0,n})$ in $\bA^2\times \bA^{3}\times \cdots \times\bA^{n-2}$. Then  \begin{equation}
    \deg(\mathbb{P}(C))=\sum_{\bf k} \deg_{\bf k}(\phi(\Mbar_{0,n}))=(2(n-3)-1)!!    
    \end{equation} where $(2n-7)!!=(2n-7)(2n-9) \cdots (5)(3)(1)$ is the odd double factorial. 
\end{thm}
In \cref{thm:main-1}, the first two quantities are geometric, and the latter two are purely combinatorial.


  The \textit{multidegree} $\deg_\mathbf{k}(\phi(\Mbar_{0,n}))$ of this embedding with respect to the tuple $\mathbf{k}=(k_1,\ldots,k_{n-3})\in \mathbb{N}^{n-3}$ is  given by intersecting the image of the embedding $\phi(\Mbar_{0,n})$ with (pullbacks of) $k_i$  hyperplane classes in each factor $\bP^i$.  We define certain \textit{omega classes} $\omega_{i+3}$ corresponding to these hyperplane pullbacks.

By relating these omega classes to the well-known $\psi$ classes on $\Mbar_{0,n}$, we obtain a recursion for the multidegree $\deg_{\bf k}(\phi(\Mbar_{0,n}))$ that resembles the recursion satisfied by the multinomial coefficient $\binom{n}{\mathbf{k}}$.    We therefore define the symbol $\multichoose{n}{\bf k}$ to satisfy the corresponding asymmetric recursion (see \cref{def:asym} below), and we show that $$\deg_{\bf k}(\phi(\Mbar_{0,n}))=\multichoose{n-3}{\rev({\bf k})}$$ where $\rev({\bf k})=(k_{n-3},k_{n-2},\ldots,k_1)$ is the tuple formed by reversing $\mathbf{k}$.

  Finally, we show that these asymmetric analogs $\multichoose{n}{\bf k}$ of multinomial coefficients exhibit a remarkable combinatorial interpretation in terms of \textit{parking functions}.  Parking functions were first defined by Konheim and Weiss \cite{KW1966} as solutions to an algorithmic problem involving parking cars, and may be defined as functions $f:\{1,2,\ldots,n\}\to \{1,2,\ldots,n\}$ such that $|f^{-1}(\{1,2,\ldots,i\})|\ge i$ for all $i$.  Parking functions have since become a central tool in combinatorics, perhaps most notably in the study of diagonal harmonics and $q,t$-analogs of Catalan numbers (see \cite{HaglundBook,HHLRU}). 
  
  We introduce here the notion of \textit{column restriction} on parking functions (see \cref{sec:combinatorics}), and define $\CPF(n,\mathbf{k})$ to be the set of all column-restricted parking functions $f$ on $\{1,2,\ldots,n\}$ such that $k_{i}=|f^{-1}(i)|$ for all $i$.  The resulting combinatorial interpretation in \cref{thm:main-1} is the primary tool we use to prove \cref{thm:main-2}.  In particular, we show that the total number of column-restricted parking functions of size $n$ is $(2n-1)!!$, giving a new combinatorial interpretation of the double factorial.

  We structure this extended abstract as follows.  In \cref{sec:background} we establish some necessary geometric and combinatorial background and notation.  In \cref{sec:geometry} we give the recursion on the multidegree of $\phi(\Mbar_{0,n})$.  In \cref{sec:combinatorics} we define column-restricted parking functions, provide the recursive formula for the generating function of the multidegree (see \cref{prop:generating-function}), and give an outline of the proofs of \cref{thm:main-1,thm:main-2}.  Full proofs and details will be given in \cite{CGM2019}.

\section{Background}\label{sec:background}

\subsection{Parking functions and compositions}\label{sec:comb-background}

A \textbf{(weak) composition} of $n$ is a tuple $\mathbf{k}=(k_1,\ldots,k_j)$ of nonnegative integers such that $\sum_{i=1}^j k_i=n$.  We say that $j$ is the \textbf{length} of the composition, and we write $\Comp(n,j)$ to denote the set of all weak compositions of $n$ having length $j$.  We say a composition $\mathbf{k}\in \Comp(n,n)$ is \defn{Catalan} if for all $j<n$, we have $k_1+k_2+\cdots+k_j\ge j$.  

A \defn{Dyck path} of height $n$ is a path from $(0,0)$ to $(n,n)$, using only steps $(0,1)$ or $(1,0)$, which always stays weakly above the diagonal line $y=x$. 
A \defn{parking function} is a Dyck path along with a labeling of all unit squares having an up-step to its left with the numbers $1,2,\ldots,n$ in some order, such that in each column the numbers are increasing from bottom to top.  An example of a parking function for $n=6$ is shown on Figure~\ref{fig:PF}.

\begin{figure}
\begin{center}
\includegraphics{main-1.pdf}
\end{center}
\caption{\label{fig:PF}An example of a parking function of size $6$.}
\end{figure}
A parking function may be specified by the sets of entries in each column from left to right.  The columns above are $(\{2,3,5\},\{\},\{1,6\},\{\},\{\},\{4\})$, giving rise to the associated \textbf{sequence of column heights} $(3,0,2,0,0,1)$.  Given the columns, we can reconstruct the parking function by placing the column entries in increasing order in each column, increasing the height by one for each successive entry from left to right.  Notice that the resulting path formed by the columns is a Dyck path if and only if the sequence of column heights is Catalan. 



\subsection{The moduli space $\Mbar_{0,n}$}\label{sec:m0n}
For $n \geq 3$, the moduli space $M_{0,n}$ parameterizes ordered $n$-tuples of distinct points on $\bP^1$. We say that two $n$-tuples $(p_1,\ldots,p_n)$ and $(q_1,\ldots, q_n)$ are equivalent if there exists a projective transformation $g \in \PGL(2,\bC)$ such that
$(q_1,\ldots, q_n) = (g(p_1),\ldots,g(p_n)).$
 Since a projective transformation can map three fixed points on $\bP^1$ to any other three points and is uniquely determined by their image, we have $\dim M_{0,n}=n-3$.

The space $M_{0,n}$ is not compact, hence we consider its Deligne-Mumford compactification $\Mbar_{0,n}$ (\cite{Ka2, Ka1,keel1992}),  
parametrizing \emph{stable $n$-pointed rational curves}.
\begin{defi}
 A \defn{stable rational $n$-pointed curve} is a tuple $(C, p_1, \ldots, p_n)$, where $C$ is a connected curve of arithmetic genus $0$ with at most simple nodal singularities, $p_1, \ldots, p_n$ are distinct nonsingular points on $C$, and each irreducible component of $C$ has at least three special points (either marked points or nodes).
\end{defi}

The divisorial components of the boundary of $\Mbar_{0,n}$ correspond to partitions of the set $\{1,\ldots,n\}$ into two subsets $I$ and $I^c$, each of cardinality at least $2$.  These correspond to the stable curves consisting of two irreducible components $C_1,C_2$ intersecting at a node, with the marked point $p_i$ on the component $C_1$ if and only if $i\in I$.  We denote the corresponding irreducible boundary divisor of $\Mbar_{0,n}$ by $\delta_I$ (or equivalently by $\delta_{I^c}$). 

\subsection{Chow ring and integral notation}

For a smooth algebraic variety $Y$, its \defn{Chow ring} $A^*(Y)$ is an algebraic version of De Rham cohomology. The elements of the $i$-th graded piece $A^i(Y)$ are integral linear combinations of irreducible subvarieties of $Y$ of codimension $i$ modulo rational equivalence. For two classes $Z_1\in A^i,\, Z_2\in A^j$, their product in $Z_1\cdot Z_2\in A^{i+j}(Y)$ is  the class of the intersection of transversely intersecting representatives of $Z_1, Z_2$. 

For the product of projective spaces $\bP^{\bf b}=\bP^{b_1}\times\ldots\times \bP^{b_n}$ let $p_i:\bP^{\bf b}\to \bP^{b_i}$ be the natural projection on the $i$-th factor. We define special divisor classes $H_1,\ldots,H_n$ in the Chow ring of $\bP^{\bf b}$ to be the pullbacks of hyperplanes in $\bP^{b_1},\ldots,\bP^{b_n}$ respectively:
$$
H_i:=p_i^* H_{\bP^{b_i}}.
$$
 
We  use integral notation for the degree of a $0$-dimensional cycle (by analogy with De Rham cohomology).  For example, if $X\subseteq \bP^{\bf b}$, we write
$$
\deg_0\left(X\cdot \prod_{i=1}^n H_i^{k_i}\right) = \int_{\bP^{\bf b}} X\cdot \prod_{i=1}^n H_i^{k_i}.
$$


\subsection{Multidegree} 

Let $X\subseteq \bP^{\bf b}$ be a subvariety of the product of projective spaces. 
Then for any integer vector ${\bf k}=(k_1,\ldots, k_n)\in \bZ_{\geq 0}^n$ one can define the degree of $X$ of index $\bf k$ to be the degree of the zero dimensional cycle 
$$
\deg_{\bf k}(X) := \int_{ \bP^{\bf b}}X\cdot \prod_{i=1}^n H_i^{k_i},
$$
where if the dimension of $X\cdot \prod_{i=1}^n H_i^{k_i}$ is nonzero, then by definition $\deg_{\bf k}(X)=0$. Note that the degree of index $\bf k$ is zero unless $\sum k_i=\dim(X)$. 


By Poincar\'e duality, the collection of numbers $\deg_{\bf k}$ for all $\bf k$ determines the class of $X$ in the Chow ring $A^*(\bP^{\bf b})$:
\begin{equation}\label{eq:poincare}
    [X]= \sum_{{\bf k},\, |{\bf k}|=\dim(X)} \deg_{\bf k}(X) \cdot H_1^{b_1-k_1}\ldots H_n^{b_n-k_n} \in A^{|{\bf b}|-\dim(X)}(\bP^{\bf b}).
\end{equation}

For $X\subseteq  \bP^{\bf b}$ let $Con(X)\subseteq \bA^{b_1+1}\times\ldots\times\bA^{b_n+1}$ be the affine cone over $X$.
The following theorem of Van Der Waerden \cite{van} relates multidegrees of $X$ with the degree of the projectivization $\mathbb{P}(Con(X))$.
\begin{thm}
The degree $\deg(\mathbb{P}(Con(X)))$ is equal to the sum of all multidegrees of $X$:
$$
\deg(\mathbb{P}(Con(X)))= \sum_{\bf k}\deg_{\bf k}(X).
$$
\end{thm}

For the closed embedding of projective variety $\phi:X\to \bP^{\bf b}$ the degree of index $\bf k$ of the image $\phi(X)$ is equal to:
$$
\int_X \prod_{i=1}^n (\phi^*H_i^{k_i}).
$$


\section{Embeddings of $\Mbar_{0,n}$ in products of projective spaces}\label{sec:geometry}  

In this section we describe the embedding $\phi:\Mbar_{0,n}\hookrightarrow\bP^1\times\cdots\times\bP^{n-3}$ obtained in \cite{KeT}. The embedding $\phi$ depends on two well-studied maps from $\Mbar_{0,n}$, namely the forgetful map $\pi_n:\Mbar_{0,n}\to\Mbar_{0,n-1}$ and Kapranov's map $\psi_n:\Mbar_{0,n}\to\bP^{n-3}$. 

The forgetful map $\pi_n:\Mbar_{0,n}\to\Mbar_{0,n-1}$ is the morphism given by forgetting the last point of $[C,p_1,\ldots p_n]$  and stabilizing the curve, i.e. contracting the components which have less than three special points and remembering the points of intersection.

To describe $\psi_n$, let $\mathbb{L}_i$ be the line bundle on $\Mbar_{0,n}$ whose fiber over a point\linebreak[0] $[C,p_1,\ldots,\linebreak[0]p_n]$ is the cotangent space of $\bP^1$ at $p_i$. Define $\psi_i=c_1(\mathbb{L}_i)$ to be the first Chern class of $\mathbb{L}_i$. The Kapranov map $\psi_n$ is the rational map given by the linear system $|\psi_n|$. This map was first described in detail by Kapranov~\cite{Ka1}, who proved in particular that  $\psi_n:\Mbar_{0,n}\to\bP^{n-3}$.


The following theorem is the key to defining $\Mbar_{0,n}$ as a subvariety of a product of projective spaces.

\begin{thm}\label{thm:embedding}\cite[Cor 2.7]{KeT} The map $\Phi_n=(\pi_n,\psi_n):\Mbar_{0,n}\rightarrow \Mbar_{0,n-1}\times \bP^{n-3}$ is a closed embedding. 
\end{thm}
Iterated applications of \cref{thm:embedding} yield a closed embedding \begin{equation}\phi:\Mbar_{0,n}\hookrightarrow \bP^1\times\bP^2\times\ldots \times\bP^{n-3}.
\end{equation}



Let  $H_1,\ldots,H_{n-3}$ as before be the pullbacks of hyperplane classes in $\bP^{1},\ldots,\bP^{n-3}$ respectively. Let $f_i=\pi_{i+1}\circ \cdots \circ \pi_n: \Mbar_{0,n} \to \Mbar_{0,i}$ be the forgetful map that forgets the points labelled by $i+1,\ldots,n$.  The class  $\phi^*H_i$ on $\Mbar_{0,n}$ is equal to $f_{i+3}^* \psi_{i+3}$, where $\psi_{i+3}$ is understood as a psi class on $\Mbar_{0,i+3}$. Therefore, the degree of $\Mbar_{0,n}$ of index ${\bf k}=(k_1,\ldots,k_{n-3})$ is nonzero only if $\sum b_i =n-3$ and is equal to:
$$
\deg_\mathbf{k}(\phi(\Mbar_{0,n})) = \int_{\Mbar_{0,n} } \prod_{i=1}^{n-3} f_{i+3}^*(\psi_{i+3}^{k_{i}}),
$$
where $\psi_i$ is the psi class on the $\Mbar_{0,i}$. Motivated by this formula we introduce the following definition.

\begin{defi}
We define an \defn{omega class} $\omega_i:=f_i^*(\psi_i)$ on $\Mbar_{0,n}$ to be the pullback of the corresponding psi class from $\Mbar_{0,i}$. 
\end{defi}

  In this notation, the degree of $\Mbar_{0,n}$ of index ${\bf k}=(k_1,\ldots,k_{n-3})$ is equal to:
$$
\int_{\Mbar_{0,n} } \prod_{i=1}^{n-3} \omega_{i+3}^{k_{i}}.
$$

\subsection{Intersection theory of $\omega$ classes on $\Mbar_{0,n}$}

Let $\St:\Sym^d\to \Sym^{d-1}$ be a linear transformation of the space of polynomials defined on monomials as
$$
\St\left(\prod x_i^{k_i}\right)=\sum_{i,k_i\ne 0} x_i^{k_i-1}\prod_{j\ne i}x_j^{k_j},
$$
and extended by linearity. The notation $\St$ is  due to the \defn{String equation} which provides the recursive formula for the intersection numbers of $\psi$ classes. If $\prod \psi_i^{k_i}$ is a monomial in $\psi$ classes with $k_a=0$ for some $1\leq a \leq n$, then
\begin{equation}\label{string}
    (\pi_a)_* \prod \psi_i^{k_i} = \St \left(\prod \psi_i^{k_i} \right).
\end{equation}
Note that if $\sum k_i =n-3$, we have
$$
\int_{\Mbar_{0,n}}\prod \psi_i^{k_i} = \St^{n-3} \left(\prod x_i^{k_i}\right)= \binom{n-3}{k_1,\ldots,k_n}.
$$
The following lemma is an analogue of the string equation for $\omega$ classes.

\begin{lemma}\label{lem:omega-classes}
Let  $ \prod_{i=1}^{a-1} \omega_i^{k_{i}} \prod_{j=a+1}^{n} \omega_j^{k_{j}}$ be a monomial in omega classes such that $k_j >0$ for all $a< j\leq n$. Then the following relation holds:
\begin{equation}\label{eq:recom}
 (\pi_{a})_*\left( \prod_{i=1}^{a-1} \omega_i^{k_{i}} \prod_{j=a+1}^{n} \omega_j^{k_{j}}\right)= (\pi_{a})_*\left( \prod_{i=1}^{a-1} \omega_i^{k_{i}} \prod_{j=a+1}^{n} \psi_j^{k_{j}}\right)=  \prod_{i=1}^{a-1} \omega_i^{k_{i}} \cdot \St \left(\prod_{j=a+1}^{n} \psi_j^{k_{j}}\right).   
\end{equation}


\end{lemma}

\begin{proof} 
The string recursion for psi classes follows from the relation: 
\begin{equation}\label{eq:pbpsi}
 \pi_{k}^*(\psi_i) = \psi_i - \delta_{i,k+1},   
\end{equation}
where $\pi_k: \Mbar_{0,k+1}\to  \Mbar_{0,k}$ is the forgetful map.  Equation \eqref{eq:recom} follows from \eqref{eq:pbpsi} and a careful use of the projection formula.
\end{proof}

The following proposition can be derived from \cref{lem:omega-classes}.

\begin{prop}\label{prop:degree-recursion}
The multidegree $\deg_{\mathbf{k}}(\Mbar_{0,n+3})$, with respect to the embedding $\phi$, satisfies the recursion:
\begin{equation}\label{eq:degree-recursion}
    \deg_{\bf k}(\Mbar_{0,n+3})=\sum_{j=i+1}^{n} \deg_{\mathbf{k}'_j}(\Mbar_{0,n+2})
\end{equation}
for all $\mathbf{k}=(k_1,\ldots,k_n)$ with $\sum_t k_t=n$, where $i$ is the index of the rightmost zero in $\mathbf{k}$ and $\mathbf{k}'_j$ is formed by (1) decreasing $k_j$ by $1$, and then (2) deleting the rightmost zero in the resulting sequence (which may be either in position $i$ or $j$).  
\end{prop}


Notice also that the embedding $\phi:\Mbar_{0,4}\to \mathbb{P}^1$ is simply the identity map since $\Mbar_{0,4}\cong \mathbb{P}^1$.  Thus  $\deg_{(1)}(\Mbar_{0,4})=1$.

\section{Parking functions and the double factorial}\label{sec:combinatorics}

We now establish the connections with parking functions and outline the proofs of the main two theorems. 

\subsection{Asymmetric multinomials}

\cref{prop:degree-recursion} naturally gives rise to the following combinatorial definitions. 

\begin{defi}
	Let $\mathbf{k}\in \Comp(n,n)$, let $k_i$ be the leftmost $0$ in $k$, and let $j<i$ be a positive integer.  Then we define $\widetilde{\mathbf{k}}_j\in \Comp(n-1,n-1)$ by decreasing $k_j$ by $1$ in $\mathbf{k}$ and then removing the leftmost $0$ from the resulting tuple (which is either in position $j$ or $i$). 
\end{defi}

For example, if $\mathbf{k}=(3,1,2,0,0,1,0)$, then $\widetilde{\mathbf{k}}_1=(2,1,2,0,1,0)$, $\widetilde{\mathbf{k}}_2=(3,2,0,0,1,0)$, and $\widetilde{\mathbf{k}}_3=(3,1,1,0,1,0)$.  Since $i=4$ in this example, $\widetilde{\mathbf{k}}_4$ is not defined.  Note that this construction is simply the reverse of the construction $k_j'$ defined in \cref{prop:degree-recursion}.

\begin{defi}\label{def:asym}
	The \defn{asymmetric multinomial coefficients} $\multichoose{n}{\bf k}$ (where $\mathbf{k}\in \Comp(n,n)$) are defined by the recursion $\multichoose{1}{1}=1$ and $$\multichoose{n}{\mathbf{k}}=\sum_{j=1}^{i_{\mathbf{k}}} \multichoose{n-1}{\widetilde{\mathbf{k}}_j}$$ where $i_{\mathbf{k}}$ is the index of the leftmost $0$ in a composition $\mathbf{k}$.
\end{defi}

The equations (\ref{eq:degree-recursion}) and \cref{def:asym} together show that $\deg_{\mathbf{k}}(\Mbar_{0,n+3})=\multichoose{n}{\rev(\bf k)}.$ Catalan sequences naturally arise from this recursion, as shown in the following lemma, whose proof we omit.

\begin{lemma}\label{lem:Catalan}
    If $\bf k\in \Comp(n,n)$ is Catalan, then $\widetilde{\bf k}_j$ is also Catalan for any $j\le i_{\bf k}$.  Conversely, if $\bf{k}$ is not Catalan then $\widetilde{\bf k}_j$ is not Catalan for any $j\le i_{\bf k}$.
    
    As a consequence, we have that $\multichoose{n}{\bf k}$ is nonzero if and only if $\mathbf{k}$ is Catalan. 
\end{lemma}

We now obtain a recursion for the generating function $$F_n(x_1,\ldots,x_n):=\sum_{\mathbf{k}\in \Comp(n,n)} \multichoose{n}{\bf k} x_1^{k_1}\cdots x_n^{k_n},$$ which is the natural dual of the Poincar\'e polynomial of equation (\ref{eq:poincare}).

Define $\Comp(n,n,i)$ to be the set of all $\bf k\in \Comp(n,n)$ for which $i$ is the index of the leftmost zero in $\bf k$.  If $k_j\neq 0$ for all $j$ we say $i=n+1$ and write the set as $\Comp(n,n,n+1)$.  We define the auxiliary generating functions $$F_{n,i}(x_1,\ldots,x_n)=\sum_{\mathbf{k}\in \Comp(n,n,i)}\multichoose{n}{\bf k}x_1^{k_1}\cdots x_n^{k_n}.$$  We simply write $X$ for the set of variables $x_1,\ldots,x_n$, and the notation $F(X\backslash x_i)$ means that we are plugging in $x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n$ into the function $F$.

\begin{prop}\label{prop:generating-function}
  We have $$F_n(X)=\sum_{i=2}^{n+1} F_{n,i}(X)$$ where the functions $F_{n,i}(X)$ satisfy the recursion $$F_{n,i}(X)=\left(\sum_{j=1}^{i-1} x_jF_{n-1,i-1}(X\backslash x_j)\right)+(x_1+\cdots+x_{i-1}) \sum_{j=i}^{n}F_{n-1,j}(X\backslash x_i)$$ with initial condition $F_{1,2}(x_1)=x_1$.
\end{prop}

\begin{proof}
This is a straightforward consequence of \cref{def:asym}.
\end{proof}



\subsection{Column-restricted parking functions}\label{sec:parking-functions}

We now obtain a combinatorial interpretation of $\multichoose{n}{\bf k}$.

\begin{defi}
	Let $P$ be a parking function, and let $a$ be a label in $P$.  Define the \defn{dominance index} of $a$, written $d_P(a)$, to be the number of columns left of $a$ that contain no label greater than $a$.  
\end{defi}


\begin{defi}
A parking function $P$ is \defn{column-restricted} if for every label $a$, $$d_P(a)<a.$$ We write $\CPF(n,\mathbf{k})$ to denote the set of all column-restricted parking functions having columns of lengths $k_1,k_2,\ldots,k_n$ from left to right, and $\CPF(n)=\bigcup_{\bf k} \CPF(n,\mathbf{k})$.
\end{defi}

For example, the parking function in \cref{fig:PF} is not column-restricted because the $1$ has an empty column to its left.  Those in \cref{fig:recursion} are column-restricted. 

We now give a brief sketch of the proof of \cref{thm:main-1}, which can be stated as: $$|\CPF(n,\mathbf{k})|=\multichoose{n}{\mathbf{k}}.$$

\begin{proof}[Proof of \cref{thm:main-1}] (Sketch.)
  We show that $|\CPF(n,\mathbf{k})|$ satisfies the recursion of \cref{def:asym}.  It is easy to check that $|\CPF(1,(1))|=1$.   
  
  For the recursion, let $P\in \CPF(n,\mathbf{k})$ and let $i$ be the index of the leftmost $0$ in $\mathbf{k}$.  Note that the entry $1$ must be in some column $j\le i-1$ by column-restrictedness.  Then if we first remove the row containing the $1$, then remove the leftmost empty column (which may be either column $j$ or column $i$), and finally decrease all remaining labels by $1$, we obtain a new parking function $P'$.  One can check that $P'\in \CPF(n,\widetilde{\mathbf{k}}_j)$, and that we can uniquely reconstruct $P$ given $P'$ and $j$.  (See \cref{fig:recursion}.) 
\end{proof}
\begin{figure}
\begin{center}
\includegraphics{main-2.pdf}
\end{center}
\caption{\label{fig:recursion} An illustration of the map $P\mapsto P'$ described in the proof of \cref{thm:main-1}.}
\end{figure}

\subsection{Counting by $(2n-1)!!$}

We now give a brief outline of the proof of \cref{thm:main-2}, namely, that $$\sum_{\mathbf{k}\in \Comp(n,n)} \multichoose{n}{\mathbf{k}}=(2n-1)!!$$  The left hand side simply counts $|\CPF(n)|$.  Since $|\CPF(1)|=1$, it suffices to show that $$|\CPF(n)|=(2n-1)|\CPF(n-1)|$$ for all $n\ge 2$.  To do so, note that any Dyck path from $(0,0)$ to $(n-1,n-1)$ passes through exactly $2n-1$ lattice points.  We show that we can ``insert'' a label $n$ at each of these points to construct a column-restricted parking function of height $n$ from one of height $n-1$.  

\begin{defi}
   A \defn{pointed} column-restricted parking function is an element $P\in \CPF(n)$ along with a choice $p$ of one of the $2n-1$ lattice points on its Dyck path.  We write $\CPF_{\bullet}(n)$ for the set of all pointed column-restricted parking functions $(P,p)$ of size $n$.
\end{defi}

With this in mind, we define the following insertion map.


\begin{defi}
  For an element $(P,p)\in \CPF_{\bullet}(n-1)$, we define $\ins(P,p)$ as follows.  Let $P_{p\to}$ be the tail of $P$ (both the path and labels) after the point $p$. 
  
  \begin{enumerate}
      \item Shift $P_{p\to}$ one step up and one step right.  Connect the newly separated paths by an up step followed by a right step, and label the new up step by $n$.
      
      \item Let $C_1,\ldots,C_t$ be the columns that contain some entry whose dominance index changed upon performing step 1 above.  Move the column $C_1$ into the rightmost empty column to its left, then move $C_2$ into the rightmost empty column to its left (which may be the column that $C_1$ occupied before), and so on.  
  \end{enumerate}
  
  The result is $\ins(P,p)$.  (See \cref{fig:ins})
\end{defi}


\begin{figure}
\begin{center}
\includegraphics{main-3.pdf}
\end{center}
\caption{\label{fig:ins}
An example of the map $\ins$, where the dotted corner above the $5$ in the left hand diagram indicates the point $p$ at which we insert $n=13$.}

\end{figure}
The following lemma, whose proof we omit, is often useful in computing $\ins$.

\begin{lemma}\label{lem:corners}
    In step 2 of computing $\ins(P,p)$, we have $t>0$ (i.e., step 2 is nontrivial) if and only if $p$ is an upper left corner of the Dyck path.
    
    Moreover, in this case, let $r$ be the label just below the point $p$.  Then the only labels whose dominance index changes in step 1 of $\ins$ are those labels $a<r$ to the right of $r$, and their dominance index increases by exactly $1$.
\end{lemma}

\cref{lem:corners} gives rise to the following natural definitions.

\begin{defi}
   We write $\Noncorner(n-1)$ (resp.\ $\Corner(n-1)$) to denote the pairs $(P,p)\in \CPF_\bullet(n-1)$ in which $p$ is not an upper left corner (resp.\ is an upper-left corner).  We refer to these types as \defn{good} and \defn{bad} pointed CPF's respectively.
\end{defi}

We can also tell from the output of $\ins(P,p)$ whether $(P,p)$ is good or bad.

\begin{lemma}
  We have $(P,p)\in \Noncorner(n-1)$ if and only if, in $\ins(P,p)$, either (a) there is no label below $n$ in its column, or (b) there is a label $r$ below $n$ and the square up-and-right from $n$ contains a label $a>r$.  
\end{lemma}

\begin{defi}
Say that a parking function $Q$ in $\CPF(n)$ is \defn{good} if either (a) there is no label below $n$ in its column, or (b) there is a label $r$ below $n$ and the square up-and-right from $n$ contains an entry $c>r$.  If $Q$ is not good, we call it \defn{bad}, and this occurs if and only if the square below $n$ contains a label $r$ and the square up-and-right from $n$ either is empty or contains a label $c$ with $c<r$.

We write $\Good(n)$ and $\Bad(n)$ for the sets of good and bad column-restricted parking functions of height $n$, respectively.
\end{defi}

\begin{prop}
	The map $\ins:\CPF_\bullet(n-1)\to \CPF(n)$ is a well-defined bijection, and it restricts to bijections $$\ins:\Noncorner(n-1)\to \Good(n)\hspace{0.5cm}\text{ and }\hspace{0.5cm}\ins:\Corner(n-1)\to \Bad(n).$$    
\end{prop}

The proof of this proposition is rather technical; full details can be found in \cite{CGM2019}.  \cref{thm:main-2} follows.

\acknowledgements{This project started at the thematic semester in combinatorial algebraic geometry. We are grateful to the Fields Institute for providing a stimulating  research environment. }

\printbibliography



\end{document}
