---
abstract: |
    Let $n\geq 1$, $0\leq t\leq {n \choose 2}$ be arbitrary integers. Define the numbers $I_n(t)$ as the number of permutations of $[n]$ with $t$ inversions.

    Let $n,d\geq 1$ and $0\leq t\leq (d-1)n$ be arbitrary integers. Define [*the polynomial coefficients*]{} $H(n,d,t)$ as the numbers of compositions of $t$ with at most $n$ parts, no one of which is greater than $d-1$.

    In our article we give explicit formulas for the numbers $I_n(t)$ and $H(n,d,t)$ using the theory of Gröbner bases and free resolutions.
author:
- |
    Gábor Hegedüs\
    [Johann Radon Institute for Computational and Applied Mathematics]{}
title: The number of permutations with $k$ inversions
---

 Introduction
=============

First we introduce some notation. Throughout the paper $n$ is a positive integer. We denote by $[n]$ the set $\{1,\dots ,n\}$.

We write ${n \choose k}_0$ for the restricted binomial coefficients $${n \choose k}_0:=\left\{ \begin{array} {ll}
{n \choose k}, & \textrm{if $n\geq k$}; \\
\\
0, & \textrm{otherwise.} 
\end{array} \right.$$

Let $n\geq 1$ and $d\geq 1$ be arbitrary integers. Throughout the paper $L_n$ stands for the set of vectors $$L_n:=\{(\alpha_1,\ldots ,\alpha_n)\in {\mathbb N}^n:~  0\leq \alpha_i\leq i-1 \mbox{ for }1\leq i \leq n\},$$ whereas we write $M(n,d)$ for the following set of vectors: $$M(n,d):=\{(\alpha_1,\ldots ,\alpha_n)\in {\mathbb N}^n:~  0\leq \alpha_i\leq d-1 \mbox{ for }1\leq i \leq n\}.$$

In the following $S_n$ denotes the [*complete symmetric group*]{}.

Let $\pi=(a_1,a_2,\ldots ,a_n)$ be a permutation of the set $[n]$. Then the pair $(a_i,a_j)$ is an [*inversion*]{} of the permutation $\pi$, if $i<j$ and $a_i > a_j$. For example, the permutation $(3,1,4,2)$ has three inversions $(3,1)$, $(3,2)$, $(4,2)$.

Let $n\geq 1$, $0\leq t\leq {n \choose 2}$ be arbitrary integers. Define $$I_n(t):=|\{\pi\in S_n:~ \pi \mbox{ has }t\mbox{ inversions}\}|.$$

We give an explicit formula for the number of permutations of $[n]$ with $t$ inversions $I_n(t)$ and for the number of compositions of $t$ with at most $n$ parts, no one of which is greater than $d-1$, $H(n,d,t)$. E. Netto and D. Knuth gave explicit formulas for $I_n(t)$ only in the restricted case $t\leq n$, but as we know, it did not appear such general explicit formulas for these numbers in the literature. We use sophisticated methods in our proof as the theory of Gröbner basis and free resolutions.

We collect here some important fundamental properties of $I_n(t)$.\

([@C Section 6.4 Theorem D (IV)]) Let $n\geq 1$, $0\leq t \leq {n \choose 2}$ be arbitrary integers. Then $$I_n({n \choose 2}-t)=I_n(t).$$

(Muir, 1898, [@M2]) Denote by $$\label{gendef}
G_n(z):=\sum_{t=0}^{{n \choose 2}} I_n(t)z^t\in {{\mathbb Q}}[z]$$ the generating function of the numbers $I_n(t)$. Then $$\label{genfg2}
G_n(z)=\frac{(1-z)\cdot\ldots\cdot (1-z^n)}{(1-z)^n}=\prod_{i=1}^{n-1} \Big(\sum_{j=0}^i z^j\Big)$$ for each $n\geq 1$.

(Bourget, 1871, [@C Section 6.4 Theorem B]) The number $I_n(t)$ of permutations of $[n]$ with $t$ inversions satisfies the following recurrance relations: $$I_n(t)=\sum_{max(0,\ t-n+1)\leq j\leq t} I_{n-1}(j)$$ for each $n\geq 1$.\
$I(n,0)=1$ for each $n\geq 1$ and $I(0,k)=0$ if $k\geq 1$.\

E. Netto [@N p. 96 ] and D. Knuth [@Kn1 p. 15] gave the following explicit formula for $I_n(t)$ in the case $t\leq n$:

([@B p. 51 (2.51)]) Let $n\geq 1$, $0\leq t\leq n$ be integers. Then $$I_n(t)={n+t-1 \choose t}+\sum_{j=1}^{\infty} (-1)^j{n+t-u_j-j-1 \choose t-u_j-j}+$$ $$+\sum_{j=1}^{\infty}(-1)^j{n+t-u_j-1 \choose t-u_j},$$ where\
$$u_j:=\frac{j(3j-1)}{2}$$ are the pentagonal numbers.

Let $n,d\geq 1$ and $0\leq t\leq (d-1)n$ be arbitrary integers. Define the [*polynomial coefficients*]{} $H(n,d,t)$ as $$H(n,d,t):=|\{(\alpha_1, \ldots ,\alpha_n)\in {\mathbb N}^n:~ \sum_j \alpha_j =t,\ 0\leq \alpha_i\leq d-1\}|.$$ These are the numbers of compositions of $t$ with at most $n$ parts, no one of which is greater than $d-1$. We recall the following well–known properties of the numbers $H(n,d,t)$.

([@C p. 77, Ex. 16], [@A] and [@Ri p. 154, Ex. 11])\
The numbers $H(n,d,t)$ have the following recurrance relations: $$H(n,d,t)=H(n-1,d,t)+\ldots +H(n-1,d,t-d+1)$$ for each $n,d\geq 1$, $0\leq t\leq (d-1)n$.\
$H(n,d,0)=1$ for each $n,d\geq 1$ and $H(1,d,t)=1$ for each $d\geq 1$, $0\leq t\leq d-1$. $H(n,d,t)=0$ if either $t<0$ or $t>n(d-1)$.\

First L. Euler [@E] described the generating function of the polynomial coefficients.\

([@C Chapter 1, Ex. 16]) The numbers $H(n,d,t)$ have the following generating function: $$(1+x+\ldots +x^{d-1})^n=\sum_{t=0}^{n(d-1)} H(n,d,t)x^t.$$

Finally we introduce the notion of $q$-binomial coefficients.

The [*$q$-binomial coefficient*]{} $\Big[ { n \atop m} \Big]_q$ is a $q$-analog for the binomial coefficient, also called a Gaussian coefficient or a Gaussian polynomial. The $q$-binomial coefficient is given by $$\label{Gaussco}
 \Big[ { n \atop m}\Big]_q:=\frac{[n]_q!}{[n-m]_q!\cdot[m]_q!}$$ for $n,m \in {\mathbb N}$, where $[n]_q!$ is the $q$-factorial ([@K], p. 26) $$[n]_q!:=(1+q)\cdot (1+q+q^2)\cdots (1+q+q^2+\ldots +q^{n-1}).$$ Clearly we have $\Big[ { n \atop k} \Big]_q=\Big[ { n \atop n-k} \Big]_q$. If we substitute $q=1$ into (\[Gaussco\]), then this substitution reduces this definition to that of binomial coefficients.

The organisation of this paper is the following. In Section 2 we collected some preliminaries concerning Gröbner bases in polynomial rings and free resolutions of graded modules. In Section 3 we stated our main formulas about the numbers $I_n(t)$ and $H(n,d,t)$. In Section 4 we proved these formulas. Finally in Section 5 we gave a lattice-theoretic interpretation of these results.

Preliminaries
=============

Gröbner basis and Hilbert function
----------------------------------

We recall now some basic facts concerning Gröbner bases and standard monomials in polynomial rings.

Let $S$ and $R$ stand for the polynomial rings ${\mathbb Q}[x_1,\ldots ,x_n]$ and ${\mathbb Q}[x_0,\ldots ,x_n]$, respectively.

We denote by $S_{\leq t}$ the vector space of polynomials $f\in S$ of total degree at most $t$, together with $0$.

We say that a total order $\prec$ on the monomials of $S$ is a [*term order*]{}, if 1 is the minimal element of $\prec$, and $uw\prec vw$ holds for any monomials $u,v,w$ with $u\prec v$. Two important term orders are the lexicographic order $\prec_l$ and the deglex order $\prec _{dl}$. The lex order is similar to the order of words in the dictionary. Let $u=x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}$ and $v=x_1^{j_1}x_2^{j_2}\cdots x_n^{j_n}$ be two monomials. Then $u$ is smaller than $v$ with respect to lex iff $i_k<j_k$ holds for the smallest index $k$ such that $i_k\not=j_k$. Similarly, $u$ is smaller than $v$ with respect to deglex iff either $\deg (u)< \deg (v)$, or $\deg(u)=\deg(v)$ and $u\prec_l v$. We have $x_n\prec x_{n-1}\prec\ldots \prec
x_1$, for both lex and deglex.

A [*degree–compatible*]{} term order orders first by total degree: if $\mbox{deg}(u)<\mbox{deg}(v)$, then $u \prec v$. For example, the deglex order is a degree–compatible term order, whereas lex is not.

The [*leading monomial*]{} ${\rm lm}(f)$ of a nonzero polynomial $f\in S$ is the largest (with respect to $\prec$) monomial which appears with nonzero coefficient in $f$ when written as a linear combination of different monomials.

Let $I$ be an ideal of $S$. A finite subset $G\subseteq I$ is a [*Gröbner basis*]{} of $I$ if for every $f\in I$ there exists a $g\in G$ such that ${\rm lm}(g)$ divides ${\rm lm}(f)$. Since $\prec $ is a well founded order, it can be shown that $G$ is actually a basis of $I$, i.e., $G$ generates $I$ as an ideal of $S$. The following Theorem is very fundamental.

([@CCS Chapter 1, Corollary 3.12] or [@AL Corollary 1.6.5, Theorem 1.9.1]) Every nonzero ideal $I$ of $S$ has a Gröbner basis.

A Gröbner basis $\{ g_1,\ldots ,g_m\}$ of $I$ is [*reduced*]{} if the coefficient of ${\rm lm}(g_i)$ is 1, and no nonzero monomial in $g_i$ is divisible by any ${\rm lm}(g_j)$, $j\not= i$. By a theorem of Buchberger ([@AL Theorem 1.8.7]) a nonzero ideal has a unique reduced Gröbner basis.

A monomial $w\in S$ is called a [*standard monomial for $I$*]{} if it is not a leading monomial of any $f\in I$. Let ${\rm Sm}(I,\prec)$ stand for the set of all standard monomials of $I$ with respect to the term-order $\prec$ over ${\mathbb Q}$. The definition and existence of Gröbner bases ([@CCS Chapter 1, Section 4]) implies that the set ${\rm Sm}(I,\prec)$ is a basis of the ${\mathbb Q}$-vector-space $S/I$ for all nonzero ideal $I$.

Let ${\mbox{$\cal V$}}\subseteq {\mathbb Q}^n$ be a finite set of points. To study the polynomial functions on ${\mbox{$\cal V$}}$, it is natural to consider the ideal $I({\mbox{$\cal V$}})$ corresponding to ${\mbox{$\cal V$}}$: $$I({\mbox{$\cal V$}}):=\{f\in S:~f(v)=0 \mbox{ whenever } v\in {\mbox{$\cal V$}}\}.$$

Recall that a polynomial $h\in R$ is [*homogeneous*]{} of total degree $d$, if every term appearing in $h$ has total degree exactly $d$. We denote by $R_t$ the vector space of homogeneous polynomials $f\in R$ of degree $t$, together with $0$.

Let $g(x_1,\ldots ,x_n)\in S$ be a polynomial of total degree $d$. We can expand $g$ as the sum of its homogeneous components $g=\sum_{i=0}^d g_i$, where $g_i$ has total degree $i$. Then $$g^h(x_0,\ldots ,x_n):=\sum_{i=0}^d g_i(x_1,\ldots ,x_n)x_0^{d-i}\in R$$ is a homogeneous polynomial of total degree $d$ in $R$. We say that $g^h$ is the [*homogenization*]{} of $g$.

An ideal $J\unlhd R$ is said to be [*homogeneous*]{}, if for each $h\in J$, the homogeneous components $h_i$ of $h$ are in $J$ as well. It can be shown easily ([@CLO Chapter 8 , Theorem 3.2]) that $J$ is a homogeneous ideal iff $J$ is generated by homogeneous polynomials.

Let $I\unlhd S$ be an arbitrary ideal in $S$. We define the [*homogenization of $I$*]{} to be the ideal $$I^h:=\langle f^h:~ f\in I\rangle\subseteq R,$$ where $f^h$ denotes the homogenization of the polynomial $f$. It is easy to verify that the homogenization $I^h$ is a homogeneous ideal in $R$ for any ideal $I\unlhd S$.

\[homogen\] ([@CLO Chapter 8, Theorem 4.4]) Let $I\unlhd S$ be an ideal of the polynomial ring $S$. Suppose that ${\mbox{$\cal G$}}=\{g_1,\ldots ,g_k\}$ is a Gröbner basis of $I$ with respect to a degree–compatible term order $\prec$. Then the homogenization of ${\mbox{$\cal G$}}$, ${\mbox{$\cal G$}}^{h}:=\{g_1^h,\ldots ,g_k^h \}$ is a Gröbner basis of the homogeneous ideal $I^h \unlhd R$.

Let $I\unlhd S$ be an arbitrary ideal of $S$. We define the [*affine Hilbert function*]{} of $S/I$ as $$h_{S/I}^a(t)=\mbox{dim}_{{\mathbb Q}}\ S_{\leq t} / (S_{\leq t}\cap I).$$

The following Theorem connects the affine Hilbert function to certain sets of standard monomials.

(Macaulay, [@CLO Chapter 9, Proposition 3.4]) \[stdmon\] Let $\prec$ be an arbitrary degree–compatible term order on the monomials of $S$. Then $$h_{S/I}^a(t)=|\{x^{\alpha}\in \mbox{Sm}(I,\prec):~ \mbox{deg}(x^{\alpha})\leq t \}|.$$

Let $J\unlhd R$ be a homogeneous ideal. The [*projective Hilbert function*]{} $h_{R/J}^p(t)$ of the quotient ring $R/J$ is $$h_{R/J}^p(t)=\mbox{dim}_{{\mathbb Q}}\ R_t /(R_t\cap J).$$ We can discover a strong connection between the affine Hilbert function of an ideal $I$ of $S$ and the projective Hilbert function of the homogenization $I^h$.

\[Hilfg\] ([@CLO Chapter 9 Theorem 3.12]) Let $I\unlhd S$ be an ideal of $S$. Then $h_{R/I^{h}}^p(t)=h_{S/I}^a(t)$ for all $t\geq 0$.

Finally we use the following terminology. If $x^{\alpha}\in R$ (respectively $S$) is an arbitrary monomial and $F\in R$ (respectively $S$) is an arbitrary polynomial, then we denote by $[x^{\alpha}]F$ the coefficient of $x^{\alpha}$ in $F$.

Free resolutions of graded modules
----------------------------------

We collect here some basic facts from the theory of free resolutions.

First we give a natural grading structure on the ring $R={\mathbb Q}[x_0,\ldots ,x_n]$. This comes from the direct sum decomposition $$R=\bigoplus_{s\geq 0} R_s$$ into the additive subgroups $R_s={\mathbb Q}[x_0,\ldots ,x_n]_s$, consisting of the homogeneous polynomials of total degree $s$, together with $0$.

We introduce some terminology for describing free resolutions.

We say that $M$ over $R$ is a [*graded module*]{} with a family of subgroups $\{M_t:~ t\in {{\mathbb Z}}\}$ of the additive group, where $M_t$ are the homogeneous elements of degree $t$, if we can write $M$ in the form $$M=\bigoplus_{t\in {\mathbb Z}} M_t$$ and $$R_sM_t \subseteq M_{s+t}$$ for all $s\geq 0$ and $t\in {\mathbb Z}$. If $M$ is finitely generated, then $M_t$ are finite dimensional vector spaces over ${\mathbb Q}$.

Let $M$ be a graded $R$-module and let $d \in {\mathbb Z}$ be an arbitrary integer. Let $$M(d):=\bigoplus_{t \in {\mathbb Z}} M(d)_t,$$ where $M(d)_t:=M_{d+t}$. Then $M(d)$ is again a graded $R$-module.

We can consider graded free modules of the form $R(d_1)\oplus \ldots \oplus R(d_n)$ for any integers $d_1, \ldots , d_n$. We call these free modules the [*twisted graded free modules*]{}.

Let $M,N$ be graded modules over $R$. Then a $\phi:M \longrightarrow N$ homomorphism is a [*graded homomorphism*]{} of degree $d$, if $\phi(M_t) \subseteq N_{t+d}$ for all $t\in {\mathbb Z}$. If $M$ is a graded $R$–module, then a [*graded resolution*]{} of $M$ is a resolution of the form $$0\longrightarrow F_n \longrightarrow \ldots \longrightarrow F_1 \longrightarrow M \longrightarrow 0,$$ where each $F_l$ is a twisted graded free module and each homomorphism $\phi_l:F_l \longrightarrow F_{l-1}$ is a graded homomorphism of degree zero.\
The following Theorem is fundamental in the theory of free resolutions.

[**Graded Hilbert Syzygy Theorem**]{} ([@CLO2 Chapter 6, Theorem 3.8]) Every finitely generated $R$–module has a finite graded resolution of length at most $n$.

Suppose that $$\label{gradd}
0\longrightarrow F_n \longrightarrow \ldots \longrightarrow F_1 \longrightarrow M \longrightarrow 0$$ is a graded resolution. We say that the resolution (\[gradd\]) is [*minimal*]{} iff $\phi_l:F_l \longrightarrow F_{l-1}$ takes the standard basis of $F_l$ to a minimal generating set of $im(\phi_l)$ for each $l\geq 1$. It can be shown that any two minimal graded resolutions of $M$ are isomorphic.

If $M$ is a finitely generated graded $R$–module, then we define the Hilbert function $H_M(t)$ by $$H_M(t):=\mbox{dim}_{{\mathbb F}}\ M_t.$$

Let $I\unlhd R$ be a homogeneous ideal of $R$. Then it is easy to show that $I$ has a natural graded module structure, set $I_t:=I\cap R_t$. Similarly the quotient ring $R/I$ has a natural grading $(R/I)_t:=R_t/I_t$. Thus it comes out from the definitions that if $M:=R/I$ is the quotient graded $R$-module, then $H_M(t)=h_{R/I}^p(t)$ for each $t\geq 0$.

We can compute easily the Hilbert function of the module $R(d)$.

Let $d\in {\mathbb Z}$ be an arbitrary integer. Then $H_{R(d)}(t)={t+d+n \choose n}$ for each $t\in {\mathbb Z}$.

The following Proposition connects the computation of the Hilbert function to the dimension of the free graded modules in a graded resolution of $M$.

\[alter\] ([@CLO2 Chapter 6, Theorem 4.4]) Let $M$ be a graded $R$–module. Then for any graded free resolution of $M$ $$0\longrightarrow F_n \longrightarrow \ldots \longrightarrow F_1 \longrightarrow M \longrightarrow 0$$ we have $$H_M(t)=\sum_{j=1}^k (-1)^j \mbox{dim}_{{\mathbb Q}}\ (F_j)_t.$$

We can easily compute the Hilbert function of the twisted graded free modules $\bigoplus_{i=1}^{m} R(d_{i})$.

\[twist\] Let $F$ be the twisted graded free module $\bigoplus_{i=1}^{m} R(d_{i})$. Then $$H_{F}(t)=\sum_{i=1}^{m} {n+d_{i}+t \choose n}.$$

Proposition \[alter\] and Proposition \[twist\] implies the following Theorem.

\[Hilbert\] ([@CLO2 Chapter 6, Proposition 4.7]) Let $M$ be a graded $R$-module with the graded free resolution $$0\longrightarrow F_n \longrightarrow \ldots \longrightarrow F_1 \longrightarrow M \longrightarrow 0.$$ If each $F_j$ is the twisted free graded module $F_j=\bigoplus_{i=1}^{m_j} R(d_{i,j})$, then $$H_M(t)=\sum_{j=1}^k (-1)^j \sum_{i=1}^{m_j} {n-d_{i,j}+t \choose n}.$$

We call the numbers $m_j$ the [*Betti numbers*]{} of the module $M$.

Let ${\mbox{$\cal V$}}\subseteq {\mathbb P}^n$, $\mbox{dim}\ {\mbox{$\cal V$}}=k$ be a $k$-dimensional variety in the projective space ${\mathbb P}^n$. The variety ${\mbox{$\cal V$}}$ is called to a [*complete intersection*]{}, if its homogeneous ideal $I({\mbox{$\cal V$}})\subseteq R$ is generated by $n-k$ elements of $R$.

If ${\mbox{$\cal V$}}\subseteq {\mathbb P}^n$ is a complete intersection, then we understand very clearly the minimal graded resolution of the ideal $I({\mbox{$\cal V$}})$. We call the minimal graded resolution of complete intersections the [*Koszul complex*]{}.

\[Koszul\] (see [@JH Example 13.16]) Let ${\mbox{$\cal V$}}\subseteq {\mathbb P}^n$, $\mbox{dim}\ {\mbox{$\cal V$}}=n-k$ be a complete intersection of hypersurfaces defined by the polynomials $G_1, \ldots ,G_k$, where $G_i$ has degree $d_i$.

Let $M:=I({\mbox{$\cal V$}})$ denote the graded module of the ideal $I({\mbox{$\cal V$}})$. Then the terms in the minimal graded free resolution of $M$ are $$F_i=\bigoplus_{1\leq a_1<\ldots <a_i\leq k} R(-d_{a_1}-\ldots -d_{a_i})$$ for each $1\leq i\leq n$. The Betti numbers $m_i$ are the binomial coefficients ${n \choose i}$. The homomorphism $\phi_i:F_i \longrightarrow F_{i-1}$ sends the generator $e_{a_1,\ldots ,a_n}$ of the module $F_i$ to the sum $\sum_j (-1)^j G_{a_j}\cdot e_{a_1,\ldots , \widehat{a_j}, \ldots, a_i}$.

The main results
================

In Theorem \[main1\] and Theorem \[main2\] we give explicit formulas for the sum of the numbers $H(n,d,t)$ and $I_n(t)$.

\[main1\] Let $n,d\geq 1$, $0\leq t\leq n(d-1)$ be arbitrary integers. Then

$$\sum_{i=0}^t H(n,d,i)=\sum_{i=0}^n (-1)^i {n \choose i}{t-di+n \choose n}_0.$$

\[main2\] Let $n\geq 1$, $0\leq t \leq {n \choose 2}$ be arbitrary integers. Then

$$\sum_{i=0}^t I_n(i)={n+t \choose t}+\sum_{j=1}^n \sum_{k={j+1 \choose 2}}^{n+1 \choose 2} (-1)^j  [q^{k-{j+1 \choose 2}}]\Big[ { n \atop j} \Big]_q\cdot {t-k+n \choose n}_0,$$

where $$[q^{k-{j+1 \choose 2}}]\Big[ { n \atop j} \Big]_q$$ denotes the coefficient of $q^{k-{j+1 \choose 2}}$ in the Gaussian polynomial $\Big[ { n \atop j} \Big]_q$.

The following two Corollaries are our main results.

\[maincor1\] Let $n\geq 1$, $d\geq 1$ and $0\leq t\leq n(d-1)$ be integers. Then $$H(n,d,t)=\sum_{i=0}^n (-1)^i {n \choose i}\Big({t-di+n \choose n}_0-{t-di+n-1 \choose n}_0\Big).$$

\[maincor2\] Let $n\geq 1$, $0\leq t\leq {n\choose 2}$ be integers. For $1\leq j\leq k$ and ${j+1 \choose 2}\leq k\leq {n+1 \choose 2}$ we denote by $$C(n,j,k):=[q^{k-{j+1 \choose 2}}]\Big[ { n \atop j} \Big]_q$$ the coefficient of $q^{k-{j+1 \choose 2}}$ in the Gaussian polynomial $\Big[ { n \atop j} \Big]_q$. Then $$I_n(t)={n+t \choose t}-{n+t-1 \choose t-1}+$$ $$\sum_{j=1}^n \sum_{k={j+1 \choose 2}}^{n+1 \choose 2} (-1)^j  C(n,j,k) \Big({t-k+n \choose n}_0-{t-k+n-1 \choose n}_0\Big).$$

Proofs
======

[**Proof of Theorem \[main1\]:**]{}\
Denote by ${\mbox{$\cal V$}}$ the [*$d$-box*]{} ${\mbox{$\cal V$}}:= [d]^n\subseteq {{\mathbb Q}}^n$ . We can describe easily the reduced Gröbner basis and the standard monomials of the ideal $I({\mbox{$\cal V$}})$.

\[doboz\] Let $\prec$ be an arbitrary term order on the monomials of ${\mathbb Q}[x_1,\dots,x_n]$. Then the reduced Gröbner basis of the ideal $I({\mbox{$\cal V$}})$ is $${\mbox{$\cal G$}}=\{\prod_{j=1}^d (x_i-j):~ 1\leq i\leq n\}$$ and the set of standard monomials is $$\mbox{Sm}(I({\mbox{$\cal V$}}),\prec)=\{x_1^{\alpha_1}\cdot\ldots\cdot x_n^{\alpha_n}:~ 0\leq \alpha_i\leq d-1\}.$$

Hence we infer from Theorem \[stdmon\] that $$h_{S/I({\mbox{$\cal V$}})}^a(m)=|\{x^{\alpha}\in \mbox{Sm}(I({\mbox{$\cal V$}}),\prec_{dl}):~ \mbox{deg}(x^{\alpha})\leq m \}|=$$ $$\label{vektor}
=|\{(\alpha_1,\ldots ,\alpha_n)\in M(n,d):~ \sum_i \alpha_i\leq m\}|.$$ It is easy to verify that the ideal $I({\mbox{$\cal V$}})$ is a complete intersection in the affin space ${{\mathbb A}}^n$. Then we infer from Theorem \[homogen\] that the homogeneous ideal $I({\mbox{$\cal V$}})^h$ is a complete intersection in the projective space ${{\mathbb P}}^n$, too.

Thus we can describe the minimal graded free resolution $$\label{graddd}
0\longrightarrow F_n \longrightarrow \ldots \longrightarrow F_1 \longrightarrow M \longrightarrow 0,$$ where $M:=I({\mbox{$\cal V$}})^h$ is the graded module of the homogenization $I({\mbox{$\cal V$}})^h$. The resolution (\[graddd\]) is the Koszul complex by Theorem \[Koszul\]. Here $d_i=d$ for each $1\leq i\leq n$.

We infer from Theorem \[Hilfg\] that $$h_{R/I^h}^p(t)=h_{S/I}^a(t)$$ for each $t\geq 0$. Hence using the exact sequence $$0\longrightarrow I \longrightarrow R \longrightarrow R/I \longrightarrow 0$$ we get that $$h_{R/I^h}^p(t)=h_R^p(t)-h_{I^h}^p(t).$$ Finally Theorem \[Hilbert\] and Theorem \[Koszul\] implies that $$\label{vegso}
h_{S/I}^a(t)=h_{R/I^h}^p(t)=h_R^p(t)-h_{I^h}^p(t)=\sum_{i=0}^n (-1)^i {n \choose i}{t-di+n \choose n}_0.$$ Theorem \[maincor1\] follows from the equations (\[vektor\]) and (\[vegso\]).

[**Proof of Theorem \[main2\]:**]{}\
Let $${\mbox{$\cal V$}}:=\{\pi(1,\ldots ,n) :~ \pi\in S_n\}\subseteq {{\mathbb Q}}^n$$ denote the orbit in ${\mathbb Q}^n$ of the vector $(1,\ldots ,n)$ under the permutation action of the complete symmetric group $S_n$.

We prove Theorem \[main2\] in the following three steps.\
1. First we give a combinatorial proof of the equality $$\sum_{i=0}^t I_n(i)=|\{(\alpha_1,\ldots ,\alpha_n)\in L_n:~ \sum_i \alpha_i\leq t\}|.$$ 2. Next we prove using Gröbner basis theory that $$h_{S/I({\mbox{$\cal V$}})}^a(t)=|\{(\alpha_1,\ldots ,\alpha_n)\in L_n:~ \sum_i \alpha_i\leq t \}|.$$ 3. Finally we prove using the theory of free resolutions that $$h_{S/I({\mbox{$\cal V$}})}^a(t)={n+t \choose t}+\sum_{j=1}^n \sum_{k={j+1 \choose 2}}^{n+1 \choose 2} (-1)^j  [q^{k-{j+1 \choose 2}}]\Big[ { n \atop j} \Big]_q\cdot {t-k+n \choose n}_0,$$ where $$[q^{k-{j+1 \choose 2}}]\Big[ { n \atop j} \Big]_q$$ denotes the coefficient of $q^{k-{j+1 \choose 2}}$ in the Gaussian polynomial $\Big[ { n \atop j} \Big]_q$.\
1. It follows from (\[genfg2\]) that $G_n(z)$, the generating function of $I_n(t)$, has the following expression:

$$\label{genfg3}
G_n(z)=\prod_{i=1}^{n-1} \Big(\sum_{j=0}^i z^j\Big).$$

Consider the following polynomial $P$ in $n$ variables: $$\label{genfg4}
P(x_1,\ldots ,x_n):=\prod_{i=2}^{n} \Big(\sum_{j=0}^{i-1} x_i^j\Big)\in {\mathbb Z}[x_1, \ldots ,x_n].$$ Then the equations (\[genfg3\]) and (\[genfg4\]) yield to the equation $$\label{pgenfg}
P(z,\ldots ,z)=G_n(z).$$ The definition of the polynomial $P$ implies that $$\label{genfg5}
P(x_1,\ldots ,x_n)=\sum_{\alpha\in L_n} x^{\alpha},$$ where if $\alpha$ is the vector $(\alpha_1,\ldots , \alpha_n)$, then we use the notation $x^{\alpha}:=x_1^{\alpha_1}\cdots x_n^{\alpha_n}$.

This implies that $$|\{(\alpha_1,\ldots ,\alpha_n)\in L_n:~ \sum_i \alpha_i\leq t \}|=$$ $$=\sum_{j=1}^t |\{x^{\alpha}:~ \alpha\in L_n,\ \mbox{deg}(x^{\alpha})=j \}|=$$ $$\label{Psum}
 =\sum_{j=1}^t |\{x^{\alpha}:~ [x^{\alpha}]P=1,\  \mbox{deg}(x^{\alpha})=j\}|,$$ where we used the expansion (\[genfg5\]) in the equality (\[Psum\]). Clearly we have $$\sum_{j=1}^t |\{x^{\alpha}:~ [x^{\alpha}]P=1,\   \mbox{deg}(x^{\alpha})=j\}|=\sum_{j=1}^t [z^j]P(z,\ldots ,z),$$ where $[z^j]P(z,\ldots ,z)$ denotes the coefficient of $z^j$ in the polynomial $P(z,\ldots ,z)$. Finally we infer from (\[gendef\]) and (\[pgenfg\]) that $$\sum_{j=1}^t [z^j]P(z,\ldots ,z)=\sum_{j=1}^t [z^j] G_n(z)=\sum_{j=1}^t I_n(j).$$

2\. We recall the definition of the complete and elementary symmetric polynomials. Let $i$ be a nonnegative integer. Write $$h_i(x_1,\ldots,x_n)=\sum_{a_1+\cdots +a_n=i}x_1^{a_1}x_2^{a_2}\cdots
x_n^{a_n}$$ for the $i$-th complete symmetric polynomial. Clearly $h_i\in {{\mathbb Q}}[x_1,\ldots ,x_n]$ is the sum of all monomials of total degree $i$.

For $0\leq i\leq n$ we write $\sigma_i$ for the $i$-th elementary symmetric polynomial: $$\sigma_i(x_1,\ldots,x_n)=\sum_{S\subset [n],~|S|=i} x_S.$$ $\sigma_i\in {\mathbb Q}[x_1,\ldots ,x_n]$ is the sum of all squarefree monomials of degree $i$ in the variables $x_1,\ldots,x_n$.

For $1\leq k\leq n$ we introduce the polynomials $f_k\in S$ as follows: $$f_k=\sum_{i=0}^k (-1)^i h_{k-i}(x_k,x_{k+1},\ldots,x_n)\sigma_i
(1,\ldots,n).$$

Clearly $f_k\in {\mathbb Q}[x_k,x_{k+1},\ldots, x_n]$. Moreover, $\mbox{deg}(f_k)=k$ and the leading monomial of $f_k$ is $x_k^k$ with respect to any term order $\prec$ for which $x_1\succ x_2\succ \ldots \succ x_n$.

G. Hegedüs and L. Rónyai [@HNR Theorem 2.2] described the reduced Gröbner basis and the standard monomials of $I({\mbox{$\cal V$}})$ with respect to any term order on the monomials of ${{\mathbb Q}}[x_1,\dots,x_n]$.

\[perm\] Let $\prec$ be an arbitrary term order on the monomials of ${\mathbb Q}[x_1,\dots,x_n]$ such that $x_n\prec \ldots \prec x_1$. Then the reduced Gröbner basis of $I({\mbox{$\cal V$}})$ is $$\{f_i:~ 1\leq i \leq n\}.$$ Moreover the set of standard monomials is $$\label{standard1}
\mbox{\em Sm}(I({\mbox{$\cal V$}}),\prec)=\{x_1^{\alpha_1}\ldots x_n^{\alpha_n}:~ 
0\leq \alpha_i \leq i-1, ~\mbox{\em for}~1\leq i\leq n \}.$$

Hence we infer from Theorem \[stdmon\] that $$h_{S/I({\mbox{$\cal V$}})}^a(t)=|\{x^{\alpha}\in \mbox{Sm}(I({\mbox{$\cal V$}}),\prec_{dl}):~ \mbox{deg}(x^{\alpha})\leq t \}|=$$

$$=|\{(\alpha_1,\ldots ,\alpha_n)\in L_n:~ \sum_i \alpha_i\leq t\}|$$

for each $t\geq 0$.\
3. Theorem \[perm\] implies that the zero–dimensional ideal $I({\mbox{$\cal V$}})$ is a complete intersection in the affin space ${{\mathbb A}}^n$. But then Theorem \[homogen\] gives that the homogenization $I({\mbox{$\cal V$}})^h$ is a complete intersection in the projective space ${{\mathbb P}}^n$. Let $M:=I({\mbox{$\cal V$}})^h$ denote the graded module of the homogenization $I({\mbox{$\cal V$}})^h$. Then the minimal graded resolution $$0\longrightarrow F_n \longrightarrow \ldots \longrightarrow F_1 \longrightarrow M \longrightarrow 0,$$ is the Koszul complex, where $d_i=i$ for each $1\leq i \leq n$.

Let $n\geq 1$, $1\leq j\leq n$ and $1\leq k\leq {n+1 \choose 2}$ be arbitrary integers. Define the numbers $$D(n,j,k):=|\{I\subseteq [n]:~ |I|=j,\ \sum_{i\in I} i=k\}|.$$ Clearly $D(n,j,k)=0$ if $1\leq k< {j+1 \choose 2}$ for a fixed $1<j\leq n$.

Theorem \[Hilbert\] and Theorem \[Koszul\] implies that $$h_{S/I}^a(t)=h_{R/I^h}^p(t)=h_R^p(t)-h_{I^h}^p(t)=$$ $$\label{Hilbert2}
={n+t \choose t}+\sum_{j=1}^n \sum_{k={j+1 \choose 2}}^{n+1 \choose 2} (-1)^j  D(n,j,k)\cdot {t-k+n \choose n}_0.$$

We give in the following a simpler expression for the numbers $D(n,j,k)$.

\[Gauss\] ([@B Chapter 2, Theorem 2.25]) Let $n\geq 1$, $1\leq j\leq n$ and $1\leq k \leq {n+1 \choose 2}$. Then $$\label{Dgauss}
D(n,j,k)=[q^{k-{j+1 \choose 2}}]\Big[ { n \atop j} \Big]_q,$$ where $[q^{k-{j+1 \choose 2}}]\Big[ { n \atop j} \Big]_q$ denotes the coefficient of $q^{k-{j+1 \choose 2}}$ in the Gaussian polynomial $\Big[ { n \atop j} \Big]_q$.

We include here a proof of Theorem \[Gauss\] for the reader’s convenience.

[**Proof of Theorem \[Gauss\]:**]{}

We can recognise the numbers $D(n,j,k)$ as the coefficients in certain two–variables polynomials.

\[coeff\] Let $n\geq 1$ be an arbitrary integer. Define $$Q_n(t,q):=\prod_{i=1}^n (1+tq^i)\in {{\mathbb Z}}[t,q].$$ Then $$D(n,j,k)=[q^kt^j]Q_n(t,q),$$ the coefficient of $[q^kt^j]$ in the polynomial $Q_n(t,q)$, for each $1\leq j\leq k$ and $1\leq k\leq {n+1 \choose 2}$.

This is clear from the definition of the polynomial $Q_n(t,q)$ and the numbers $D(n,j,k)$.

The following well–known Theorem is a special case of the $q$-binomial Theorem ([@G Theorem 1.1] and [@C Chapter 2, Exercise 11]).

([**Cauchy binomial Theorem**]{}) \[Cauchy\] Let $n\geq 1$ be an arbitrary integer. Then $$Q_n(t,q)=\prod_{i=1}^n (1+tq^i)=\sum_{m=0}^n t^m q^{\frac{m(m+1)}{2}}\Big[ { n \atop m} \Big]_q.$$

Finally we conclude from Theorem \[coeff\] and Theorem \[Cauchy\] that $$D(n,j,k)=[q^kt^j]Q_n(t,q)=[q^kt^j]\Big(\sum_{m=0}^n t^m q^{\frac{m(m+1)}{2}}\Big[ { n \atop m} \Big]_q\Big)=$$ $$=[q^kt^j]\Big(t^jq^{\frac{j(j+1)}{2}}\Big[ { n \atop j} \Big]_q\Big),$$ which implies (\[Dgauss\]). $\Box$

Now we finish the proof of Theorem \[main2\]. From equations (\[Hilbert2\]) and (\[Dgauss\]) we infer that $$h_{S/I}^a(t)={n+t \choose t}+\sum_{j=1}^n \sum_{k={j+1 \choose 2}}^{n+1 \choose 2} (-1)^j  D(n,j,k)\cdot {t-k+n \choose n}_0=$$ $$={n+t \choose t}+\sum_{j=1}^n \sum_{k={j+1 \choose 2}}^{n+1 \choose 2} (-1)^j  [q^{k-{j+1 \choose 2}}]\Big[ { n \atop j} \Big]_q\cdot {t-k+n \choose n}_0.$$

Concluding remarks
==================

We give a nice interpretation of this problem and its solution in lattice theory.

We say that a $P$ poset is [*graded of rank $n$*]{} if every maximal chain of $P$ has the same length. In this case we can give a unique rank function $\rho:P \to \{0, \ldots ,n\}$ such that $\rho(x)=0$ if $x$ is a minimal element of $P$, and $\rho(y)=\rho(x)+1$ if $y$ covers $x$ in $P$. If $\rho(x)=i$, then we say that $x$ has [*rank*]{} $i$.

If $P$ is a graded poset of rank $n$ and has $t_i$ elements of rank $i$ then the polynomial $$G(P,q)=\sum_{i=0}^n t_iq^i\in {\mathbb Z}[q]$$ is called the [*rank-generating function*]{} of $P$.

Let $n>0$ be an integer. We make the set of all positive divisors of $n$ easily into a poset $D_n$ by defining $i\preceq j$ in $D_n$ if $j$ is divisible by $i$. It is easy to verify that $D_n$ with this partial ordering $\preceq$ becomes a graded poset. The rank of $P$ is the number of prime divisors of $n$, counting with multiplicity.

Let $P_n$ denote the partially ordered set of all $n$-permutations in which $p\leq q$ if either $p$ can be obtained from $q$ by a series of transpositions, or $p=q$. Then $\leq$ is called the Bruhat order on $S_n$ and it is easy to verify that $(P_n,\leq)$ is again a graded poset.

Let $p_1, \ldots ,p_{n}$ denote the first $n$ prime numbers in increasing order. Then it can be shown easily that the poset $(P_n,\leq)$ is isomorphic with the poset $(D_k,\preceq)$, where $k=p_1^1 \cdot \ldots \cdot p_{n-1}^{n-1}$. Thus $I_n(t)$ is the number of elements of rank $t$ in $D_k$. Similarly, if $\ell:=p_1^{d-1}\cdot \ldots \cdot p_n^{d-1}$, then $H(n,d,t)$ is the number of elements of rank $t$ in $D_{\ell}$.

Thus we determined the rank generating function of the ranked poset $D_n$ for certain $n$’s. It would be very interesting to determine the rank generating function of $D_n$ in the general case, when $n$ is an arbitrary integer.

R. S. Deodhar and M. Srinivasan [@DS] defined a statistic on involutions, which they called [*weight*]{}.

Let $F(2n)$ denote the set of all fixed point free involutions of $[2n]$.

A $2$-cycle is a set consisting of two distinct positive integers. We write $[i,j]$ for an arc with $i<j$. The [*span*]{} of an arc $[i,j]$ is defined as $\mbox{span}[i,j]=j-i-1$. A pair of disjoint arcs $[i,j]$ and $[k,l]$ is a [*crossing*]{} if $i<j<k<l$ or $k<i<l<j$.

We can write the involutions in [*standard representations*]{}, which is in increasing order in their initial points.

Let $\delta$ be an arbitrary involution. The numbers of arcs in $\delta$ is denoted by $|\delta|$. The [*crossing number*]{} of $\delta$, denoted by $c(\delta)$, is the number of pairs of arcs of $\delta$ that are crossings. Define the [*weight*]{} of $\delta$, denoted by $\mbox{wt}(\delta)$, as follows: $$\mbox{wt}(\delta):=\Big(\sum_{[i,j]\in \delta}   \mbox{span}[i,j]\Big)-c(\delta).$$

Let $\delta=[a_1,b_1][a_2,b_2]\ldots [a_n,b_n]\in F(2n)$ be an arbitrary involution. Then we say that $\tau$ is obtained from $\delta$ by an [*interchange*]{}, written $\delta \sim \tau$, if there exist $1\leq i<j \leq n$ such that\
\
(i) $\tau$’s standard representation is obtained from $\delta$ by exchanging $b_i$ and $a_j$, or\
(ii) $\tau$’s standard representation is obtained from $\delta$ by exchanging $b_i$ and $b_j$.

We say that $\tau$ is obtained from $\delta$ by a [*weight increasing interchange*]{}, if $\delta \sim \tau$ and $\mbox{wt}(\delta)<\mbox{wt}(\tau)$.

They defined a partial order on $F(2n)$ as follows: Let $\delta,\tau\in F(2n)$. Then $\delta \leq \tau$ if $\tau$ can be obtained from $\delta$ by a sequence of (zero or more) weight increasing interchanges.

R. S. Deodhar and M. Srinivasan [@DS Theorem 1.3] proved that $(F(2n), {\leq})$ is a graded poset of rank $2{n\choose 2}$ for each $n\geq 1$. The rank of $\delta \in F(2n)$ is given by $\mbox{wt}(\delta)$ and the rank generating function of this poset $F(2n)$ is the following: $$G(F(2n),q)=[1]_q[3]_q\ldots [2n-1]_q.$$ We think that it would be interesting to apply our methods for this poset and we can give explicit formulas for the rank generating function of $F(2n)$, but we shall treat this topic in a future paper.

[**Acknowledgements.**]{} I am indebted to Jonathan Farley for his useful remarks.

[MM]{}

W. W. Adams and P. Loustaunau, [*An Introduction to Gröbner Bases,*]{} American Mathematical Society, 1994.

G. E. Andrews, “Euler’s exemplum memorabile inductionis fallacis’ and $q$-trinomial coefficients”, J. Amer. Math. Soc. [**3**]{} (1990) 653–668.

M. Bona, Combinatorics of permutations, Chapman & Hall/CRC, 2004.

L. Comtet, [*Advanced combinatorics*]{}, D. Reidel Publishing Company, 1974.

A. M. Cohen, H. Cuypers and H. Sterk (eds.), [*Some Tapas of Computer Algebra,*]{} Springer, 1999.

D. Cox, J. Little, D. O’Shea, [*Ideals, varieties, and algorithms*]{}, Springer, 1992.

D. Cox, J. Little, D. O’Shea, [*Using Algebraic Geometry*]{}, Springer, 2005.

R. S. Deodhar, M: Srinivasan, A Statistic on Involutions, [*J. of Alg. Comb.*]{} [**13**]{} (2001), 187–198.

L. Euler, On the expansion of the power of any polynomial $(1+x+x^2+x^3+x^4+etc)$ (electronically http://arxiv.org/abs/math.HO/0505425).

V. J. W. Guo, The $q$-binomial theorem and two symmetric $q$-identities. [*Electron. J. Combin.*]{} [**10**]{} (2003), Research Paper 34.

G. Hegedűs, A. Nagy, L. Rónyai, Gröbner bases for permutations and oriented trees, [*Annales Univ. Sci. Budapest*]{}, Sect. Comp. [**23**]{} (2004), 137–148.

J. Harris, [*Algebraic Geometry. A First Course*]{}, Springer, 1992.

Koepf, W. [*Hypergeometric Summation: An Algorithmic Approach to Summation and Special Function Identities*]{}, Vieweg, 1998.

D. E, Knuth, [*The art of computer programming, Volume 3, Sorting and searching,*]{} Addison-Wesley, 1973.

B. H. Margolius, Permutations with inversions. [*Journal of Integer Sequences*]{} [**4**]{}, (2001), no. 2, Article 01.2.4 (electronic).

Muir, “On a simple term of a determinant” [*Proc. Royal S. Edingburgh*]{} [**21**]{} (1898-9), 441–477

E. Netto, [*Lehrbuch der Kombinatorik*]{}, Teubner, 1927.

J. Riordan, [*An Introduction to Combinatorial Analysis*]{}, John Wiley and Sons, 1958.
