Mathematical Foundation of Computer Science

DISCRETE NUMERIC FUNCTIONS

AND GENERATING FUNCTIONS

2.1 Introduction.......................................................................................................................

2.2 Properties of Numeric Functions

2.2.1 Addition of numeric functions

2.2.2 Multiplication of numeric functions

2.2.3 Multiplication with scalar factor to numeric function

2.2.4 Q uotient of numeric functions

2.2.5 Modulus of numeric function

2.2. 6SI an and S–I an

2.2.7 Accumulated sum of numeric functions

2.2.8 Forward difference & backward difference

2.2.9 Convolution of numeric functions

2.3 Asymptotic Behavior (Performance) of Numeric Functions

2.3.1 Big—Oh (O) Notation

2.3.2 Omega (ΩΩΩΩΩ) Notation

2.3.3 Theta (θθθθθ) Notation

2.4 Generating Functions

2.5 Application of Generating Function to Solve Combinatorial Problems

Exercises