\documentclass[12pt]{article} \usepackage{e-jc} \specs{P9}{19}{2012} \usepackage{amsmath} \usepackage{amssymb} \usepackage{latexsym} \usepackage{amsthm} \parskip 0.1in \usepackage{amsfonts} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{definition}{Definition} \newcommand{\s}{\mathbf{s}} \newcommand {\no}{\noindent} \newcommand{\A}{{\rm Asc}\,} \newcommand {\des}{{\rm des}} \newcommand {\asc}{{\rm asc}} \newcommand{\integers}{\mathbb{Z}} \newcommand{\reals}{\mathbb{R}} \newcommand{\la}{\lambda} \newcommand{\PP}{{\cal P}} \newcommand {\exc}{{\rm exc}} \newcommand {\Exc}{{\rm Exc}} \newcommand {\cyc}{{\rm \#cyc}} \date{\dateline{Oct 5, 2011}{Dec 19, 2011}{Jan 6, 2012}\\ \small Mathematics Subject Classification: 05A, 52B11, 11P81} \begin{document} \title{The ${1/k}$-Eulerian Polynomials} \author{Carla D. Savage and Gopal Viswanathan\\ \small Department of Computer Science\\[-0.8ex] \small North Carolina State University\\[-0.8ex] \small Raleigh, NC 27695-8206 USA\\ \small \texttt{savage@ncsu.edu} and \texttt{gviswan@ncsu.edu} } \maketitle \begin{abstract}{We use the theory of lecture hall partitions to define a generalization of the Eulerian polynomials, for each positive integer $k$. We show that these {\em ${1}/{k}$-Eulerian polynomials} have a simple combinatorial interpretation in terms of a single statistic on {\em generalized inversion sequences}. The theory provides a geometric realization of the polynomials as the $h^*$-polynomials of {\em $k$-lecture hall polytopes}. Many of the defining relations of the Eulerian polynomials have natural ${1}/{k}$-generalizations. In fact, these properties extend to a bivariate generalization obtained by replacing ${1}/{k}$ by a continuous variable. The bivariate polynomials have appeared in the work of Carlitz, Dillon, and Roselle on Eulerian numbers of higher order and, more recently, in the theory of rook polynomials. } \end{abstract} \section{Overview} The Eulerian polynomials, $A_{n}(x)$, can be defined, for $n \geq 0$, by any of the following relations: \begin{eqnarray} A_{n}(x) & = & \sum_{\pi \in S_{n}} x^{\des(\pi)}; \label{Edes}\\ \sum_{t \geq 0} (t+1)^{n} x^{t} & = & \frac{A_{n}(x)}{(1-x)^{n+1}}; \label{Anseries}\\ \sum_{n \geq 0} A_{n}(x) \frac{z^{n}}{n!} & = & \frac{(1-x)}{e^{z(x-1)}-x}. \label{egf} \end{eqnarray} In (\ref{Edes}), $S_n$ is the set of permutations $\pi: \{1,2, \ldots, n\} \rightarrow \{1,2, \ldots, n\}$ and $\des(\pi)$ is the number of $i$ such that $\pi(i) > \pi({i+1})$. Referring to Foata's survey \cite{foata} on the history of the Eulerian polynomials, (\ref{Anseries}) and (\ref{egf}) are due to Euler \cite{euler} and (\ref{Edes}) is due to Riordan \cite{riordan}. In this paper, for positive integers $k$, we define the $1/k$-Eulerian polynomial combinatorially, as the distribution of a certain statistic ``$\asc$'' over a set of ``$k$-inversion sequences'', $I_{n,k}$, specified in the next subsection. These polynomials arise naturally in the theory of lecture hall partitions, via an associated ``$k$-lecture hall polytope''. We will show that the Ehrhart polynomial of the $k$-lecture hall polytope can be computed explicitly. Consequently, the exponential generating of the $1/k$-Eulerian polynomials can be derived to establish the following relations analogous to (\ref{Edes}) - (\ref{egf}): \noindent {\em The ${1}/{k}$-Eulerian polynomials, $A_{n}^{(k)}(x)$, can be defined for $n \geq 0$ by any of the following relations:} \begin{eqnarray} A_{n}^{(k)}(x) & = & \sum_{e \in {I}_{n,k}} x^{\asc(e)}; \label{ascent_dist}\\ \nonumber \\ \sum_{t \geq 0} \binom{t-1 +\frac{1}{k}}{t} (kt+1)^{n} x^{t} & = & \frac{A_{n}^{(k)}(x)}{(1-x)^{n+\frac{1}{k}}}; \label{series}\\ \nonumber \\ \sum_{n \geq 0} A_{n}^{(k)}(x) \frac{z^{n}}{n!} & =& \left ( \frac{1-x}{e^{kz(x-1)}-x}\right ) ^{\frac{1}{k}}. \label{expgf} \end{eqnarray} Their name is derived from (\ref{expgf}) where their exponential generating function is the $1/k$-th power of a $k$-generalization of (\ref{egf}). Our main contribution is to show that the $1/k$-Eulerian polynomials have a simple combinatorial interpretation in terms of inversion sequences and a geometric realization in terms of lecture hall polytopes. \subsection{Inversion sequences and ascents} In eq.~(\ref{ascent_dist}), the sum is over the set $I_{n,k}$ of {\em $k$-inversion sequences} defined by \begin{eqnarray} I_{n,k} & = & \{ e \in \integers^n \ | \ 0 \leq e_i \leq (i-1)k \}. \label{invseq} \end{eqnarray} For $e \in {I}_{n,k}$, $\asc(e)$ is the number of {\em ascents} of $e$, defined as \begin{eqnarray*} \asc(e) & = & \#\left\{ i: 1 \leq i \leq n-1 \ \Big | \ \ \frac{e_i}{(i-1)k+1} \ < \ \frac{e_{i+1}}{ik+1} \right \}. \label{ascdef} \end{eqnarray*} Note the somewhat unusual definition of ``ascent''. See Figure 1 for an example of the computation of $A_{3}^{(2)}(x)$ from (\ref{ascent_dist}) using these definitions. \subsection{The $1/k$-Eulerian numbers} Define the {\em ${1}/{k}$-Eulerian numbers} $a^{(k)}_{n,j}$ by $a^{(k)}_{n,j} = \#\{ e \in I_{n,k} \ | \ \asc(e) = j\}$. \noindent The triangle of $1/2$-Eulerian numbers is shown below, for $1 \leq n \leq 7$. \begin{tabbing} xxxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\=\kill \>1 \> \\ \>1 \> \>2 \\ \>1 \> \>10 \> \>4 \\ \>1 \> \> 36 \> \> 60 \> \> 8\\ \> 1 \> \> 116 \> \>516 \> \>296 \> \>16 \\ \> 1 \> \>358 \> \>3508 \> \>5168 \> \> 1328 \> \>32\\ \> 1 \> \> 1086 \> \> 21120 \> \> 64240\> \> 42960\> \> 5664\> \>64 \end{tabbing} The third row corresponds to the polynomial in Figure 1. Of course, from the definition, $\sum_{j=0}^{n-1} a^{(k)}_{n,j} = \prod_{i=0}^{n-1} (ik+1)$. \subsection{Lecture hall polytopes} It is a bit surprising that the polynomials $A_{n}^{(k)}(x)$ defined by (\ref{expgf}) have the simple combinatorial interpretation (\ref{ascent_dist}). This interpretation has its roots in the theory of {\em lecture hall partitions} \cite{BME1,BME2}. In Section 2, the equivalence of (\ref{ascent_dist}) and (\ref{series}) is established using recent work of Savage and Schuster relating lecture hall polytopes to statistics on inversion sequences \cite{SS}. It follows from Theorem 5 in \cite{SS} that $A_{n}^{(k)}(x)$, defined by (\ref{ascent_dist}) has a geometric interpretation as the {$h^*$-vector} of the {\em $k$-lecture hall polytope}, $P_{n,k}$, defined by \begin{eqnarray} P_{n,k} & = & \left \{\lambda \in \reals^n \ | \ 0 \leq \frac{\la_1}{1} \leq \frac{\la_2}{k+1} \leq \frac{\la_3}{2k+1} \leq \ldots \leq \frac{\la_n}{(n-1)k+1} \leq 1 \right \}. \label{Pkndef} \end{eqnarray} A key part of the proof of the equivalence of (\ref{ascent_dist}) and (\ref{series}) in Section 2 is a rather involved, explicit computation of the Ehrhart polynomial of $P_{n,k}$. All definitions and background are provided in Section 2. {\center{ \begin{figure} {\small{ \begin{tabbing} xxxxxxxx\=xxxxxxxx\=xxxxxxxxxxxxxx\= xxxxxx\=xxxxxxxx\=xxxxxxxxxxxxxx\= xxxxxx\=xxxxxxxx\=xxxxxxxx\= \kill \\ %xxxxxxxx\=xxxxxxxx\=xxxxxxxxxxxxxxxxx\= % xxxxxx\=xxxxxxxx\=xxxxxxxxxxxxxxxxx\= % xxxxxx\=xxxxxxxx\=xxxxxxxx\= \kill \\ $e$ \> ascents \> $\asc(e)$ \> $e$ \> ascents \> $\asc(e)$ \> $e$ \> ascents \> $\asc(e)$ \\ \\ 000 \> $\{\}$ \> 0 \> 010 \> $\{1\}$ \> 1 \> 020 \> $\{1\}$ \> 1 \\ 001 \> $\{2\}$ \> 1 \> 011 \> $\{1\}$ \> 1 \> 021 \> $\{1\}$ \> 1 \\ 002 \> $\{2\}$ \> 1 \> 012 \> $\{1,2\}$ \> 2 \> 022 \> $\{1\}$ \> 1 \\ 003 \> $\{2\}$ \> 1 \> 013 \> $\{1,2\}$ \> 2 \> 023 \> $\{1\}$ \> 1 \\ 004 \> $\{2\}$ \> 1 \> 014 \> $\{1,2\}$ \> 2 \> 024 \> $\{1,2\}$ \> 2 \end{tabbing} }} \caption{Computation of $A_{3}^{(2)}(x)=1+10x+4x^2$ using (\ref{ascent_dist}).} \end{figure} }} \subsection{Generalizing properties of the Eulerian polynomials} In addition to properties (\ref{Edes}) - (\ref{egf}), the Eulerian polynomials satisfy many relations, including: a recursive definition as an $n$-term sum; a two-term differential recurrence; a differential operator definition; a recurrence for the coefficients; an explicit formula for the coefficients; and a Worpitzky identity (See \cite{foata}). All of these properties can be generalized to the $1/k$-Eulerian polynomials. In order to do so, in Section 3, we view them in a more general setting. In the process, we will uncover a connection between the $1/k$-Eulerian polynomials and previous work. To this end, for $n \geq 0$, define the bivariate polynomial $F_n(x,y)$ by \begin{eqnarray} %\sum_{t \geq 0} \binom{t+y-1}{t}(t+y)^n x^t &= &\frac{F_n(x,y)}{(1-x)^{n+y}}. \sum_{t \geq 0} \binom{t+y-1}{t}(t+y)^n x^t &= &\frac{F_n(x,y)}{(1-x)^{n+y}}. \label{seriesF_intro} \end{eqnarray} Then from (\ref{series}), the relationship between $A_n^{(k)}(x)$ and $F_n(x,y)$ is given by \begin{eqnarray} A_n^{(k)}(x) & = & k^n F_n(x,1/k). \label{AandF} \end{eqnarray} This provides further motivation for the term ``$1/k$-Eulerian polynomials''. In Section 3, we prove that all of the aforementioned properties of the Eulerian polynomials generalize to $F_n(x,y)$ and thereby to the $1/k$-Eulerian polynomials. Most of these identities appear in some form in earlier work and we make the connections in Section 4. However, it is unexpected that the non-integral case of $y=1/k$ should be so interesting. \subsection{The combinatorics of $F_n(x,y)$} In concluding this overview, we highlight one particular outcome of Section 3. It turns out that $F_n(x,y)$ has a simple interpretation in terms of the statistics ``excedance'' and ``number of cycles'' on permutations. The {\em excedance} of a permutation $\pi \in S_n$ is defined by \begin{equation*} \exc(\pi) = \#\{i \ | \ \pi(i) > i\}. \end{equation*} Recall that every $\pi \in S_n$ can be decomposed uniquely as the product of disjoint cycles. The number of such cycles is denoted by $\cyc(\pi)$. The last relation we prove in Section 3 is that \begin{eqnarray} F_n(x,y) & = & \sum_{\pi \in S_n} x^{\exc(\pi)} y^{\cyc(\pi)}. \label{exc_cyc_dist_intro} \end{eqnarray} As discussed in Section 4, this relationship has appeared in various forms elsewhere in the literature. However, the following two consequences of (\ref{exc_cyc_dist_intro}) are relevant here. First, combining (\ref{exc_cyc_dist_intro}), (\ref{AandF}) and (\ref{ascent_dist}), we have \begin{eqnarray*} \sum_{e \in I_{n,k}} x^{\asc(e)} & = & \sum_{\pi \in S_n} x^{\exc(\pi)} k^{n-\cyc(\pi)}. \end{eqnarray*} This gives further evidence that the $k$-inversion sequences and their associated ascent statistic are encoding something of combinatorial significance. Secondly, our results provide a {\em geometric} interpretation of the joint distribution (\ref{exc_cyc_dist_intro}) in terms of the $k$-lecture hall polytope defined by (\ref{Pkndef}), in the special case that $y$ is the reciprocal of an integer. The variable $y$ that tracks the number of cycles in a permutation is related to the angles at which the faces of the polytope meet. In Section 4 we discuss connections between Section 3 and other work in the literature and suggest some further directions for inquiry. \section{The geometry of the ${1/k}$-Eulerian polynomials} \subsection{Lecture hall polytopes and inversion sequences} For a sequence $\s = \{s_i\}_{i \geq 1}$ of positive integers, the {\em $\s$-lecture hall polytope} $\PP_n^{(\s)}$ is defined by \[ \PP_n^{(\s)} = \left\{ \la \in \reals^n \ \Big| \ 0 \leq \frac{\la_{1}}{s_{1}} \leq \frac{\la_{2}}{s_{2}} \leq \cdots \leq \frac{\la_{n}}{s_{n}} \leq 1 \right\}. \] These polytopes, introduced in \cite{SS}, were named after the {\em lecture hall partitions} \cite{BME1,BME2} of Bousquet-Melou and Eriksson. Let $t\PP_n^{(\s)} = \{ t \la \ | \ \la \in \PP_n^{(\s)}\}$ denote the $t$-th {\em dilation} of $\PP_n^{(\s)}$. Define $i(\PP^{(\s)}_n,t)$ by \begin{eqnarray*} i(\PP^{(\s)}_n,t) & = & |t\PP_n^{(\s)} \cap\, \integers^n|. \end{eqnarray*} Since all vertices of $\PP^{(\s)}_n$ have integer coordinates, $i(\PP^{(\s)}_n,t)$ is a rational polynomial in $t$, known as the {\em Ehrhart polynomial} of $\PP^{(\s)}_n$ \cite{ehrhart1,ehrhart2}. There is a relationship between the Ehrhart polynomial of $\PP^{(\s)}_n$ and the distribution of a certain statistic on $\s$-inversion sequences, as we now describe. For a sequence $\s = \{s_i\}_{i \geq 1}$ of positive integers, define the set $I_n^{(\s)}$ of {\em $\s$-inversion sequences} of length $n$ by \begin{eqnarray*} I_n^{(\s)} & = & \left\{(e_1, \ldots, e_n) \in \integers^n \ \left | \right. \ 0 \leq e_i < s_i \ {\rm{for}} \ 1 \leq i \leq n \right\}. \end{eqnarray*} When $\s=(1,2, \ldots, n)$, $I_n^{(\s)}$ is the familiar set of inversion sequences in bijection with $S_n$. For $e \in I_n^{(\s)}$, an {\em ascent} of $e$ is a position $i$ such that $ 1 \leq i < n$ and \begin{eqnarray*} \frac{e_i}{s_i} & < & \frac{ e_{i+1}}{s_{i+1}}. \end{eqnarray*} {\em In addition}, if $e_1 > 0$ then 0 is an ascent of $e$. Let $\asc(e)$ be the number of ascents of $e$. For example, if $\s=(5,3,7)$, then $e=(3,2,3)$ is an $\s$-inversion sequence with ascents in positions 0 and 1, but not in position 2. As another example, if $\s=(1,4,7)$, then $e=(0,3,4)$, as an $\s$-inversion sequence, has an ascent only in position 1. In fact, no $(1,4,7)$-inversion sequence will have 0 as as ascent. The following relationship between the $\s$-inversion sequences and the $\s$-lecture hall polytopes was established in \cite{SS}. \begin{theorem} {\rm \cite{SS}} Let $\s$ be any sequence of positive integers. For integer $n \geq 0$, \begin{eqnarray} \sum_{t \geq 0} i(\PP^{(\s)}_n,t) \ x^t & = & \frac{\sum_{e \in I_n^{(\s)}} \,x^{\asc(e) }} {(1-x)^{n+1}}. \end{eqnarray} \end{theorem} Stanley \cite{hstar} has shown that for any convex lattice polytope, $\PP$, of dimension $n$, there is a polynomial, $h_n^*(x)$, with nonnegative integer coefficients satisfying \begin{eqnarray*} \sum_{t \geq 0} i(\PP,t) x^t & = & \frac{h_n^*(x)}{(1-x)^{n+1}}. \end{eqnarray*} The $\s$-lecture hall polytopes are all convex, in fact they are simplices. So Theorem 1 says, in other words: \begin{quote} {\em The $h^*$-polynomial of the $\s$-lecture hall polytope $\PP_n^{(\s)}$ is the ascent polynomial of the set of $\s$-inversion sequences $I_n^{(\s)}$.} \end{quote} In this paper, our focus is on sequences $\s$ of the form \begin{equation} \s = (1,\ k+1, \ 2k+1, \ \ldots, \ (n-1)k+1), \label{our_s} \end{equation} where $k$ is a positive integer. Recalling $I_{n,k}$ and $P_{n,k}$ from (\ref{invseq}) and (\ref{Pkndef}) in Section 1, we have \begin{eqnarray*} I_{n,k} = I_n^{(\s)} & {\rm and} & P_{n,k} = \PP_n^{(\s)}, \end{eqnarray*} where $\s$ is defined by (\ref{our_s}), giving the following corollary. \begin{corollary} For integers $k \geq 1$ and $n \geq 0$, \begin{eqnarray*} \sum_{t \geq 0} i(P_{n,k},t) x^t & = & \frac{ \sum_{e \in I_{n,k}} x^{\asc(e)}} {(1-x)^{n+1}}. \end{eqnarray*} \label{SScor} \end{corollary} For completeness, we include a proof of Corollary \ref{SScor} in the Appendix. \subsection{The main result} We will show in Section 2.3 that when the sequence $\s$ has the special form (\ref{our_s}), the Ehrhart polynomial of the $\s$-lecture hall polytope has the following closed form. \begin{theorem} For integers $k \geq 1$ and $n,t \geq 0$, \begin{eqnarray*} i(P_{n,k},t) & = & (-1)^{t} \sum_{p=0}^{t} \binom{\frac{1}{k} -1}{t-p} \binom{{-1}/{k}}{p} (kp+1)^{n}, \end{eqnarray*} where \begin{eqnarray*} i(P_{n,k},t) & = & \#\left \{\lambda \in \integers^n \ | \ 0 \leq \frac{\la_1}{1} \leq \frac{\la_2}{k+1} \leq \frac{\la_3}{2k+1} \leq \ldots \leq \frac{\la_n}{(n-1)k+1} \leq t \right \}. \end{eqnarray*} %\label{main} \end{theorem} Our main result, Theorem 3 below, is a consequence of Theorem 2 and Corollary 1. \begin{theorem} For integers $k \geq 1$ and $n \geq 0$, let \begin{eqnarray*} A_n^{(k)}(x) & = & \sum_{e \in {I}_{n,k}} x^{\asc(e)}. \end{eqnarray*} Then \begin{eqnarray*} \sum_{t \geq 0} \binom{t-1 +\frac{1}{k}}{t} (kt+1)^{n} x^{t} & = & \frac{ A_n^{(k)}(x)}{(1-x)^{n+\frac{1}{k}}}. \end{eqnarray*} \end{theorem} \noindent {\bf Proof.} In Theorem 2, sum over $t \geq 0$ and apply the binomial theorem to get \begin{eqnarray*} \sum_{t \geq 0} i(P_{n,k},t) x^t & = & \sum_{t \geq 0} (-x)^{t} \sum_{p=0}^{t} \binom{\frac{1}{k} -1}{t-p} \binom{{-1}/{k}}{p} (kp+1)^{n}\\ & = & (1-x)^{1/k - 1} \sum_{p \geq 0} \binom{{-1}/{k}}{p} (kp+1)^{n} (-x)^p.\\ & = & (1-x)^{1/k - 1} \sum_{p \geq 0} \binom{{p-1+\frac{1}{k}}}{p} (kp+1)^{n} x^p. \end{eqnarray*} From Corollary 1, \begin{eqnarray*} \frac{ A_n^{(k)}(x)}{(1-x)^{n+\frac{1}{k}}} & = & \frac{\sum_{t \geq 0} i(P_{n,k},t) x^t}{(1-x)^{1/k - 1}}\\ & = & \sum_{p \geq 0} \binom{{p-1+\frac{1}{k}}}{p} (kp+1)^{n} x^p. \end{eqnarray*} {\hfill $\Box$} \subsection{Proof of Theorem 2: computation of $i(P_{n,k},t)$} \begin{definition} Let $G_{n, k}^{(j, d, r)}$ be the number of $\la \in \integers^n$ satisfying both \[ 0 \leq \frac{\la_1}{1} \leq \frac{\la_2}{k+1} \leq \ldots \leq \frac{\la_n}{(n-1)k+1} \] and \[ \la_n \leq j((n-1)k+1) + d(n-1) + r. \] \label{bigG} \end{definition} Note that \begin{eqnarray*} i(P_{n,k},t) & = & G_{n, k}^{(t, 0, 0)}. \end{eqnarray*} For suitable conditions on $n,k,j,d,r$, we will find and prove a recurrence for $G_{n, k}^{(j, d, r)}$, solve the recurrence, and then set $d=r=0$ to get $i(P_{n,k},t)$, thereby proving Theorem 2. \begin{theorem} For integers $n \geq 0$, $k \geq 1$, $j \geq 0$ and nonnegative integers $d, r$ satisfying $d=r=0$ if $n=0$ and otherwise $r \leq n-1$ and $(n-1)d + r < k(n-1)+1$, \[ G_{n, k}^{(j, d, r)} = \left \{ \begin{array}{ll} 1 & \mbox{if $n=0$ or $j=d=r=0$, else}\\ G_{n, k}^{(j-1, k, 0)}+ \ G_{n-1, k}^{(j, 0, 0)} & \mbox{if $d=r=0$, else} \\ G_{n, k}^{(j, d-1, n-1)} & \mbox{if $r=0$, else} \\ G_{n, k}^{(j, d, r-1)}+ \ G_{n-1, k}^{(j, d, r-1)} & \mbox{otherwise}. \end{array} \right. \] \label{new_recurrence} \end{theorem} We will need a technical lemma. \begin{lemma} If $0 < r \leq n-1$ and $0 \leq d < k$ then \begin{eqnarray*} \left\lfloor \frac{(n-2)k+1}{(n-1)k+1}((n-1)d+r) \right\rfloor & = &(n-2)d+r-1. \end{eqnarray*} \label{floor_lemma} \end{lemma} \noindent {\bf Proof.} It suffices to verify that \begin{equation*} \frac{(n-2)k+1}{(n-1)k+1}((n-1)d+r) -1 \ <\ (n-2)d+r-1 \ \leq\ \frac{(n-2)k+1}{(n-1)k+1}((n-1)d+r), \end{equation*} which is straightforward. {\hfill $\Box$} \noindent {\bf Proof of Theorem \ref{new_recurrence}.} Let $S_{n, k}^{(j, d, r)}$ denote the set counted by $G_{n, k}^{(j, d, r)}$ in Definition \ref{bigG} and let $\la \in S_{n, k}^{(j, d, r)}$. When $n=0$, or when $j=d=r=0$, $S_{n, k}^{(j, d, r)}$ contains only the empty sequence. Otherwise, $n>0$, with $j+d+r>0$. If $d=r=0$, then $j>0$ and $\lambda_{n} \leq j(k(n-1)+1)$, either $ \lambda_{n} =j(k(n-1)+1) $ or \[ \lambda_{n} \ \leq \ j(k(n-1)+1)-1 \ = \ (j-1)(k(n-1)+1)+(n-1)k+0. \] In the latter case $\la \in S_{n, k}^{(j-1, k, 0)}$. In the former case, $\la$ satisfies \[ \lambda_{n-1} \ \leq \ (k(n-2)+1) \frac{j(k(n-1)+1)}{(k(n-1)+1)} \ = \ j(k(n-2)+1), \] so $(\lambda_{1}, \ldots, \lambda_{n-1}) \in S_{n-1, k}^{(j, 0, 0)}$. Otherwise, if $r=0$, but $d>0$, then \[ \lambda_{n} \ \leq \ j(k(n-1)+1)+(n-1)d \ = \ \lambda_{n} \leq j(k(n-1)+1)+(n-1)(d-1)+n-1. \] Therefore $\la \in S_{n, k}^{(j, d-1, n-1)}$. Otherwise, $r>0$ and $n>0$ and either \[ \lambda_{n} \ = \ j(k(n-1)+1)+(n-1)d+r \] or \[ \lambda_{n}\ \leq \ j(k(n-1)+1)+(n-1)d+r-1. \] Clearly in the latter case $\la \in S_{n, k}^{(j, d, r-1)}$. In the former case, $0 < r \leq n-1$ and $0 \leq d < k$ and $\la$ satisfies \begin{eqnarray*} \lambda_{n-1} & \leq & (k(n-2)+1) \frac{(j(k(n-1)+1)+(n-1)d+r)}{(k(n-1)+1)}\\ & \leq & j(k(n-2)+1) + \left\lfloor \frac{(k(n-2)+1)((n-1)d+r)}{(k(n-1)+1)} \right\rfloor \\ & \leq & j(k(n-2)+1) + (n-2)d+(r-1), \end{eqnarray*} where we have used Lemma \ref{floor_lemma} for the last inequality. Since $n \geq 2$ and $r>0$ we can conclude that $(\lambda_{1}, \ldots, \lambda_{n-1}) \in S_{n-1, k}^{(j, d, r-1)}$. {\hfill $\Box$} Now we solve the recurrence. \begin{theorem} Let integers $k \geq 1$ and $n,j,d,r \geq 0$ satisfy $d=r=0$ if $n=0$ and otherwise $r \leq n-1$ and $(n-1)d + r < k(n-1)+1$. Then $G_{n, k}^{(j, d, r)}$, defined by Definition {\rm{\ref{bigG}}}, has the closed form \begin{eqnarray} \label{rs} G_{n, k}^{(j, d, r)} & = & (-1)^{j} \sum_{p=0}^{j} \binom{\frac{1}{k} -1}{j-p} \binom{\frac{-1}{k}}{p} (kp+1) (kp+d+1)^{n-1-r}(kp+d+2)^{r}. \end{eqnarray} \label{main} \end{theorem} \no {\bf Proof.} Let $f_{n, k}^{(j, d, r)}$ denote the expression on the right-hand side of (\ref{rs}). We prove it satisfies the recurrence of Theorem \ref{new_recurrence}. When $n=0$, then $d=r=0$, and \begin{equation*} f_{0, k}^{(j, 0, 0)} \ = \ (-1)^{j} \sum_{p=0}^{j} \binom{\frac{1}{k} -1}{j-p} \binom{\frac{-1}{k}}{p} \ = \ (-1)^{j} \binom{-1}{j} \ = \ 1, \end{equation*} by the Chu-Vandermonde convolution identity. When $j=d=r=0$, clearly $f_{n, k}^{(0, 0, 0)}=1$. Otherwise, $n>0$ with $j+d+r>0$. If $d=r=0$, then $j>0$ and \begin{eqnarray*} \lefteqn{f_{n, k}^{(j-1, k, 0)} + f_{n-1, k}^{(j, 0, 0)}}\\ &=& (-1)^{j-1} \sum_{p=0}^{j-1} \binom{\frac{1}{k}-1}{j-1-p} \binom{\frac{-1}{k}}{p} (kp+1) (kp+k+1)^{n-1} \\ && \ \ \ \ \ + (-1)^{j} \sum_{p=0}^{j} \binom{\frac{1}{k}-1}{j-p} \binom{\frac{-1}{k}}{p} (kp+1)^{n-1} \\ &=& (-1)^{j} \sum_{p=1}^{j} \binom{\frac{1}{k}-1}{j-p} \binom{\frac{-1}{k}}{p} kp (kp+1)^{n-1} + (-1)^{j} \binom{\frac{1}{k}-1}{j}\\ && \ \ \ \ \ + (-1)^{j} \sum_{p=1}^{j} \binom{\frac{1}{k}-1}{j-p} \binom{\frac{-1}{k}}{p} (kp+1)^{n-1} \\ &=& (-1)^{j} \sum_{p=0}^{j} \binom{\frac{1}{k}-1}{j-p} \binom{\frac{-1}{k}}{p} (kp+1)^{n} \ = \ f_{n, k}^{(j, 0, 0)}. \end{eqnarray*} Otherwise, if $r=0$, but $d>0$, then \begin{equation*} f_{n, k}^{(j, d-1, n-1)} \ = \ (-1)^{j} \sum_{p=0}^{j} \binom{\frac{1}{k}-1}{j-p} \binom{\frac{-1}{k}}{p} (kp+1) (kp+d+1)^{n-1} \ = \ f_{n, k}^{(j, d, 0)}. \end{equation*} Otherwise, $r>0$ and $n>0$, and \begin{eqnarray*} \lefteqn{f_{n,k}^{(j, d, r-1)} + f_{n-1,k}^{(j,d,r-1)}} \\ &=& (-1)^{j} \sum_{p=0}^{j} \binom{\frac{1}{k}-1}{j-p} \binom{\frac{-1}{k}}{p} (kp+1) (kp+d+2)^{(r-1)} ((kp+d+1)^{n-r} \\ && \ \ \ \ \ + (-1)^{j} \sum_{p=0}^{j} \binom{\frac{1}{k}-1}{j-p} \binom{\frac{-1}{k}}{p} (kp+1) (kp+d+2)^{(r-1)} (kp+d+1)^{n-r-1} \\ &=& (-1)^{j} \sum_{p=0}^{j} \binom{\frac{1}{k}-1}{j-p} \binom{\frac{-1}{k}}{p} (kp+1) (kp+d+1)^{n-r-1} (kp+d+2)^{(r)} \ =\ f_{n,k}^{(j, d, r)}. \end{eqnarray*} {\hfill $\Box$} Setting $d=r=0$ in Theorem 5 gives Theorem 2. Note that in computing $G_{n, k}^{(j, d, r)}$, we have actually computed the Ehrhart {\em quasi-polynomial} of the {\em rational lecture hall polytope} $R_{n,k}$: \begin{eqnarray*} R_{n,k} & = & \left \{\lambda \in \reals^n \ | \ 0 \leq \frac{\la_1}{1} \leq \frac{\la_2}{k+1} \leq \frac{\la_3}{2k+1} \leq \ldots \leq \frac{\la_n}{(n-1)k+1} \leq \frac{ 1}{(n-1)k+1} \right \}. \label{Pkn} \end{eqnarray*} \section{A bivariate generalization of the Eulerian polynomials} In Theorem \ref{Ftheorem} of this section, we extend the properties of the Eulerian polynomials to $F_n(x,y)$, defined by (\ref{seriesF_intro}), and therefore, in view of (\ref{AandF}), to $A_n^{(k)}(x)$. We first introduce a $y$-generalization of the binomial coefficient that will play a role. For any real value $y$, define the {\em $y$-binomial coefficient} $\binom{n}{i}_{\hspace{-.02in} y}$ by \begin{eqnarray} \binom{n}{i}_{\hspace{-.02in} y} & = & \binom{n-1}{i}_{\hspace{-.02in} y} + \binom{n-1}{i-1}_{\hspace{-.02in} y}, \label{ybinomial} \end{eqnarray} with initial conditions $\binom{0}{0}_{\hspace{-.02in} y} =1/y$, $\binom{n}{0}_{\hspace{-.02in} y}=1$ for $n>0$, and $\binom{n}{i}_{\hspace{-.02in} y} =0$ for $i > n$. Then $\binom{n}{i}_{\hspace{-.02in} 1} =\binom{n}{i}$ and it is easy to show that \begin{eqnarray*} \binom{n}{i}_{\hspace{-.02in} y} & = &\binom{n-1}{i} + y^{-1} \binom{n-1}{i-1}. \end{eqnarray*} In particular, observe that \begin{eqnarray*} \binom{n}{n}_{\hspace{-.02in} y} & = & 1/y. \end{eqnarray*} When $y=p/r$ for positive integers $p$ and $r$, the numbers $p\binom{n}{i}_{\hspace{-.02in} p/r }$ are referred to as the $(p,r)$ binomial coefficients. We will make use of the following $y$-generalization of the binomial theorem. \begin{lemma} For positive integer $n$, \begin{eqnarray*} \sum_{i=0}^n y \binom{n}{i}_{\hspace{-.02in} y} w^i & = & (y+w)(1+w)^{n-1}. \end{eqnarray*} {\rm (}The sum is equal to $1$ if $n=0$.{\rm )} \label{binomthm} \end{lemma} \noindent {\bf Proof.} This is clear for $n=0$ and $n=1$. For $n > 1$, assume the lemma is true for integers smaller than $n$. Then using (\ref{ybinomial}), \begin{eqnarray*} \sum_{i=0}^n y \binom{n}{i}_{\hspace{-.02in} y} w^i & = & y + \sum_{i=1}^{n-1}y \binom{n-1}{i}_{\hspace{-.02in} y} w^i + \sum_{i=1}^{n-1} y \binom{n-1}{i-1}_{\hspace{-.02in} y} w^i + w^n\\ & = & (y+w)(1+w)^{n-2} + w(y+w)(1+w)^{n-2} \ = \ (y+w)(1+w)^{n-1}. \end{eqnarray*} {\hfill $\Box$} \begin{theorem} For $n \geq 0$, define $F_n(x,y)$ by \begin{eqnarray} \sum_{t \geq 0} \binom{t+y-1}{t}(t+y)^n x^t &= &\frac{F_n(x,y)}{(1-x)^{n+y}}. \label{seriesF} \end{eqnarray} Then $F_n(x,y)$ satisfies each of the following relations {\rm (\ref{expgfF}) - (\ref{exc_cyc_dist})}: \label{Ftheorem} \end{theorem} \vspace{.1in} \noindent {\bf Exponential generating function:} \begin{eqnarray} \sum_{n \geq 0} F_n(x,y) \frac{z^n}{n!} & = & \left ( \frac{1-x}{e^{z(x-1)} -x} \right )^y. \label{expgfF} \end{eqnarray} \vspace{.1in} \noindent {\bf Recursive definition via $y$-binomial coefficient} \begin{eqnarray} F_n(x,y) &= & \sum_{j = 0}^{n-1} y \binom{n}{j}_{\hspace{-.02in} y} F_j(x,y) (x-1)^{n-j-1}. \label{inductiveF} \end{eqnarray} with initial conditions $F_{0}(x,y)=1$, $F_{1}(x,y)=y$. \vspace{.1in} \noindent {\bf Two-term differential recurrence:} \begin{eqnarray} F_{n+1}(x,y) &= & x(1-x) \frac{d}{dx} F_n(x,y) + (y+nx)F_n(x,y), \label{poly_recF} \end{eqnarray} with initial conditions $F_{0}(x,y)=1$, $F_{1}(x,y)=y$. \vspace{.2in} \noindent {\bf Differential operator definition} \vspace{.1in} Define the operator $D_y$ by $D_y= \frac{x}{y} \frac{d}{dx}$. Then \begin{eqnarray} D_y^{n}\left (\frac{1}{(1-x)^{y}} \right)& =& \frac{ (x/y)^{n} F_{n}(1/x,y)}{(1-x)^{n +y}}. \label{kdiffopF} \end{eqnarray} \vspace{.1in} \noindent {\bf Recurrence for the coefficient of $x^j$} \vspace{.1in} Let $F_{n}(x,y) = \sum_{j = 0}^{n-1} f_{n,j}(y) x^j$. Then \begin{eqnarray} f_{n+1,j}(y) &= & (j+y) f_{n,j}(y) \ + \ (n+1-j) f_{n,j-1}(y). \label{EnumberRecF} \end{eqnarray} \vspace{.1in} \noindent {\bf Formula for the coefficient of $x^j$} \begin{eqnarray} f_{n,j}(y) &=& \sum_{t = 0}^{j} (-1)^{j-t} \binom{t-1+y}{t} \binom{n+y}{j-t} (t+y)^{n}. \label{kEformula} \end{eqnarray} \vspace{.1in} \noindent {\bf Generalized Worpitzky identity} \begin{eqnarray} \binom{t-1+y}{t} (t+y)^{n} & = &\sum_{j} f_{n,j}(y) \binom{t+y+n-j-1}{t-j}. \label{kWorpitzkyF} \end{eqnarray} \vspace{.1in} \noindent {\bf Recurrence for the coefficient of $x^jy^k$} \vspace{.1in} Let $f_{n,j,k}$ be the coefficient of $x^jy^k$ in $F_n(x,y)$. Then \begin{eqnarray} f_{n,j,k} & = & j f_{n-1,j,k} \ + \ (n-j) f_{n-1,j-1,k} \ + \ f_{n-1,j,k-1}, \label{3drec} \end{eqnarray} with boundary conditions $f_{0,0,0}=1$ and $f_{n,j,k}=0$ if $j+k>n$. \vspace{.1in} \vspace{.1in} \noindent {\bf Combinatorial characterization:} \begin{eqnarray} F_n(x,y) & = & \sum_{\pi \in S_n} x^{\exc(\pi)} y^{\cyc(\pi)}, \label{exc_cyc_dist} \end{eqnarray} where $S_n$ is the set of permutations $\pi: \{1,2, \ldots, n\} \rightarrow \{1,2, \ldots, n\}$, $\exc(\pi) = \#\{i \ | \ \pi(i) > i\}$, and $\cyc(\pi)$ is the number of cycles in the disjoint cycle representation of $\pi$. \vspace{.1in} \noindent {\bf Proof of (\ref{expgfF})}. Using (\ref{seriesF}), \begin{eqnarray*} \sum_{n \geq 0} F_{n}(x,y) \frac{z^{n}}{n!} & = & \sum_{n \geq 0} (1-x)^{n+y} \sum_{t \geq 0} \binom{t-1 +y}{t} (t+y)^{n} x^{t} \frac{z^{n}}{n!}\\ & = & (1-x)^{y} \sum_{t \geq 0} \binom{t-1 +y}{t} x^{t} \sum_{n \geq 0} \frac{(z(1-x)(t+y))^{n}}{n!}\\ & = & (1-x)^{y} \sum_{t \geq 0} \binom{t-1 +y}{t} x^{t} e^{z(1-x)(t+y)}\\ & = & (1-x)^{y}e^{yz(1-x)} \sum_{t \geq 0} \binom{t-1 +y}{t} (xe^{z(1-x)})^{t}\\ & = & \frac{((1-x)e^{z(1-x)})^y}{(1-xe^{z(1-x)})^{y}} \ \ = \ \ \left ( \frac{1-x}{e^{z(x-1)} -x} \right )^y. \end{eqnarray*} \hfill{$\Box$} \vspace{.1in} \noindent {\bf Proof of (\ref{inductiveF})}. Let $S_{n}^{(k)}(x) = F_{n}(x,y)/(1-x)^{n+y}.$ We will show, equivalently, that \begin{eqnarray*} (1-x) S_{n}(x,y) & = & \sum_{i=0}^{n-1} y \binom{n}{i}_{\hspace{-.02in} y} S_{i}(x,y) (-1)^{n-1-i}. \end{eqnarray*} Using our series expansion (\ref{seriesF}) of $S_{i}(x)$ and equating coefficients of $x^j$, it suffices to show that \begin{eqnarray*} \lefteqn{\binom{j-1 + y}{j} (j+y)^n - \binom{j-2 + y}{j-1} (j-1+y)^n}\\ && \ \ \ \ \ = \ \sum_{i=0}^{n-1} y \binom{n}{i}_{\hspace{-.02in} y} \binom{j-1 +y}{j} (j+y)^i (-1)^{n-1-i}, \end{eqnarray*} or, more simply, that \begin{eqnarray*} \sum_{i=0}^{n-1} y \binom{n}{i}_{\hspace{-.02in} y} (j+y)^i (-1)^{n-1-i} & = & (j+y)^n - j(j-1+y)^{n-1}. \end{eqnarray*} To show this, apply Lemma \ref{binomthm}, setting $w=-(j+y)$: \begin{eqnarray*} (-1)^{n-1}\sum_{i=0}^{n} y \binom{n}{i}_{\hspace{-.02in} y} (-1)^i (j+y)^i & = & (-j)(y+j-1)^{n-1}. \end{eqnarray*} The result follows now by subtracting the $i=n$ term from both sides. {\hfill $\Box$} \vspace{.1in} \noindent {\bf Proof of (\ref{poly_recF})}. Apply (\ref{seriesF}) and rewrite as follows: \begin{eqnarray*} F_{n+1}(x,y) & = & (1-x)^{n+1+y} \sum_{t \geq 0} \binom{t-1 +y}{t} (t+y)^{n+1} x^{t} \nonumber\\ & = & (1-x)^{n+1+y} \left [ \sum_{t \geq 0} \binom{t-1 +y}{t} t (t+y)^{n} x^{t} + y\sum_{t \geq 0} \binom{t-1 +y}{t} (t+y)^{n} x^{t} \right] \nonumber\\ & = & x(1-x)\left [ (1-x)^{n+y} \sum_{t \geq 0} \binom{t-1 +y}{t} t (t+y)^{n} x^{t-1} \right] + y(1-x)F_{n}(x,y). \end{eqnarray*} Now note that \begin{eqnarray*} \frac{d}{dx} F_{n}(x,y) & = & \left [ (1-x)^{n+y} \sum_{t \geq 0} \binom{t-1 +y}{t} t (t+y)^{n} x^{t-1} \right] - \frac{(n+y) F_{n}(x,y)}{1-x}. \label{derivative} \end{eqnarray*} Combining the two calculations gives the result. \hfill{$\Box$} \vspace{.1in} \noindent {\bf Proof of (\ref{kdiffopF})}. We use induction on $n$. The identity is clearly true when $n=0$. Assume it is true for some $n > 0$. Then \begin{eqnarray*} D_y^{n+1}\left( \frac{1}{ (1-x)^y } \right)& =& (x/y) \frac{d}{dx} \left [ \frac{ (x/y)^{n} F_{n}(1/x,y)}{(1-x)^{n +y }} \right ]. \end{eqnarray*} Using (\ref{poly_recF}) with the chain rule, \begin{eqnarray*} \frac{d}{dx} F_{n}(1/x,y) & = & \frac{1}{(1-x)}\left [F_{n+1}(1/x,y) -(y+n/x)(F_{n}(1/x,y) \right ]. \end{eqnarray*} Thus \begin{eqnarray*} \frac{x}{y}\frac{d}{dx} \left [ \frac{ (x/y)^{n} F_{n}(1/x,y)}{(1-x)^{n + y }} \right ] & = & \left ( \frac{(x/y)^{n+1}}{(1-x)^{n +y }} \right ) \frac{d}{dx} F_{n}(1/x,y)\\ & & \ \ \ \ \ + \ \frac{x}{y} F_{n}(1/x,y) \frac{d}{dx} \left [\frac{(x/y)^n}{(1-x)^{n +y}} \right ]\\ & = & \frac{(x/y)^{n+1}( F_{n+1}(1/x,y)-(y+\frac{n}{x})F_{n}(1/x,y))} {(1-x)^{n+1 +y }}\\ & & \ \ \ \ \ + \ \frac{x}{y} F_{n}(1/x,y) \left[ \frac{(x/y)^{n}(y+\frac{n}{x})}{(1-x)^{n+1+y}} \right]\\ & = & \frac{(x/y)^{n+1} F_{n+1}(1/x,y)} {(1-x)^{n+1 +y}}. \end{eqnarray*} \hfill{$\Box$} \vspace{.1in} \noindent {\bf Proof of (\ref{EnumberRecF})}. By (\ref{poly_recF}), \begin{eqnarray*} \sum_{j=0}^{n} f_{n+1,j}(y)x^j & = & x(1-x) \frac{d}{dx} \sum_{j=0}^{n} f_{n,j}(y)x^j + (y+nx) \sum_{j=0}^{n} f_{n,j}(y)x^j\\ & = & x(1-x) \sum_{j=0}^{n}j f_{n,j}(y)x^{j-1} + (y+nx) \sum_{j=0}^{n} f_{n,j}(y)x^j\\ & = & \sum_{j=0}^{n} (j f_{n,j}(y) -(j-1) f_{n,j-1}(y) + yf_{n,j}(y) + n f_{n,j-1}(y)) x^j\\ & = & \sum_{j=0}^{n} ((j+y) f_{n,j}(y) + (n+1-j) f_{n,j-1}(y)) x^j. \end{eqnarray*} Now equate coefficients of $x^j$ on both sides. \hfill{$\Box$} \vspace{.1in} \noindent {\bf Proof of (\ref{kEformula})}. Start with (\ref{seriesF}), apply the binomial theorem, and extract the coefficient of $x^j$: \begin{eqnarray*} \sum_{j=0}^{n-1} f_{n,j}(y) x^{j} &=& \sum_{t \geq 0} \binom{t-1+y}{t} (t+y)^{n} x^{t}(1-x)^{n+y} \\ &=& \sum_{t \geq 0} \binom{t-1+y}{t} (t+y)^{n} x^{t} \sum_{p \geq 0}^{} \binom{n+y }{p} (-x)^{p} \\ &=& \sum_{j \geq 0} \sum_{t = 0}^{j} (-1)^{j-t} \binom{t-1+y}{t} \binom{n+y }{j-t} (t+y)^{n} x^{j}. \\ \end{eqnarray*} \hfill{$\Box$} \vspace{.1in} \noindent {\bf Proof of (\ref{kWorpitzkyF})}: Start with (\ref{seriesF}), apply the binomial theorem, and extract the coefficient of $x^t$: \begin{eqnarray*} \sum_{t \geq 0} \binom{t-1+y}{t} (t+y)^{n} x^{t} &=& {\sum_{i=0}^{n-1} f_{n,i}(y) x^{i} }{(1-x)^{-(n+y})} \\ &=& \sum_{i=0}^{n-1} f_{n,i}(y) x^{i} \sum_{p \geq 0}^{} \binom{p+n-1+y }{p} x^{p} \\ &=& \sum_{t \geq 0} \sum_{i \geq 0} f_{n,i}(y) \binom{t+y+n-i-1}{t-i} x^{t}. \end{eqnarray*} \hfill{$\Box$} \vspace{.1in} \noindent {\bf Proof of (\ref{3drec})}: The boundary conditions are clear. For $n > 0$, start with the definition of $f_{n,j,k}$ and apply (\ref{EnumberRecF}): \begin{eqnarray*} F_n(x,y) \ = \ \sum_{j=0}^{n-1} \sum_{k=1}^{n} f_{n,j,k} x^jy^k & = & \sum_{j=0}^{n-1} f_{n,j}(y) x^j\\ & = & \sum_{j=0}^{n-1} ((j+y)f_{n-1,j}(y) + (n-j)f_{n-1,j-1}(y))x^j\\ & = & \sum_{j=0}^{n-1} \sum_{k=1}^{n} (j f_{n-1,j,k} + (n-j) f_{n-1,j-1,k} + f_{n-1,j,k-1}) y^kx^j. \end{eqnarray*} Equating coefficients of $y^kx^j$ gives the result. {\hfill $\Box$} \vspace{.1in} \noindent {\bf Proof of (\ref{exc_cyc_dist})}: This follows from (\ref{egf}) and the Exponential Theorem (Chapter 5, \cite{stanley2}), but we give a combinatorial proof using (\ref{3drec}). Let $g_{n,j,k}$ be the number of permutations $\pi \in S_n$ with $\exc(\pi) = j$ and $\cyc(\pi) = k$. We show that $g_{n,j,k}$ satisfies the recurrence (\ref{3drec}) with the same boundary conditions. Let $\Exc(\pi) = \{i \ | \ \pi(i) > i\}$. The boundary conditions are clear. When $n=1$, $g_{n,j,k}=0$ unless $j=0$ and $k=1$, in which case it is 1. This agrees with $F_1(x,y)=y$. For $n>1$, a permutation $\mu \in S_n$ with $k$ cycles and $j$ excedances can be constructed in one of three mutually exclusive ways from a permutation in $S_{n-1}$: (i) From a $\pi \in S_{n-1}$ with $k-1$ cycles and $j$ excedances, by adding the cycle $(n)$ of length 1. Then $\cyc(\mu) = \cyc(\pi) + 1$ and $\Exc(\mu) = \Exc(\pi)$. (ii) From a $\pi \in S_{n-1}$ with $k$ cycles and $j$ excedances, by inserting `$n$' between $t$ and $\pi(t)$ on the cycle containing $t$, where $t \in Exc(\pi)$. Then $\cyc(\mu) = \cyc(\pi)$ and $\Exc(\mu) = \Exc(\pi)$. (iii) From a $\pi \in S_{n-1}$ with $k$ cycles and $j-1$ excedances, by inserting `$n$' between $t$ and $\pi(t)$ on the cycle containing $t$, where $t$ is one of the $(n-1)-(j-1)$ elements $t \not \in Exc(\pi)$. In this case, $\cyc(\mu) = \cyc(\pi)$ and $\Exc(\mu) = \Exc(\pi) \cup \{t\}$. {\hfill $\Box$} This concludes the proof of Theorem \ref{Ftheorem}. \section{Connections, observations and further directions} From Theorem \ref{Ftheorem}, we have both (\ref{expgfF}) and (\ref{exc_cyc_dist}), facts that have appeared in various forms in the literature. For {\em integer} $y$, $F_n(x,y)$, defined by (\ref{expgfF}), arises as a special case in the work of Carlitz \cite{carlitz}. For real $y$, Dillon and Roselle \cite{DillonRoselle} use the exponential in (\ref{expgfF}) to define a reciprocal of $F_n(x,y)$ and prove several properties, including analogs of (\ref{EnumberRecF}), (\ref{kEformula}), and (\ref{3drec}). They also provide a combinatorial characterization of their polynomial as the joint distribution, over $S_n$, of the ascent statistic and the left-to-right-maximum. Since their polynomial is the reciprocal of ours, this implies (\ref{exc_cyc_dist}), by the fundamental transformation of Foata and Sch{\"u}tzenberger \cite{fs}. In \cite{fs}, Foata and Sch{\"u}tzenberger directly compute the exponential generating function of the distribution defined by (\ref{exc_cyc_dist}) and obtain a different, but equivalent, form of (\ref{expgfF}). A refinement appears in the work of Ksavrelof and Zeng \cite{zeng}, where the number of fixed points is also included as a parameter. Variations of (\ref{seriesF}) and (\ref{kWorpitzkyF}) based on weak excedances appear in work in progress of Gessel \cite{gessel2}. The thesis of Butler \cite{ButlerThesis}, on rook theory, contains $q$-analogs of the identities (\ref{seriesF}), (\ref{EnumberRecF}), and (\ref{kEformula}). When $q=1$, his corresponding polynomial is the joint distribution over $S_n$ of the statistics (descent, left-to-right-min), which have the same joint distribution as $(\exc, \cyc)$. We have not found (\ref{inductiveF}) in the literature in quite this form. Of course the $y=1$ case is well known. Variations for the cases $y=2$ and $y=3$ appear in Sloane (see the 2- and 3-restricted numbers below), which also suggested to us the differential operator definition (\ref{kdiffopF}) for the general case. Several special cases of $F_n(x,y)$ have been studied. Note that from (\ref{seriesF}) we get a nice proof of the fact (see \cite{zeng}) that \[ F_n(x,-1) \ = \ -(x-1)^{n-1}, \] since only the $t=0$ term is nonzero and it is $(-1)^n$. Also, in (\ref{poly_recF}), setting $x=1$ gives the recurrence $F_{n+1}(1,y) = (y+n)F_{n}(1,y)$, which has solution \[ F_{n+1}(1,y) \ = \ (y+1)(y+2) \cdots (y+n-1), \] the generating function for the unsigned Stirling cycle numbers. The ``second order Eulerian numbers'' appearing in \cite{GKP} and as entry A008517 in Sloane's EIS have the same row sums as our 1/2-Eulerian polynomial, $A_n^{(2)}(x)$, but the entries are not the same. On the other hand, the reciprocal of $A_n^{(2)}(x)$ is given by the rows of the triangle in entry A156919 of Sloane's EIS, so the row polynomial is \[ R_n(x) \ = \ x^n A_n^{(2)}(1/x) \ = \ (2x)^nF_n(1/x,1/2). \] That entry is referred to as a ``Table of coefficients of polynomials related to the Dirchlet eta function''. The rows of the triangle of ``2-restricted Eulerian numbers'' in entry A014496 of Sloane's EIS defines a polynomial $P_n(x)$ that is the reciprocal of a multiple of $F_n(x,2)$, namely \[ P_n(x) \ = x^nF_n(1/x,2)/2. \] More generally, the rows of the ``$r$-restricted Eulerian number'' triangle satisfy \[ P^{(r)}_n(x) \ = x^nF_n(1/x,r)/r. \] We close with a few questions. First, is it possible to interpret $F_n(x,y)$ in terms of lecture hall polytopes for other values of $y$, for example, when $y$ is rational? Secondly, can we define a meaningful $q$-analog of the $1/k$-Eulerian polynomial? We could have $q$ track the ``amaj'' statistic defined in \cite{SS}. Another possibility is to adapt the $q$-analogs of $F_n(x,y)$ that are used in rook theory. In \cite{PS}, the work of \cite{SS} is being extended to rational lecture hall polytopes. This should allow an interpretation of the $h^*$ polynomial of the rational $k$-lecture hall polytope whose Ehrhart quasi-polynomial was computed at the end of Section 2. Will this have a continuous analog corresponding to anything that has been studied before? Finally, is there a more direct connection between lecture hall partitions and rook theory that could provide insight into either area? \vspace{.2in} \noindent {\bf Acknowledgments} We would like to thank the following colleagues for helpful discussions: Herbert Wilf (on the proof of Theorem 3), Peter Paule (on the proof of Theorem 5), and Ira Gessel (for showing us connections with the work of \cite{ButlerThesis,fs,zeng}). Thanks also for the support of the American Institute of Mathematics where some of these discussions took place. \section{Appendix: Proof of Corollary \ref{SScor} : the $h^*$-vector of $\PP^{(k)}_n$} We are to show that \begin{align} \sum_{t \geq 0} \#\left \{\lambda \in \integers^n \ | \ 0 \leq \frac{\la_1}{1} \leq \frac{\la_2}{k+1} \leq \ldots \leq \frac{\la_n}{(n-1)k+1} \leq t \right \} x^t & = \frac{ \sum_{e \in {I}_{n,k}} x^{\asc(e)}} {(1-x)^{n+1}}. \label{TE} \end{align} \noindent {\bf Proof.} The proof uses the notion of barred inversion sequences, adapted from the method of barred permutations from \cite{GS}. A {\em barred $k$-inversion sequence} is a sequence $e \in {I}_{n,k}$ in which one or more vertical bars are inserted before and/or after elements $e_i$, with the stipulation that if $i$ is an {\em ascent} of $e$, there is at least one bar in position $i$, the space immediately preceding $e_{i+1}$. We show that both sides of (\ref{TE}) count the barred $k$-inversion sequences of length $n$. For the right-hand side, consider a barred $k$-inversion sequence $e \in {I}_{n,k}$. It must must have at least one bar following each ascent position, but additional bars may be distributed among all of the $n + 1$ `` spaces '' of $e$. The number of ways to place $j$ identical bars into $n+1$ spaces is the coefficient of $x^{j}$ in $ 1 / \left(1-x \right)^{n+1} $, so, summing over all $e \in {I}_{n,k}$, the right-hand side of (\ref{TE}) counts the number of barred $k$-inversion sequences in ${I}_{n,k}$. For the left-hand side, for each $t$, we establish a bijection between the barred $k$-inversion sequences with $t$ bars and the set $t {P}_{n,k} \cap \mathbb{Z}^{n}$ counted by the summand. Let $e$ be a barred $k$-inversion sequence with $t$ bars. For $1 \leq i \leq n$, let $b_{i}$ be the total number of bars preceding $e_{i}$ in any position. Then $b_{1} \leq b_{2} \leq \ldots \leq b_{n}$. Define $\lambda=(\lambda_{1}, \ldots, \lambda_{n})$ by \[ \lambda_{i} = (k(i-1)+1)b_{i} - e_{i}. \] We show that $\lambda \in (t {P}_{n,k} \cap \mathbb{Z}^{n})$. First note that $\lambda_{i} \geq 0$, since $e_{i} < k(i-1)+1$ and if $b_{i}=0$, then no position $j