Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 53

(ii) – 1 + 6 + 30 + ...........................

(iii) 1 + 6 + 24 + 84 + ......................

(iv) 2 + 7 + 25 + 19 + .....................

2.4 Determine the generating function of the numeric function an where

a n

n n

n

= − n

R

S

T

5

5

for is even

for is odd

2.5 Determine the discrete numeric functions corresponding to the following generating functions

(i)A(z) = (1 + 3z)/(1 + 11z + 28z^2 )(ii)A(z) = (2z + 1)/(z^2 + 1) (z – 1)

(iii)A(z) = (1 – z + 2z^2 )/(1 – z)^3 (iv)A(z) = (7 + z)/(1 + z) (1 + z^2 )

(v)A(z) = (2 + z)n + (2 – z)–n

2.6 Determine the asymptotic order of the following numeric functions

(i)an = 8n + C where C > 1024 (ii)an = 3n^3 + 2n^2 + 1

(iii)an = 2n n^3 + n (iv)an = n!

(v)an = 3n^3 + 2n^2 +1 (vi)an = n log n + n^2

(vii)an = n^2 n + 5*2n (viii)an = n1.5 + n log n

(ix)an = n1.001 + n log n (x)an = kΣ

n

= 0 k

2

(xi)an = kΣ

n

= 0 k

3

2.7 In how many ways can 3n men can be selected form 2n men of white hairs, 2n men of curly

hairs, and 2n men of silky hairs.

2.8 Let an denote the number of ways to seat 7 students in a row of n chairs so that no two students

will occupy adjacent seats. Determine the generating function of the discrete numeric function.

2.9 Determine the numeric function and the generating function of the following series :

(i) nnn n

k

n

012 n

F^22222

HG

I

KJ

+F

HG

I

KJ

+F

HG

I

KJ

++F

HG

I

KJ

++F

HG

I

KJ

............ ............

(ii)GHF 0 nn nIJK+ (^2) HFG 1 IJK+ (^22) GHF 2 JKI++............ 22 knHGFnkKIJ++............ FHGnnIKJ
(iii)
nnk
nk
n
n
n
0 n
221
1
F^2
HG
I
KJ++
−
−
F
HG
I
KJ++
−
−
F
HG
I
KJ+
F
HG
I
............ ............ KJ
(iv) 2
0 221 232 21
nnn (^231) n n
n
F n
HG
I
KJ+
F
HG
I
KJ+
F
HG
I
KJ+++
F
HG
I
KJ
/ / ............ +/
(v) nnn 012 11 knnk nn
F^22222
HG
I
KJ −
F
HG
I
KJ +
F
HG
I
KJ −+−
F
HG
I
KJ ++−
F
HG
I
............ ( ) ............ ( ) KJ
2.10 Determine the time complexity of the following programs :
(i) //a function which return the summation of n numbers placed in
the array A[0, n – 1]
int Sum1(int A[ ], int n)
{
int sum = 0;
for (int I = 0; I < n ; I ++ )
sum = sum + A[I];
return sum;
}