Cryptography Reference
In-Depth Information
Definition A.13
(
Factorial Notation!)
If
n
, then
n
!(
read
“enn factorial”)
is the product of the first
n
natural
numbers. In other words,
∈
N
n
n
!=
i.
i
=1
We agree, by convention, that
0! = 1
. In other words, multiplication of no
factors yields the identity.
The factorial notation gives us the number of distinct ways of arranging
n
objects. For instance, if you have 10 topics on your bookshelf, then you can
arrange them in 10! = 3,628,800 distinct ways. This motivates the next symbol.
Definition A.14
(
Binomial Coe:cients)
If
k,n
n
, then the symbol
k
(
read “
n
choose
k
”
)
is given
∈
Z
with
0
≤
k
≤
by
n
k
=
n
!
k
!(
n
−
k
)!
the
binomial coeGcient
.
The binomial coeGcient is used in the theory of probability as the number of
different combinations of
n
objects taken
k
at a time. For instance, the number
of ways of choosing two objects from a set of five objects,
without regard for
order
,is
2
=5!
/
(2!3!) = 10 distinct ways (see Appendix E).
Proposition A.1
(
Properties of the Binomial Coe:cient)
If
n,k
∈
Z
and
0
≤
k
≤
n
, then
(a)
n
n
−
k
=
k
.
Symmetry Property)
(b)
n
+1
k
+1
=
n
k
+1
+
k
.
(
Pascal's Identity)
1)
i
i
=0.
(c)
i
=0
(
−
(
Null Summation Property)
(d)
i
=0
i
=2
n
.
(
Full Summation Property)
Proof
. See [167, Proposition 1.2.1, pages 18 and 19].
✷
The full summation property given above can be broken down into two more
revealing parts. For this we need a new function as follows.
Definition A.15
(
The Greatest Integer Function — The Floor)
If
x
x<n
+1
.
We say that
n
is the
greatest integer less than or equal to
x
or
the floor
of
x
,
denoted by
∈
R
, then there is a unique integer
n
∈
Z
such that
n
≤
x
=
n
.
Search WWH ::
Custom Search