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