Information Technology Reference
In-Depth Information
chosen. In conclusion, if binomial coefficients provide the number of
j
-subsets for
sets of size smaller than
n
+
1 (with
j
≤
n
), then: the number of combinations with
a
is
k
, and the number of combinations without
a
is
n
1
. This concludes the
k
+
proof.
The number of combinations is easily computed by the following triangle due to
Tartaglia and Pascal, but already known by Chinese mathematicians at least 1000
years earlier. It is based on the previous theorem. In fact, the
n
-th row provides the
values of
k
for
k
going from 0 (left) to
n
(right). In the triangle, the elements of
the
-th row are obtained by summing the two elements over it in the
n
-th row
(the top left and the top right). The first seven rows of this triangle are the following:
(
n
+
1
)
1
11
12 1
1331
14641
15 0 051
1
6
15
20
15
6
1
Tartaglia's (or Pascal's) triangle is symmetric. In fact, choosing
k
objects among
n
is equivalent to chose
n
−
k
among
n
, which correspond to those which are not
chosen, that is:
n
k
n
n
=
.
−
k
Of course, the definition by induction has to coincide with the definition by means
of factorials, that is:
(
n
k
!
+
(
)
k
n
)
k
+
1
!
=
(
n
+
1
)
k
+
1
.
(
k
+
1
)
(
k
+
1
)
!
Newton's formula, for computing the power of a binomial, is based on binomial
coefficients. In fact, it is easy to realize that the coefficient of a power
a
k
b
n
−
k
,ofde-
gree
n
, coincides with the number of ways the factor
a
can be chosen in the product
(
a
+
b
)(
a
+
b
)
...
(
a
+
b
)
of
n
binomials (so that
b
is chosen
n
−
k
times), therefore:
n
k
a
k
b
n
−
k
n
k
=
0
n
(
a
+
b
)
=
.
1 we get the number 2
n
of all possible subsets of
n
elements. In fact,
k
-subsets, with
k
going from 0 to
n
, are all possible subsets of
n
elements:
When in this formula
a
=
b
=
