A Generating Function for Numbers of Insets

Milan Janjić Department of Mathematics and Informatics University of Banja Luka Banja Luka, 78000 Republic of Srpska, Bosnia and Herzegovina

                        agnus@blic.net

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.

1 Introduction

Janjić and Petković [1] defined the notion of an inset of a set in the following way. Let n and q_{1}, …, 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, …, n), X_{i} having q_{i} elements, and a block Y with m elements. Furthermore, let Q_{n} denote the set {q_{1}, …, q_{n}}.

An (n + k)-inset of X is a subset S of X such that |S| = n + k and S ∩ X_{i} ≠ ∅ for all i. The number of (n + k)-insets of X is denoted by \binom{m,n}{k,Q_{n}}. In the case n = 1, when Q_{1} = \{q_{1}\}, we write \binom{m,n}{k,q_{1}}.

In this paper, we derive a generating function for the sequence \binom{m,n}{k,Q_{n}}, (m = 0, 1, …). 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.

2 The generating function

Theorem 1. Let n be a positive integer, Q_{n} = {q_{1}, …, q_{n}} a set of n positive integers, and k a nonnegative integer such that k − ∑_{i=1}^{n}(q_{i} − 1) ≥ 0.

Then we have

\frac{∏_{i=1}^{n}(1 − x^{q_{i}})}{(1 − x)^{n+k+1}} = ∑_{i=0}^{∞} \binom{i + s, n}{k, Q_{n}}x^{i},  (1)

where s = k − ∑_{i=1}^{n}(q_{i} − 1).

Proof. We prove formula (1) by induction on n.

Base case: n = 1:

Now formula (1) becomes

\frac{1 − x^{q_{1}}}{(1 − x)^{k+2}} = ∑_{i=0}^{∞} \binom{i + s, 1}{k, q_{1}}x^{i}.  (2)

From the binomial series

\frac{1}{(1 − x)^{k+1}} = ∑_{i=0}^{∞} \binom{k + i}{k}x^{i},

we obtain

\frac{1 − x^{q_{1}}}{(1 − x)^{k+2}} = ∑_{i=0}^{∞} \binom{k + i}{k}x^{i} · ∑_{i=0}^{q_{1}−1} x^{i}.  (3)

We define b_{i} = 1, (i = 0, …, q_{1} − 1), and b_{i} = 0 otherwise. Multiplying the series on the right-hand side of equation (3), we obtain

\frac{1 − x^{q_{1}}}{(1 − x)^{k+2}} = ∑_{i=0}^{∞} [∑_{j=0}^{i} b_{j}\binom{k + i − j}{k}] x^{i}.  (4)

Let a_{i} denote the coefficient of x^{i} in (4). To complete the proof of (2) it suffices to show that a_{i} = \binom{i+s,1}{k,q_{1}} for every i.

We proceed by considering two cases: i ≤ q_{1} − 1 and i > q_{1} − 1.

1. First assume that i ≤ q_{1} − 1. We have

a_{i} = \binom{k + i}{k} + \binom{k + i − 1}{k} + ⋯ + \binom{k}{k}.

Using the horizontal recurrence for the binomial coefficients, we conclude that

a_{i} = \binom{k + i + 1}{k + 1}.

Since s = k − q_{1} + 1 we have

a_{i} = \binom{s + q_{1} + i}{k + 1}.

According to formula (6) from [1], we have

\binom{s + i, 1}{k, q_{1}} = \binom{s + i + q_{1}}{k + 1} − \binom{s + i}{k + 1}.

Since i ≤ q_{1} − 1, we have \binom{s+i}{k+1} = \binom{k−q_{1}+1+i}{k+1} = 0, which implies

a_{i} = \binom{s + i, 1}{k, q_{1}}, for all i = 0, …, q_{1} − 1.  (5)

2. Now assume that i > q_{1} − 1. Then we have

a_{i} = \binom{k + i}{k} + \binom{k + i − 1}{k} + ⋯ + \binom{k + i − q_{1} + 1}{k},

which, by the same horizontal recurrence relation used earlier, implies that

a_{i} = \binom{k + i + 1}{k + 1} − \binom{s + i}{k + 1}.

Using again the formula (6) in [1], we conclude that

a_{i} = \binom{s + i, 1}{k, q_{1}}, for all i ≥ q_{1}.  (6)

Hence, from formulae (5) and (6), we conclude that (2) is true. This completes the proof of the base case: n = 1.

Inductive step: Assume that formula (1) holds for n ≥ 1 and deduce that it holds for n + 1 as well.

In other words, assuming that Q_{n+1} = Q_{n} ∪ {q_{n+1}} and that s̄ = k − ∑_{i=1}^{n+1}(q_{i} − 1) ≥ 0, we need to derive the following formula from (1):

\frac{∏_{i=1}^{n+1}(1 − x^{q_{i}})}{(1 − x)^{n+k+2}} = ∑_{i=0}^{∞} \binom{i + s̄, n + 1}{k, Q_{n+1}}x^{i}.  (7)

Let s = k −∑_{i=1}^{n}(q_{i} −1). It follows from the definition of s̄ and the fact that q_{n+1} −1 ≥ 0 that s = s̄ + q_{n+1} − 1 ≥ 0.

Therefore we can apply the induction hypothesis and multiply both sides of formula (1) by

\frac{1 − x^{q_{n+1}}}{1 − x} = ∑_{i=0}^{q_{n+1}−1} x^{i},

to obtain

\frac{∏_{i=1}^{n+1}(1 − x^{q_{i}})}{(1 − x)^{n+k+2}} = ∑_{i=0}^{∞} \binom{i + s, n}{k, Q_{n}}x^{i} · ∑_{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

a_{i} = ∑_{j=0}^{i} b_{j}\binom{i + s − j, n}{k, Q_{n}},  (8)

where b_{j} = 1, (0 ≤ j ≤ q_{n+1} − 1), and b_{j} = 0 otherwise.

Consider the following two cases.

1. First assume that i < q_{n+1} − 1. We have

a_{i} = ∑_{j=0}^{i} \binom{i + s − j, n}{k, Q_{n}}.

It follows that

a_{i} = ∑_{j=0}^{q_{n+1}−1} \binom{i + s − j, n}{k, Q_{n}} − ∑_{j=i+1}^{q_{n+1}−1} \binom{i + s − j, n}{k, Q_{n}}.  (9)

The term \binom{i+s−j, n}{k, Q_{n}}, (j = i+1, …), according to its definition in [1], equals the number of (n + k)-insets of a set having

i + s − j + ∑_{j=1}^{n} q_{j} < ∑_{j=1}^{n} q_{j} + s = ∑_{j=1}^{n+1} q_{j} + s̄ − 1,

elements. Since n + k = ∑_{i=1}^{n+1} q_{i} + 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 \binom{i+s−j,n}{k,Q_{n}} = 0, (j ≥ i + 1), and therefore the second sum in formula (9) equals 0.

Hence,

a_{i} = ∑_{j=0}^{q_{n+1}−1} \binom{i + s − j, n}{k, Q_{n}}.

Note that s = s̄ + q_{n+1} − 1. Introducing a new index of summation t = q_{n+1} − 1 − j we obtain

a_{i} = ∑_{t=0}^{q_{n+1}−1} \binom{i + s̄ + t, n}{k, Q_{n}}.

Applying formula (12) from [1], we get

a_{i} = \binom{i + s̄, n + 1}{k, Q_{n+1}},

and the assertion (7) is true.

2. Now assume that i ≥ q_{n+1} − 1. In this case, according to the fact that b_{j} = 0, (j > q_{n+1} − 1), in (8), we immediately have

a_{i} = ∑_{j=0}^{q_{n+1}−1} \binom{i + s − j, n}{k, Q_{n}},

and the formula (7) follows in the same way as in the preceding case.

This completes the proof of the inductive step and shows that the statement of the theorem is true.

3 Some applications

We shall first interpret equation (1) in terms of integer partitions. In what follows we write Q instead of Q_{n}.

Let p(Q, i), (i > 0) denote the number of partitions of i, the parts of which belong to the set Q = {q_{1}, q_{2}, …, q_{n}}. We put p(Q, 0) = 1.

Similar as for the standard partitions we consider the expression S = \frac{1}{∏_{i=1}^{n}(1−x^{q_{i}})}. Then S can be written as

S = (1 + x^{q_{1}} + x^{2q_{1}} ⋯) ⋯ (1 + x^{q_{n}} + x^{2q_{n}} + ⋯).

It follows that

S = ∑_{(a_{1},...,a_{i})} x^{a_{1}q_{1}+···+a_{n}q_{n}},

where a_{i} ≥ 0, (i = 1, 2, …, n). We conclude that the coefficient of x^{k} in the preceding sum equals p(Q, k).

We conclude that ∏_{i=1}^{n}(1 − x^{q_{i}}) is the inverse of the power series ∑_{i=0}^{∞} p(Q, i)x^{i}.

We write equation (1) in the form

∏_{i=1}^{n}(1 − x^{q_{i}}) = ∑_{i=0}^{n+k+1}(−1)^{i}\binom{n + k + 1}{i}x^{i} · ∑_{i=0}^{∞} \binom{i + s, n}{k, Q}x^{i},

The degree of the polynomial on the left-hand side of the preceding equation is N = ∑_{i=1}^{n} q_{i}. It follows that

∏_{i=1}^{n}(1 − x^{q_{i}}) = ∑_{i=0}^{N} [∑_{j=0}^{i}(−1)^{i−j}\binom{n + k + 1}{i − j}\binom{j + s, n}{k, Q}] x^{i}.  (10)

If we let

∏_{i=1}^{n}(1 − x^{q_{i}}) = ∑_{i=0}^{∞} a_{i}x^{i},

where

a_{i} = ∑_{j=0}^{i}(−1)^{i−j}\binom{n + k + 1}{i − j}\binom{j + s, n}{k, Q}, (i = 0, 1, …, N),  (11)

and a_{i} = 0 otherwise, then ∑_{i=0}^{∞} a_{i}x^{i} is the inverse of ∑_{i=0}^{∞} p(Q, i)x^{i}.

We thus obtain

Theorem 2. The numbers p(Q, i) satisfy the following system of homogeneous linear equations

\begin{matrix}a_{0}p(Q, 0) = 1, \\ ∑_{j=0}^{i} a_{i−j}p(Q, j) = 0, (i = 1, 2, …, N). \end{matrix}

Next, we derive an explicit formula for coefficients of expansion of the Euler product function ∏_{i=1}^{∞}(1 − x^{i}).

Proposition 3. Assume that

∏_{i=1}^{∞}(1 − x^{i}) = ∑_{i=0}^{∞} b_{i}x^{i}.  (12)

Then,

b_{n} = ∑_{j=0}^{n}(−1)^{n−j}\binom{\frac{n^{2}+n+2}{2}}{n − j}\binom{j, n}{\frac{n^{2}−n}{2}, Q}.  (13)

Proof. We consider the particular case of equation (10), when q_{i} = i, (i = 1, 2, …, n), and s = 0. In this case, we have k = ∑_{i=1}^{n}(i − 1) = \frac{n^{2}−n}{2}, and N = \frac{n^{2}+n}{2}.

The formula (10) becomes

∏_{i=1}^{n}(1 − x^{i}) = ∑_{i=0}^{\frac{n^{2}+n}{2}} [∑_{j=0}^{i}(−1)^{i−j}\binom{\frac{n^{2}+n+2}{2}}{i − j}\binom{j, n}{\frac{n^{2}−n}{2}, Q}] x^{i}.

In particular, taking i = n in the right-hand side, we obtain (13).

Note that the coefficient of x^{n} in the expansions ∏_{i=1}^{n}(1 − x^{i}) and ∏_{i=1}^{∞}(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.

The Euler pentagonal number theorem may be stated in terms of insets in the following way:

Proposition 4. Let n be a positive integer. Then,

∑_{j=0}^{n}(−1)^{n−j}\binom{\frac{n^{2}+n+2}{2}}{n − j}\binom{j, n}{\frac{n^{2}−n}{2}, Q} = \begin{cases}(−1)^{t}, & if n = \frac{t(3t±1)}{2}; \\ 0, & otherwise. \end{cases}

Remark 5. Formula (13) concerns the sequence \underline{A010815} of pentagonal numbers. In this sense, Theorem 1 may be considered as an extension of the Euler pentagonal number theorem.

The series on the right-hand side of (12) is the inverse of the series ∑_{i=0}^{∞} p(i)x^{i}, where p(0) = 1, and p(i) is the number of partitions of i. We thus obtain

Proposition 6. The numbers of partitions satisfy the following system of homogeneous linear equations

∑_{j=0}^{i} b(j)p(i − j) = 0, (i = 1, 2, …),  (14)

and p(0) = b(0) = 1, where b’s are given by (13).

Remark 7. This proposition concerns the sequence \underline{A000041}.

Remark 8. If one could solve the system (14), one would obtain the formula for p(n). Since the system (14) 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{matrix}p(5) = −b(1)^{5} − 5b(1)^{3}b(2) − 3b(1)^{2}b(3) − 3b(1)b(2)^{2} + 2b(1)b(4) + 2b(2)b(3) − b(5) \\ b(5) = −p(1)^{5} − 5p(1)^{3}p(2) − 3p(1)^{2}p(3) − 3p(1)p(2)^{2} + 2p(1)p(4) + 2p(2)p(3) − p(5). \end{matrix}

Finally, as a consequence of Theorem 1, we derive an explicit formula for entries of the Mahonian triangle \underline{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

∏_{i=1}^{u} \frac{1 − x^{i}}{1 − x} .

In other words

∏_{i=1}^{u} \frac{1 − x^{i}}{1 − x} = ∑_{v=0}^{∞} T (u, v)x^{v}.  (15)

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 + ⋯ + (u − 1) = \frac{u^{2}−u}{2}. Hence T (u, v) = 0 for all v > \frac{u^{2}−u}{2}. Our next theorem determines the values for T (u, v), when v ≤ \frac{u^{2}−u}{2}.

Theorem 9. The entries T (u, v) of the Mahonian triangle satisfy the following equality

T (u, v) = ∑_{i=0}^{v}(−1)^{v−i}\binom{\frac{u^{2}−u+2}{2}}{v − i}\binom{i, u}{\frac{u^{2}−u}{2}, Q}, for all v = 0, 1, …, \frac{u^{2} − u}{2},

where Q = {1, 2, …, u}.

Proof. Note first that the generating function for the numbers T (u, v) can be written as

∏_{i=1}^{u} \frac{1 − x^{i}}{1 − x} = \frac{∏_{i=1}^{u}(1 − x^{i})}{(1 − x)^{u+k+1}} · (1 − x)^{k+1}.

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

Note first that the condition s ≥ 0, in Theorem 1, is satisfied. For q_{i} = i for all i = 1, …, u implies s = k − ∑_{i=1}^{u}(q_{i} − 1) = k − ∑_{i=1}^{u}(i − 1) = 0. It follows from formula (1) that

∏_{i=1}^{u} \frac{1 − x^{i}}{1 − x} = ∑_{i=0}^{∞} \binom{i, u}{\frac{u^{2}−u}{2}, Q}x^{i} · ∑_{i=0}^{\frac{u^{2}−u+2}{2}}(−1)^{i}\binom{\frac{u^{2}−u+2}{2}}{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

∑_{i=0}^{v}(−1)^{v−i}\binom{\frac{u^{2}−u+2}{2}}{v − i}\binom{i, u}{\frac{u^{2}−u}{2}, Q}.

The assertion of the theorem now follows from formula (15).

We also have

Corollary 10. For v > \frac{u^{2}−u}{2}, we have

∑_{i=0}^{v}(−1)^{v−i}\binom{\frac{u^{2}−u+2}{2}}{v − i}\binom{i, u}{\frac{u^{2}−u}{2}, Q} = 0.

References

[1] M. Janjić and B. Petković. A counting function generalizing binomial coefficients and some other classes of integers. J. Integer Sequences 17 (2014), Article 14.3.5.

[2] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 11P81. Keywords: partitions, Euler pentagonal number theorem, Mahonian number.

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

Received February 23 2014; revised versions received July 13 2014; September 4 2014. Published in Journal of Integer Sequences, September 4 2014.

Return to Journal of Integer Sequences home page.