<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf
A Generating Function for Numbers of Insets
}
\vskip 1cm
\large
Milan Janji\'c \\
Department of Mathematics and Informatics\\
 University of Banja Luka\\
Banja Luka, 78000\\
Republic of Srpska, Bosnia and Herzegovina\\
\href{mailto:agnus@blic.net}{\tt agnus@blic.net}\\
\end{center}

\vskip .2 in

\begin{abstract}
In a previous paper, we defined the notion of inset. In this paper,
we first derive a generating function for the number of insets in
terms of one of its parameters. Using this function, we connect
insets with some important classes of integers.

We first prove that the numbers of integer partitions satisfy a
system of homogeneous linear equations. Then we derive an explicit
formula for the coefficients of the Euler product function in
terms of the number of insets. As a consequence, we express the
Euler pentagonal number theorem in terms of insets.

Finally, we derive an explicit formula for the entries of the Mahonian
triangle.
\end{abstract}


\section{Introduction}
Janji\'c and Petkovi\'c \cite{mil}
defined the notion of an inset of a set in the following way.
Let $n$ and $q_1,\ldots,q_n$ be positive integers and $m$ and $k$ nonnegative integers.
Suppose that a set $X$ consists of $n$  blocks
$X_i,\;(i=1,2,\ldots,n),$ $X_i$ having $q_i$ elements, and a block
$Y$ with $m$ elements. Furthermore,
let $Q_n$ denote the set $\{q_1,\ldots,q_n\}$.

An $(n+k)$-inset of $X$ is a subset $S$ of $X$ such that $|S|=n+k$ and $S\cap X_i \neq\emptyset$ for all $i$.
The number of $(n+k)$-insets of $X$ is denoted by $m,n\choose k,Q_n$.
In the case $n=1$, when $Q_1=\{q_1\}$, we write $m,n\choose k,q_1$.

In this paper, we derive a generating function for the
sequence ${m,n\choose k,Q_n},\; (m=0,1,\ldots)$.   This function
connects the notion of insets with some well-known classes of
integers.

We first establish a connection with integer partitions by proving
that the numbers of partitions, with parts in a given set, satisfy
a system of homogeneous linear equations.

Then we derive an explicit formula for the coefficients of the Euler product
function in terms of insets. We also show that the Euler pentagonal number
theorem may be expressed in terms of insets.

Finally, we derive an explicit formula for the entries of the Mahonian
triangle. To our knowledge, such a formula  has not been put forward  until now.

\section{The generating function}
\begin{theorem}\label{MT}
Let $n$ be a positive integer,
$Q_n=\{q_1,\ldots,q_n\}$ a set of $n$ positive integers,
and $k$ a nonnegative integer such that $k-\sum_{i=1}^n(q_i-1)\geq 0$.

    Then we have
\begin{equation}\label{te}\frac{\prod_{i=1}^n(1-x^{q_i})}{(1-x)^{n+k+1}}=
\sum_{i=0}^\infty{i+s,n \choose k,Q_n}x^i,\end{equation}
where $s=k-\sum_{i=1}^n(q_i-1)$.
\end{theorem}
\begin{proof}
We prove formula $(\ref{te})$ by induction on $n$.

\bigbreak
\noindent {Base case:} $n=1$:

Now formula $(\ref{te})$ becomes
\begin{equation}\label{BS1}\frac{1-x^{q_1}}{(1-x)^{k+2}}=
\sum_{i=0}^\infty{i+s,1 \choose k,q_1}x^i.\end{equation}

From the binomial series
\[\frac{1}{(1-x)^{k+1}}=\sum_{i=0}^\infty{k+i\choose k}x^i,\]
we obtain
\begin{equation}\label{BS2}\frac{1-x^{q_1}}{(1-x)^{k+2}}=\sum_{i=0}^\infty{k+i\choose k}x^i\cdot\sum_{i=0}^{q_1-1}x^i.\end{equation}

We define  $b_i=1,\;(i=0,\ldots,q_1-1),$ and $b_i=0$ otherwise. Multiplying the series
on the right-hand side of equation $(\ref{BS2})$, we obtain
\begin{equation}\label{vj}
\frac{1-x^{q_1}}{(1-x)^{k+2}}=\sum_{i=0}^\infty\left[\sum_{j=0}^ib_j{k+i-j\choose
k}\right]x^i.\end{equation}

Let $a_i$ denote the coefficient of $x^i$ in  (\ref{vj}).
To complete the proof of $(\ref{BS1})$ it suffices to show that $a_i= {i+s,1 \choose k,q_1}$ for every $i$.

We proceed by considering two cases: $i\leq q_1-1$ and $i &gt; q_1-1$.

 \begin{enumerate}
 \item First assume that $i\leq q_1-1$.
 We have
\[a_i={k+i\choose k}+{{k+i-1\choose k}}+\cdots+{k\choose k}.\]
Using the horizontal recurrence for the binomial coefficients, we conclude that
\[a_i={k+i+1\choose k+1}.\]
Since $s=k-q_1+1$ we have \[a_i={s+q_1+i\choose k+1}.\]

According to formula (6) from \cite{mil}, we have
\[{s+i,1\choose k,\;q_1}={s+i+q_1\choose k+1}-{s+i\choose k+1}.\]


Since  $i\leq q_1-1,$ we have ${s+i\choose k+1}={k-q_1+1+i\choose k+1}=0,$ which implies

\begin{equation}\label{BS3}a_i={s+i,1\choose k,\;q_1}, \text{ for all } i=0,\ldots,q_1-1.\end{equation}


\item Now assume that $i&gt;q_1-1$. Then we have
\[a_i={k+i\choose k}+{{k+i-1\choose k}}+\cdots+{k+i-q_1+1\choose k},\]
which, by the same horizontal recurrence relation used earlier,
implies that
\[a_i={k+i+1\choose k+1}-{s+i\choose k+1}.\]
Using again the formula (6) in \cite{mil}, we conclude that
\begin{equation}\label{BS4}
a_i={s+i,1\choose k,\;q_1},\text{ for all } i\geq q_1.
\end{equation}

\end{enumerate}

Hence, from formulae (\ref{BS3}) and (\ref{BS4}), we conclude that (\ref{BS1}) is true. This completes the proof of the base case: $n=1$.

\bigbreak
\noindent {Inductive step:} Assume that formula (\ref{te}) holds for $n\geq 1$ and deduce that it holds for $n+1$ as well.

In other words, assuming that $Q_{n+1}=Q_n\cup \{q_{n+1}\}$ and that
$\bar{s}=k-\sum_{i=1}^{n+1}(q_i-1)\geq 0$, we need to derive the
following formula from
(\ref{te}):

\begin{equation}\label{IS1}\frac{\prod_{i=1}^{n+1}(1-x^{q_i})}{(1-x)^{n+k+2}}=
\sum_{i=0}^\infty{i+\bar{s},n+1 \choose k,Q_{n+1}}x^i.
\end{equation}

Let $s=k-\sum_{i=1}^{n}(q_i-1)$. It follows from the definition of
$\bar{s}$ and the fact that $q_{n+1}-1\geq 0$ that
$s=\bar{s}+q_{n+1}-1\geq 0$.

Therefore we can apply the induction hypothesis and multiply both sides of formula (\ref{te}) by
\[\frac{1-x^{q_{n+1}}}{1-x}=\sum_{i=0}^{q_{n+1}-1}x^i,\]
to obtain
\[\frac{\prod_{i=1}^{n+1}(1-x^{q_i})}{(1-x)^{n+k+2}}=
\sum_{i=0}^\infty{i+s,n\choose k,\;Q_n}x^{i}\cdot \sum_{i=0}^{q_{n+1}-1}x^i.\]

We let $a_i$ denote the coefficient of $x^i$ on the right-hand side of this equation.
We have
\begin{equation}\label{eex}a_i=\sum_{j=0}^ib_j{i+s-j,n\choose k,Q_n},\end{equation}
where $b_j=1,\;(0\leq j\leq q_{n+1}-1),$ and $b_j=0$ otherwise.

Consider the following  two cases.
\begin{enumerate}
\item First assume that $i&lt; q_{n+1}-1$.
 We have
\[a_i=\sum_{j=0}^i{i+s-j,n\choose k,Q_n}.\]
It follows that
\begin{equation}\label{IS2}
a_i=\sum_{j=0}^{q_{n+1}-1}{i+s-j,n\choose k,Q_n}-\sum_{j=i+1}^{q_{n+1}-1}{i+s-j,n\choose
k,Q_n}.
\end{equation}
The term ${i+s-j,\;n\choose k,\;Q_n},\;(j=i+1,\ldots),$
according to its definition in \cite{mil}, equals the number of
$(n+k)$-insets of a set having
\[i+s-j+\sum_{j=1}^nq_j&lt;\sum_{j=1}^nq_j+s=\sum_{j=1}^{n+1}q_j+\bar{s}-1,\] elements. Since
$n+k=\sum_{i=1}^{n+1}q_i+\bar{s}-1,$ the above inequality would mean that we have an $(n+k)$-inset in a set with less than $n+k$ elements, which is impossible. This implies that ${i+s-j,n\choose k,Q_n}=0,(j\geq i+1),$ and therefore the second sum in formula (\ref{IS2}) equals $0$.

Hence,\[a_i=\sum_{j=0}^{q_{n+1}-1}{i+s-j,n\choose k,Q_n}.\]
Note that $s=\bar{s}+q_{n+1}-1$. Introducing a new index of summation $t = q_{n+1}-1-j$ we obtain
\[a_i=\sum_{t=0}^{q_{n+1}-1}{i+\bar{s}+t,n\choose k,Q_n}.\]
Applying formula (12) from \cite{mil}, we get
\[a_i={i+\bar{s},n+1\choose k,Q_{n+1}},\]
and the assertion (\ref{IS1}) is true.

\item Now assume that $i\geq q_{n+1}-1$.
In this case, according to the fact that $b_j=0,\;(j&gt;q_{n+1}-1),$ in (\ref{eex}),  we immediately  have
\[a_i=\sum_{j=0}^{q_{n+1}-1}{i+s-j,n\choose k,Q_n},\]
and the formula (\ref{IS1}) follows in the same way as in the preceding case.

\end{enumerate}
This completes the proof of the inductive step and shows that the statement of the theorem is true.
\end{proof}

\section{Some applications}

We shall  first interpret equation (\ref{te}) in terms of
integer partitions.
In what follows we write $Q$ instead of $Q_n$.

Let $p(Q,i),\;(i&gt;0)$ denote the number of
partitions of $i,$ the parts of which belong to the set  $Q=\{q_1,q_2,\ldots,q_n\}$. We put
$p(Q,0)=1$.

Similar as for the standard partitions we consider the expression  $S=\frac{1}{\prod_{i=1}^n(1-x^{q_i})}$.
Then $S$ can be written as
\[S=(1+x^{q_1}+x^{2q_1}\cdots)\cdots(1+x^{q_n}+x^{2q_n}+\cdots).\]
It follows that
\[S=\sum_{(a_1,\ldots,a_i)}x^{a_1q_1+\cdots+a_nq_n},\]
where $a_i\geq 0,\;(i=1,2,\ldots,n)$. We conclude that the coefficient of $x^k$ in the preceding sum equals $p(Q,k)$.

We conclude that $\prod_{i=1}^n(1-x^{q_i})$ is the inverse of the
power series $\sum_{i=0}^\infty p(Q,i)x^i$.

We write equation (\ref{te}) in the form
\[\prod_{i=1}^n(1-x^{q_i})=\sum_{i=0}^{n+k+1}(-1)^i{n+k+1\choose i}x^i\cdot
\sum_{i=0}^\infty{i+s,n\choose k,Q}x^i,\]


The degree of the polynomial on the left-hand side of the
preceding equation is $N=\sum_{i=1}^nq_i$. It follows that
\begin{equation}\label{kur}\prod_{i=1}^n(1-x^{q_i})=\sum_{i=0}^{N}\left[\sum_{j=0}^i
(-1)^{i-j}{n+k+1\choose i-j}{j+s,n\choose
k,Q}\right]x^i.\end{equation}
If we let \[\prod_{i=1}^n(1-x^{q_i})=\sum_{i=0}^\infty a_ix^i,\]
where
\begin{equation}\label{ai}a_i=\sum_{j=0}^i
(-1)^{i-j}{n+k+1\choose i-j}{j+s,n\choose
k,Q},\;(i=0,1,\ldots,N),\end{equation} and $a_i=0$ otherwise, then
$\sum_{i=0}^\infty a_ix^i$ is the inverse of $\sum_{i=0}^\infty
p(Q,i)x^i$.

We thus obtain

\begin{theorem}\label{op}
 The numbers $p(Q,i)$ satisfy the following system of
homogeneous linear equations
\[\begin{array}{c}
a_0p(Q,0)=1,\\
\sum_{j=0}^ia_{i-j}p(Q,j)=0,\;(i=1,2,\ldots,N).
\end{array}\]
\end{theorem}


Next, we derive an explicit formula for coefficients of expansion of the Euler product function $\prod_{i=1}^\infty (1-x^i)$.
\begin{proposition} Assume that
\begin{equation}\label{ppt}\prod_{i=1}^\infty(1-x^i)=\sum_{i=0}^\infty b_ix^i.\end{equation}
Then,
\begin{equation}\label{ai1}b_n=\sum_{j=0}^n
(-1)^{n-j}{\frac{n^2+n+2}{2}\choose n-j}{j,n\choose
\frac{n^2-n}{2},Q}.\end{equation}
\end{proposition}
\begin{proof}
We consider the particular case of equation (\ref{kur}), when
$q_i=i,\;(i=1,2,\ldots,n),$ and $s=0$. In this case, we have
$k=\sum_{i=1}^n(i-1)=\frac{n^2-n}{2},$ and $N=\frac{n^2+n}{2}$.

 The formula (\ref{kur}) becomes
  \[\prod_{i=1}^n(1-x^i)=\sum_{i=0}^{\frac{n^2+n}{2}}\left[\sum_{j=0}^i
(-1)^{i-j}{\frac{n^2+n+2}{2}\choose i-j}{j,n\choose
\frac{n^2-n}{2},Q}\right]x^i.\] In particular, taking
$i=n$ in the right-hand side, we
obtain (\ref{ai1}).

Note that the coefficient of $x^n$ in the expansions $\prod_{i=1}^n(1-x^i)$ and $\prod_{i=1}^\infty(1-x^i)$ are the same, since the next factor $1-x^{n+1}$ that would be included in the finite product will keep all the terms of degree strictly less than $n+1$ the same.
\end{proof}
The  Euler pentagonal number theorem  may be stated in terms of
insets in  the following way:

\begin{proposition} Let $n$ be a positive integer. Then,
\[\sum_{j=0}^n(-1)^{n-j}{\frac{n^2+n+2}{2}\choose n-j}{j,n\choose \frac{n^2-n}{2},Q}=
\begin{cases}(-1)^t,&amp;\text{ if }n=\frac{t(3t\pm 1)}{2};\\
0, &amp;\text{otherwise.}
\end{cases}\]
\end{proposition}

\begin{remark} Formula (\ref{ai1}) concerns the sequence \seqnum{A010815}
 of pentagonal numbers. In this sense, Theorem {\ref{MT}} may be considered as an extension
 of the Euler pentagonal number theorem.
\end{remark}
The series on the right-hand side of (\ref{ppt}) is the  inverse
of the series $\sum_{i=0}^\infty p(i)x^i,$ where $p(0)=1,$ and
$p(i)$ is the number of partitions of $i$. We thus obtain
\begin{proposition} The numbers of partitions satisfy the following system of homogeneous linear equations
\begin{equation}\label{jp}\sum_{j=0}^ib(j)p(i-j)=0,\;(i=1,2,\ldots),\end{equation} and
$p(0)=b(0)=1,$ where $b$'s are given by (\ref{ai1}).
\end{proposition}
\begin{remark} This proposition concerns the sequence \seqnum{A000041}.
\end{remark}
\begin{remark} If one could solve the system (\ref{jp}), one would
obtain the formula for $p(n)$.
Since the system (\ref{jp}) is symmetric with respect to $b$'s and
$p$'s, the expression of $p(n)$ in terms of $b$'s is the same as
the expression of $b(n)$ in terms of $p$'s.

For example,
\[\begin{array}{c}p(5)=-b(1)^5-5b(1)^3b(2)-3b(1)^2b(3)-3b(1)b(2)^2+2b(1)b(4)+2b(2)b(3)-b(5)\\
b(5)=-p(1)^5-5p(1)^3p(2)-3p(1)^2p(3)-3p(1)p(2)^2+2p(1)p(4)+2p(2)p(3)-p(5)
.\end{array}\]

\end{remark}


Finally, as a  consequence of Theorem~\ref{MT}, we derive an explicit
formula for entries of the Mahonian triangle \seqnum{A008302},
which we denote by $T(u,v)$.

The number $T(u,v)$ is defined to be the number of permutations of $S_u$ which have exactly $v$ inversions.

It is well known that the generating function for the numbers
$T(u,v)$ is
\[\prod_{i=1}^u\frac{1-x^i}{1-x}.\]


In other words
\begin{equation}\label{GFMN}
\prod_{i=1}^u\frac{1-x^i}{1-x}=\sum_{v=0}^{\infty} T(u,v)x^v.\end{equation}
On the other hand, the product on the left hand side of the previous formula is a polynomial in $x$ and its degree is $1+\cdots +(u-1)=\frac{u^2-u}{2}$. Hence $T(u,v)=0$ for all $v&gt;\frac{u^2-u}{2}$. Our next theorem determines the values for $T(u,v),$ when $v\leq \frac{u^2-u}{2}$.

\begin{theorem} The entries $T(u,v)$ of the Mahonian triangle satisfy the following equality
\[T(u,v)=\sum_{i=0}^v(-1)^{v-i}{\frac{u^2-u+2}{2}\choose{v-i}}{i,u\choose
\frac{u^2-u}{2},Q},\text{ for all } v=0,1,\ldots,\frac{u^2-u}{2}, \]
where $Q=\{1,2,\ldots,u\}$.
\end{theorem}
\begin{proof}
Note first that the generating function for the numbers $T(u,v)$
can be written as
\[\prod_{i=1}^u\frac{1-x^i}{1-x}=\frac{\prod_{i=1}^u(1-x^i)}{(1-x)^{u+k+1}}\cdot
(1-x)^{k+1}.\]

Now we can apply Theorem \ref{MT} to the right-hand side of the above equality. We assume that $k=\frac{u^2-u}{2}$.

Note first that the condition $s\geq 0$, in Theorem \ref{MT}, is satisfied. For $q_i=i$ for all $i=1,\ldots,u$ implies
$s=k-\sum_{i=1}^{u}(q_i-1)=k-\sum_{i=1}^{u}(i-1)=0$.
It follows from formula (\ref{te}) that
  \[\prod_{i=1}^u\frac{1-x^i}{1-x}=\sum_{i=0}^\infty{i,u\choose
 \frac{u^2-u}{2},Q}x^i\cdot\sum_{i=0}^{\frac{u^2-u+2}{2}}(-1)^i{\frac{u^2-u+2}{2}\choose
 i}x^i.\]
As explained earlier, the degree of the polynomial on the left-hand side of the preceding
equation equals $\frac{u^2-u}{2}$.
It is easy to see that the coefficient of $x^v$ on the right hand side equals
\[\sum_{i=0}^v(-1)^{v-i}{\frac{u^2-u+2}{2}\choose v-i}{i,u\choose \frac{u^2-u}{2},Q}.\]
The assertion of the theorem now follows from formula (\ref{GFMN}).
\end{proof}

We also have
\begin{corollary} For $v&gt;\frac{u^2-u}{2},$ we have
\[\sum_{i=0}^v(-1)^{v-i}{\frac{u^2-u+2}{2}\choose v-i}{i,u\choose \frac{u^2-u}{2},Q}=0.\]
\end{corollary}

\begin{thebibliography}{9}
\bibitem{mil}
M. Janji\'c and B. Petkovi\'c.
\newblock A counting function generalizing binomial coefficients
and some other classes of integers.
\newblock {\em J. Integer Sequences} {\bf 17} (2014),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Janjic/janjic45.html}{Article 14.3.5}.

\bibitem{slo}
N. J. A. Sloane.
\newblock The On-Line Encyclopedia of Integer Sequences,
\url{http://oeis.org}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary
05A10; Secondary 11P81.

\noindent \emph{Keywords: } partitions, Euler pentagonal number
theorem, Mahonian number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000041},
\seqnum{A008302}, and
\seqnum{A010815}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 23 2014;
revised versions received  July 13 2014; September 4 2014.
Published in {\it Journal of Integer Sequences}, September 4 2014.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
</pre></body></html>