\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<i$ is an ascent, so $e_{1}=\ldots =e_{i}=0$.
Since $e$ is a $k$-inversion sequence, $ \frac{e_{j}}{k(j-1)+1}<1$ for all $j$.
Now, if $i$ is an ascent of $e$, there is at least one bar between $e_{i}$ and $e_{i+1}$, so $b_{i}<b_{i+1}$ and
\[
\frac{\lambda_{i}}{k(i-1)+1} \   = \  b_{i} -\frac{e_{i}}{k(i-1)+1} \   \leq \  b_{i} \  \leq \  b_{i+1}-1  \  <  b_{i+1} -\frac{e_{i+1}}{ki+1} \  =  \   \frac{\lambda_{i+1}}{ki+1}.
\]
On the other hand, if $i$ is not an ascent of $e$,
then
\[
\frac{e_{i}}{k(i-1)+1}  \ \geq  \ \frac{e_{i+1}}{ki+1},
\]
so
\[
\frac{\lambda_{i}}{k(i-1)+1}  \  = \  b_{i} -\frac{e_{i}}{k(i-1)+1}  \   \leq  \ b_{i+1} -\frac{e_{i+1}}{ki+1}  \ =  \   \frac{\lambda_{i+1}}{ki+1}.
\]
To complete the proof that $\la \in (tP_{n,k} \cap \integers^n)$
note that since $b_n \leq t$ (the total number of bars in $e$),
\[
\frac{\lambda_{n}}{k(n-1)+1} = b_{n} - \frac{e_{n}}{k(n-1)+1}  \leq t.
\]
To prove that this is a bijection, we define the inverse.
If $\lambda \in (t  {P}_{n,k}   \cap \mathbb{Z}^{n})$, let
\[
b= \left( \left \lceil \frac{\lambda_{1}}{1} \right \rceil, \ldots, \left\lceil \frac{\lambda_{n}}{k(n-1)+1} \right \rceil \right)=(b_{1}, \ldots, b_{n}). 
\]
Then  $b_{n} \leq t $. Let $e=(e_{1}, \ldots, e_{n})$, where
$
 e_{i} = s_{i}b_{i} - \lambda_{i}.
$
Then $e \in {I}_{n,k}$ and we ``bar'' it by placing $b_{1}$ bars before $e_{1}$, $b_{i}-b_{i-1}$ bars before $e_{i}$ for $2 \leq i \leq  n$, and $t-b_{n}$ bars after $e_{n}$.
By definition of $b$ and $e$, $e_1=0$, so 0 is not an ascent of $e$.
If, for some $i$ with $1 \leq i <  n$, there is no bar following $e_i$,
then $b_{i}=b_{i+1}$ and therefore, since $\lambda \in (t {\PP}_n^{(k)}  \cap \mathbb{Z}^{n})$, 
 \[
 \frac{e_{i}}{k(i-1)+1} \  = \  b_{i} - \frac{\lambda_{i}}{k(i-1)+1}  \ \geq  \  b_{i} - \frac{\lambda_{i+1}}{ki+1}  \ =  \  b_{i+1} - \frac{\lambda_{i+1}}{ki+1} \  =  \  \frac{e_{i+1}}{ki+1}.
 \]
Thus $i$ is not an ascent of $e$ and the ``barring'' is valid.
{\hfill $\Box$}




\bibliographystyle{plain}
\begin{thebibliography}{10}

\bibitem{BME1}
Mireille Bousquet-M{\'e}lou and Kimmo Eriksson.
\newblock Lecture hall partitions.
\newblock {\em Ramanujan J.}, 1(1):101--111, 1997.

\bibitem{BME2}
Mireille Bousquet-M{\'e}lou and Kimmo Eriksson.
\newblock Lecture hall partitions. {II}.
\newblock {\em Ramanujan J.}, 1(2):165--185, 1997.

\bibitem{ButlerThesis}
Frederick~Michael Butler.
\newblock {\em Cycle-counting {Q}-rook theory and other generalizations of
  classical rook theory}.
\newblock ProQuest LLC, Ann Arbor, MI, 2004.
\newblock Thesis (Ph.D.)--University of Pennsylvania.

\bibitem{carlitz}
L.~Carlitz.
\newblock Eulerian numbers and polynomials of higher order.
\newblock {\em Duke Math. J.}, 27:401--423, 1960.

\bibitem{DillonRoselle}
J.~F. Dillon and D.~P. Roselle.
\newblock Eulerian numbers of higher order.
\newblock {\em Duke Math. J.}, 35:247--256, 1968.

\bibitem{ehrhart1}
Eugene Ehrhart.
\newblock Sur un probl\`eme de g\'eom\'etrie diophantienne lin\'eaire. {I}.
  {P}oly\`edres et r\'eseaux.
\newblock {\em J. Reine Angew. Math.}, 226:1--29, 1967.

\bibitem{ehrhart2}
Eugene Ehrhart.
\newblock Sur un probl\`eme de g\'eom\'etrie diophantienne lin\'eaire. {II}.
  {S}yst\`emes diophantiens lin\'eaires.
\newblock {\em J. Reine Angew. Math.}, 227:25--49, 1967.

\bibitem{euler}
Leonhard Euler.
\newblock Remarques sur un beau rapport entre les s{\'e}ries des puissances
  tant directes que r{\'e}ciproques.
\newblock {\em M{\'e}moires de l'acad{\'e}mie des sciences de Berlin},
  27:83--106, 1768.

\bibitem{foata}
Dominique Foata.
\newblock Eulerian polynomials: from {E}uler's time to the present.
\newblock In {\em The Legacy of {A}lladi {R}amakrishnan in the Mathematical
  Sciences}, pages 253--273. Springer, New York, Dordrecht, Heidelberg, London,
  2010.

\bibitem{fs}
Dominique Foata and Marcel-P. Sch{\"u}tzenberger.
\newblock {\em Th\'eorie g\'eom\'etrique des polyn\^omes eul\'eriens}.
\newblock Lecture Notes in Mathematics, Vol. 138. Springer-Verlag, Berlin,
  1970.

\bibitem{gessel2}
Ira Gessel.
\newblock private communication.

\bibitem{GS}
Ira Gessel and Richard~P. Stanley.
\newblock Stirling polynomials.
\newblock {\em J. Combinatorial Theory Ser. A}, 24(1):24--33, 1978.

\bibitem{GKP}
Ronald~L. Graham, Donald~E. Knuth, and Oren Patashnik.
\newblock {\em Concrete {m}athematics}.
\newblock Addison-Wesley Publishing Company, Reading, MA, second edition, 1994.
\newblock A foundation for computer science.

\bibitem{zeng}
G{\'e}rald Ksavrelof and Jiang Zeng.
\newblock Two involutions for signed excedance numbers.
\newblock {\em S\'em. Lothar. Combin.}, 49:Art. B49e, 8 pp. (electronic),
  2002/04.

\bibitem{PS}
Thomas~W. Pensyl and Carla~D. Savage.
\newblock Rational lecture hall polytopes and inflated {E}ulerian polynomials.
\newblock 2011.
\newblock submitted, preprint available at
  \texttt{http://www4.ncsu.edu/$\sim$savage/PAPERS/rational.pdf}.

\bibitem{riordan}
John Riordan.
\newblock {\em An introduction to combinatorial analysis}.
\newblock Wiley Publications in Mathematical Statistics. John Wiley \& Sons
  Inc., New York, 1958.

\bibitem{SS}
Carla~D. Savage and Michael~J. Schuster.
\newblock Ehrhart series of lecture hall polytopes and {E}ulerian polynomials
  for inversion sequences.
\newblock submitted, preprint available at
  \texttt{http://www4.ncsu.edu/$\sim$savage/PAPERS/ESofLHPandEPforIS.pdf},
  2011.

\bibitem{hstar}
Richard~P. Stanley.
\newblock A monotonicity property of {$h$}-vectors and {$h^*$}-vectors.
\newblock {\em European J. Combin.}, 14(3):251--258, 1993.

\bibitem{stanley2}
Richard~P. Stanley.
\newblock {\em Enumerative combinatorics. {V}ol. 2}, volume~62 of {\em
  Cambridge Studies in Advanced Mathematics}.
\newblock Cambridge University Press, Cambridge, 1999.
\newblock With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

\end{thebibliography}


\end{document}




