Information Technology Reference
In-Depth Information
the standard notation for this number is:
n
k
.
These numbers are called
binomial coefficients
, because (as Newton showed) they
are the coefficients occurring in the expansion of the powers of binomials:
n
k
a
k
b
n
−
k
n
k
=
0
n
(
a
+
b
)
=
By using the factorial representation of subfactorials we get the following equation:
n
k
n
!
=
!
k
!
The formula above is simple, but it is very complex to be computed. In fact, when
numbers are big it is computationally prohibitive. In the next section we will provide
(
n
−
k
)
a recurrent formula for computing
k
without using factorials.
7.1.3
Inductive Derivation of Binomial Coefficients
There is only one possibility of choosing
n
objects among
n
given objects, and
there are
n
possibilities of choosing one object among them. Of course, zero ob-
jects among
n
corresponds to the choice of the empty set, therefore we can put the
following equalities:
n
n
=
1
n
1
=
n
n
0
=
1
.
Theorem 7.1.
For any n
≥
k
>
0
:
n
n
k
n
k
+
1
=
+
+
+
k
1
1
Proof.
Let us consider
n
+
1 objects (
n
≥
0). We can select
k
+
1ofthem(
k
≤
n
) by using the following procedure. Let us fix one object among the given
n
+
1
objects, call it
a
. The subsets of the
k
1 chosen elements can belong to one of
two classes: the sets including
a
and the sets that do not include
a
. The sets of the
first type are in one-to-one correspondence with the choices of
k
objects among
n
,
because
a
can be added to any choice of
k
. The sets of the second type are in one-to-
one correspondence with the choices of
k
+
+
1 objects among
n
, because
a
is never
