Counting on rectangular areas
Counting on Rectangular Areas
Milan Janjić,
Faculty of Natural Sciences and mathematics,
Banja Luka, Republic of Srpska, Bosnia and Herzegovina.
Counting on Rectangular Areas
Abstract
In the first section of this paper we prove a theorem for the number
of columns of a rectangular area that are identical to the given one. A
special case, concerning (0, 1)-matrices, is also stated.
In the next section we apply this theorem to derive several combina-
torial identities by counting specified subsets of a finite set. This means
that the obtained identities will involve binomial coefficients only. We
start with a simple equation which is, in fact, an immediate consequence
of Binomial theorem, but it is derived independently of it. The second
result concerns sums of binomial coefficients. In a special case we obtain
one of the best known binomial identity dealing with alternating sums.
Klee’s identity is also obtained as a special case as well as some formu-
lae for partial sums of binomial coefficients, that is, for the numbers of
Bernoulli’s triangle.
1 A counting theorem
The set of natural numbers {1, 2, . . . , n} will be denoted by [n], and by |X | will
be denoted the number of elements of the set X.
For the proof of the main theorem we need the following simple result:
(−1)|I| = 0, (1)
where I run over all subsets of [n] (empty set included). This may be easily
proved by induction or using Binomial theorem. But the proof by induction
makes all further investigations independent even of Binomial theorem.
Let A be an m× n rectangular matrix filled with elements which belong to
a set Ω.
By the i-column of A we shall mean each column of A that is equal to
[c1, c2, . . . , cm]
T , where c1, c2, . . . , cm of Ω are given. We shall denote the number
of i-columns of A by νA(c) or simply by ν(c).
For I = {i1, i2, . . . , ik} ⊂ [m], by A(I) will be denoted the maximal number
of columns j of A such that
aij 6= cj , (i ∈ I).
http://arxiv.org/abs/0704.0851v1
We also define
A(∅) = n.
Theorem 1. The number ν(c) of i-columns of A is equal
ν(c) =
(−1)|I|A(I), (2)
where summation is taken over all subsets I of [m].
Proof. Theorem may be proved by the standard combinatorial method, by
counting the contribution of each column of A in the sum on the right side of
We give here a proof by induction. First, the formula will be proved in the
case ν(c) = 0 and ν(c) = n. In the case ν(c) = n it is obvious that for I 6= ∅ we
have A(I) = 0, which implies
(−1)|I|A(I) = n+
I 6=∅
(−1)|I|A(I) = n.
In the case ν(c) = 0 we use induction on n. If n = 1 then the matrix
A has only one column, which is not equal c. It yields that there exists i0 ∈
{1, 2, . . . ,m} such that ai0,1 6= ci0 . Denote by I0 the set of all such numbers.
Then A(I) = 1 if and only if I ⊂ I0. From this and (1) we obtain
(−1)|I|A(I) =
(−1)|I| = 0.
Suppose now that the formula is true for matrices with n columns and that
A has n+ 1-columns, and νA(c) = 0. Omitting the first column, the matrix B
with n columns remains. If I0 is the same as in the case n = 1, then
(−1)|I|A(I) =
I 6⊂I0
(−1)|I|A(I) +
(−1)|I|A(I) =
I 6⊂I0
(−1)|I|B(I) +
(−1)|I|(B(I) + 1) =
(−1)|I|B(I) +
(−1)|I| = 0,
since the first sum is equal zero by the induction hypothesis, and the second by
For the rest of the proof we use induction on n again. For n = 1 the matrix
A has only one column which is either equal c or not. In both cases theorem is
true, from the preceding.
Suppose that theorem holds for n, and that the matrix A has n+1 columns.
We may suppose that ν(c) ≥ 1. Omitting one of the i-columns we obtain the
matrix B with n columns. By the induction hypothesis theorem is true for B.
On the other hand it is clear that A(I) = B(I) for each nonempty subset I.
Furthermore A has one i-column more then B, which implies
ν(c) = νA(c) = νB(c) + 1 = 1 +
(−1)|I|B(I) =
= 1 + n+
I 6=∅
(−1)|I|B(I) = 1 + n+
I 6=∅
(−1)|I|A(I).
ν(c) =
(−1)|I|A(I),
and theorem is proved.
If the number A(I) does not depend on elements of the set I, but only on
its number |I| then the equation(2) may be written in the form
ν(c) =
(−1)i
A(i), (3)
where |I| = i.
Our object of investigation will be (0, 1) matrices. Let c be the i- column of
a such matrix A. Take I0 ⊆ [m], |I0| = k such that
1 i ∈ I0
0 i 6∈ I0
Then the number A(I) is equal to the number of columns of A having 0’s in
the rows labelled by the set I ∩ I0, and 1’s in the rows labelled by the set I \ I0.
Suppose that the number A(I) depends only on |I ∩ I0|, |I \ I0|. If we denote
|I ∩ I0| = i1, |I \ I0| = i2, A(I) = A(i1, i2), then (2) may be written in the form
ν(c) =
(−1)i1+i2
A(i1, i2). (5)
2 Counting subsets of a finite set
Suppose that a finite set X = {x1, x2, . . . , xn} is given. Label by 1, 2, . . . , 2
n all
subsets of X arbitrary and define an n× 2n matrix A in the following way
aij =
1 if xi lies in the set labelled by j
0 otherwise
. (6)
Take I0 ⊆ [n], |I0| = k, and form the submatrix B of A consisting of those
rows of A which indices belong to I0. Let c be arbitrary i-column of B. Define
= {i ∈ I0 : ci = 1},
I ′′0 = {i ∈ I0 : ci = 0}
. (7)
The number ν(c) is equal to the number of subsets that contain the set
{xi, i ∈ I
0}, and do not intersect the set {xi : i ∈ I
0 }. There are obviously
ν(c) = 2n−k,
such sets.
Furthermore, if I ⊆ I0 then the number B(I) is equal to the number of
subsets that contain the set {xi : i ∈ I ∩ I
}, and do not meet the set {xi : i ∈
I ∩ I ′0}. It is clear that there are
B(I) = 2n−|I|
such subsets, so that the formula (2) may be applied. It follows
2n−k =
(−1)i
2n−i.
Thus we have
Proposition 2.1. For each nonnegative integer k holds
(−1)i
2k−i.
Note 2.1. The preceding equation is a trivial consequence of Binomial theorem.
But here it is obtained independently of this theorem.
The preceding Proposition shows that counting i-columns over all subsets of
X always produce the same result.
We shall now make some restrictions on the number of subsets of X . Take
0 ≤ m1 ≤ m2 ≤ n fixed, and consider the submatrix C of A consisting of rows
whose indices belong to I0, and columns corresponding to those subsets of X
that have m, (m1 ≤ m ≤ m2) elements.
Let c be an i-column of C. Define I ′0 = {i ∈ I0 : ci = 1}, |I
0| = l.
The number ν(c) is equal to the number of sets that contain {xi : i ∈ I
and do not intersect the sets {xi : i ∈ I0 \ I
}. We thus have
m2−|I
i=m1−|I
n− |I0|
On the other hand, for I ⊆ I0 the number C(I) corresponds to the number
of sets that contain {xi : i ∈ I \ I
}, and do not intersect {xi : i ∈ I ∩ I
}. Its
number is equal
m2−|I\I
i3=m1−|I\I
n− |I|
It follows that the formula (5) may be applied. We thus have
Proposition 2.2. For 0 ≤ m1 ≤ m2 ≤ n, and 0 ≤ l ≤ k holds
i=m1−l
m2−i2
i3=m1−i2
(−1)i1+i2
k − l
n− i1 − i2
In the special case when one takes k = l, m1 = m2 = m we obtain
Corollary 2.1. For arbitrary nonnegative integers m,n, k holds
(−1)i
. (9)
Note 2.2. The preceding is one of the best known binomial identities. It appears
in the book [1] in many different forms.
Taking m1 = m2 = m, in (8) one gets
Corollary 2.2. For arbitrary nonnegative integer m,n, k, l, (l ≤ k) holds
(−1)i1+i2
k − l
n− i1 − i2
m− i2
, (10)
For l = 0 we obtain
(−1)i
, (11)
which is only another form of (9).
Taking n = 2k, l = k in (10)we obtain
(−1)i1
2k − i1
Substituting k − i1 by i we obtain
Corollary 2.3. Klee’s identity,([2],p.13)
(−1)k
(−1)i
k + i
From (8) we may obtain different formulae for partial sums of binomial
coefficients, that is, for the numbers of Bernoulli’s triangle. For instance, taking
l = 0, m1 = 0, m2 = m we obtain
Corollary 2.4. For any 0 ≤ m ≤ n and arbitrary nonnegative integer k holds
(−1)i1
n+ k − i1
. (12)
Note 2.3. The number k in the preceding equation may be considered as a free
variable that takes nonnegative integer values. Specially, for k = 1 the equa-
tion represents the standard recursion formula for the numbers of Bernoulli’s
triangle.
Taking k = l = m1, m2 = m one obtains
(−1)i1
n+ k − i1
Note 2.4. The formulae (12) and (13) differs in the range of the index i2.
References
[1] J. Riordan, Combinatorial Identities. New York: Wiley, 1979.
	A counting theorem
	Counting subsets of a finite set
