Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 51

Differentiate w.r.t z
1.5/(1 – 5z)^2 = 0 + 5.1 + 2.5^2 z + 3.5^3 z^2 + .......... + n.5n zn–1 + ..................
or 5/(1 – 5z)^2 = 0.5^0 + 1.5^1 + 2.5^2 z + 3.5^3 z^2 + .......... + n.5n zn–1 + .............
Multiply both sides with z, so we have
5 z/(1 – 5z)^2 = 0.5^0 z + 1.5z + 2.5^2 z^2 + 3.5^3 z^3 + .......... + n.5n zn + ..............
or 5 z/(1 – 5z)^2 = 0.5^0 + 1.5z + 2.5^2 z^2 + 3.5^3 z^3 + ..........+ n.5n zn + ................
Therefore, 5z/(1 – 5z)^2 is the generating function for (0.5^0 , 1.5^1 , 2.5^2 , ........, n.5n, .............).
Example 2.35 Determine generating function and discrete numeric function of series

• 3/2 + 2 + 0 + 8 + ........
  Sol. Let scale of relation of the given series be 1 – pz – qz^2. Obtain p and q from the equations,
  0 – 2p + 3/2q = 0 and 8 – 0 – 2q = 0
  So we obtain q = 4 and p = 3. Whence, scale of relation is 1 – 3z – 4z^2.
  Hence, the generating function A(z) for series, – 3/2 + 2.z + 0.z^2 + 8.z^3 + ........ is
  = [– 3/2 + (2 + 3.3/2)z]/(1 – 3z – 4z^2 ) (using equation (2.7))
  = (– 3/2 + 13/2z )/ (1 – 3z – 4z^2 )
  So, A(z) = (– 3/2 + 13/2z)/(1 – 3z – 4z^2 )
  Since A(z) can be written as (using partial fraction)
  = (8/5)/(1 + z) – (31/10)/(1 – 4z)
  So numeric function will be the coefficient of zn that will be,
  an = (8/5).(– 1)n.1 – (31/10).4n
  or an = (– 1)n .(8/5) – (31/10).4n for n ≥ 0.

2.5 Application of Generating Function to Solve Combinatorial Problems.........................

The important application of generating function representation of numeric function is the

solving of combinatorial problems. Consider the numeric function an, i.e.,

an =

m

n

F

HG

I

KJ for a fixed value of n

Since, a

m

n n

m

n nm

n=

F

HG

I

KJ==

F

HG

I

KJ=>

R

S

||

T

|

|

10

0

for

for

we recall following definitions that are frequently used in solving of combinatorial problems,

• The expression n(n – 1) ..... 2 .1 is called n – factorial, and denoted by n!, with the
  convention 0! = 1.


• 
  

  m
  n

  
  

F

HG

I

KJ is called binomial coefficient, i.e., (number of n – subsets of an m – set)

m

n

F

HG

I

KJ

= m!/n! (m – n)!

• Binomial coefficients m
  n

F

HG

I

KJ

have no combinatorial meaning for negative values of m.