Important Announcement
PubHTML5 Scheduled Server Maintenance on (GMT) Sunday, June 26th, 2:00 am - 8:00 am.
PubHTML5 site will be inoperative during the times indicated!

Home Explore BCA124 CU- BCA-Sem 2 -Discrete Mathematical Structures(Draft 3)-converted

BCA124 CU- BCA-Sem 2 -Discrete Mathematical Structures(Draft 3)-converted

Published by Teamlease Edtech Ltd (Amita Chitroda), 2021-04-20 17:46:50

Description: BCA124 CU- BCA-Sem 2 -Discrete Mathematical Structures(Draft 3)-converted

Search

Read the Text Version

Part1: If ℎ������ satisfies the associated homogeneous recurrence then ������������ satisfies the non-homogeneous recurrence. ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) ℎ������ = ������1ℎ������−1 + ������2ℎ������−2 + ⋯ + ������������ℎ������−������ Now ������������ + ℎ������ = ������1(������������−1 + ℎ������−1) + ������2(������������−2 + ℎ������−2) + ⋯ + ������������(������������−������ + ℎ������−������) + ������(������) Since, ������������ = ������������ + ℎ������ ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) So, ������������ is a solution of the non-homogeneous recurrence. Part2: If������������ satisfies the non-homogeneous recurrence then ℎ������is satisfies the associated homogeneous recurrence. ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) ������������ − ������������ = ������1(������������−1 − ������������−1) + ������2(������������−2 − ������������−2) + ⋯ + ������������(������������−������ − ������������−������) ℎ������ = ������������ − ������������ Since, ℎ������ = ������1ℎ������−1 + ������2ℎ������−2 + ⋯ + ������������ℎ������−������ So, ℎ������is a solution of the associated homogeneousrecurrence. Proposition: Let ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������)be a linear nonhomogeneous recurrence. Assume the sequence ������������satisfies the recurrence. Another sequence an satisfies the non-homogeneous recurrence if and only ifℎ������ = ������������ − ������������is also a sequence that satisfies theassociated homogeneous recurrence. Proof:We already know how to find ℎ������. • For many common������(������), a solution ������������ to the non-homogeneousrecurrence is similar to f(n). • Then you should find solution������������ = ������������ + ℎnto the nonhomogeneousrecurrence that satisfies both recurrence andinitial conditions. 150 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 2: What is the solution of the recurrence relation������������ = ������������−1 + ������������−2 + 3������ + 1 ������������������������ ≥ 2 with ������0 = 2and ������1 = 3 ? Solution: Since it is linear non-homogeneous recurrence, ������������ is similar to ������(������) Guess: ������������ = ������������ + ������ ������������ = ������������−1 + ������������−2 + 3������ + 1 ������������ + ������ = ������(������ − 1) + ������ + ������(������ − 2) + ������ + 3������ + 1 ������������ + ������ = ������������ − ������ + ������ + ������������ − 2������ + ������ + 3������ + 1 0 = (3 + ������)������ + (������ − 3������ + 1) ������ = −3, ������ = −10 So ������������ = −3������ − 10 (bn only satisfies the recurrence, it does not satisfy the initial conditions.) 7.5 SUMMARY In this unit, we had discussed how recursive techniques can derive sequences and be used for solving counting problems. The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation. A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s).The simplest form of a recurrence relation is the case where the next term depends only on the immediately previous term. A recurrence relation can also be higher order. To generate sequence based on a recurrence relation, one must start with some initial values. For a first order recursion, one just needs to start with an initial value x0 and can generate all remaining terms using the recurrence relation. For a second order recursion, one needs to begin with two values x0 and x1. Higher order recurrence relations require correspondingly more initial values. 7.6 KEYWORDS: • Recurrence:A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s). • Initial Condition: an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted t = 0). 151 CU IDOL SELF LEARNING MATERIAL (SLM)

• General Term: a mathematical expression composed of variables and constants that yields the successive terms of a sequence or series when integers are substituted for one of the variables often denoted by k. • Backtracking: A technique for finding an explicit formula for the sequence defined by a recurrence relation is called backtracking. • Finite Difference: The finite difference is the discrete analog of the derivative 7.7 LEARNING ACTIVITY 1. Discuss the difference between finite difference and backtracking method 2. Check that an = 2n + 1 is a solution to the recurrence relation an = 2an-1 - 1 with a1 = 3 7.8 UNIT END QUESTIONS A. Descriptive Questions 1. Find a recurrence relation and initial conditions for 1,5,17,53,161,485… 2. Check that an=2n+1 is a solution to the recurrence relation an = 2an−1 − 1with a1=3. 3. Solve the recurrence relation an=an−1 + n with initial term a0=4. 4. Explain Homogeneous Recurrence Relations 5. Discuss IN Homogeneous Recurrence Relations B. Multiple Choice Questions: 1. Consider the recurrence relation a1=4, an=5n+an-1. The value of a64 is a) 10399 b) 23760 c) 75100 d) 53700 2. Determine the solution of the recurrence relation Fn=20Fn-1 − 25Fn-2 where F0=4 and F1=14. 152 a) an = 14*5n-1 b) an = 7/2*2n−1/2*6n CU IDOL SELF LEARNING MATERIAL (SLM)

c) an = 7/2*2n−3/4*6n+1 d) an = 3*2n−1/2*3n 3. What is the recurrence relation for 1, 7, 31, 127, 499? a) bn+1=5bn-1+3 b) bn=4bn+7! c) bn=4bn-1+3 d) bn=bn-1+1 4. f Sn=4Sn-1+12n, where S0=6 and S1=7, find the solution for the recurrence relation. a) an=7(2n) −29/6n6n b) an=6(6n) +6/7n6n c) an=6(3n+1) −5n d) an=nn−2/6n6n 5. Find the value of a4 for the recurrence relation an=2an-1+3, with a0=6. a) 320 b) 221 c) 141 d) 65 6. The solution to the recurrence relation an=an-1+2n, with initial term a0=2 is a) 4n+7 b) 2(1+n) c) 3n2 d) 5*(n+1)/2 7. Determine the solution for the recurrence relation bn=8bn-1−12bn-2 with b0=3 and b1=4. a) 7/2*2n−1/2*6n b) 2/3*7n-5*4n c) 4! *6n d) 2/8n 153 CU IDOL SELF LEARNING MATERIAL (SLM)

8. What is the solution to the recurrence relation an=5an-1+6an-2? a) 2n2 b) 6n c) (3/2) n d) n! *3 9. Determine the value of a2 for the recurrence relation an = 17an-1 + 30n with a0=3. a) 4387 b) 5484 c) 238 d) 1437 10. Determine the solution for the recurrence relation an = 6an-1−8an-2 provided initial conditions a0=3 and a1=5. a) an = 4 * 2n – 3n b) an = 3 * 7n – 5*3n c) an = 5 * 7n d) an = 3! * 5n Answers: 1 -a; 2 - b; 3 -c; 4 - b; 5 - c; 6 – b; 7 – a; 8 – b; 9 – d; 10 – b. 7.9 REFERENCES • Kenneth Rosen, Discrete Mathematics and Its Applications with Combinatorics and Graph Theory (SIE) | 7th Edition, McGraw Hill Education; 7 editions • Jean-Paul Tremblay, R Manohar, DISCRETE MATHEMATICAL STRUCTURES WITH APPLICATIONS TO COMPUTER SCIENCE, McGraw Hill Education; 1st edition • Seymour Lipschutz, Marc Lara’sLipson, Varsha H. Patil, Discrete Mathematics (Schaum's Outlines) | Revised 3rd Edition, McGraw Hill Education; Revised Third edition. • Jiri Matousek , Jaroslav Nesetril, Invitation to Discrete Mathematics,OUP Oxford • V.K. Balakrishnan, Introductory Discrete Mathematics (Dover Books on Computer Science),Dover Publications Inc. • Harry Lewis, Rachel Zax, Essential Discrete Mathematics for Computer Science, Princeton University Press. • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 154 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 8- GENERATING FUNCTION 1 Structure 8.0. Learning Objectives 8.1. Introduction 8.2. Closed form expression, 8.3. Properties of G.F. 8.4. Generating Function Models 8.5. Summary 8.6. Keywords 8.7. Learning Activity 8.8. Unit End Questions 8.9. References 8.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • Explain the closed form expression using Generating Function. • Discuss the properties of Generating functions and its models. 8.1 INTRODUCTION An important idea in mathematics is to establish connections between two fields in order to apply knowledge in one field to the other field, or at least take a problem in one field and transform it to a problem in the other field. This idea motivates the idea of a generating function, which establishes a connection between functions of a real variable and sequences of numbers. Generating functions are one of the most surprising and useful inventions in Discrete Math. Roughly speaking, generating functions transform problems about sequences into problems about functions. This is great because we’ve got piles of mathematical machinery for manipulating functions. We can apply generating functions to the machinery of problems about sequences. 8.2 CLOSED FORM EXPRESSION, Generating Function of Sequence: The concept of generating functions is a powerful tool for solving counting problems. Intuitively put, its general idea is as follows. In counting problems, we are often interested in counting the number of 155 CU IDOL SELF LEARNING MATERIAL (SLM)

objects of ‘size n’, which we denote by an. By varying n, we get different values of an. In this way we get a sequence of real numbers a0, a1, a2, … Here our interest is in the sequence of real numbers (a0, a1, a2, …, ar, …), and such function whose domain is the set of nonnegative integers and whose range is the set of real numbers. Expressions like ������ = {������������ }∞������ is used to denote such sequences, where aris the number of ways to select r objects in some procedure. Example 1: The sequence 0 ������ = {2������}∞������=0is the sequence (1,2,4,8,16, …, 2r, …); the sequence������ = {������������}∞������=0 Where 0 ������������ 0 ≤ ������ ≤ 4 ������������ = {23 ������������ 5 ≤ ������ ≤ 4 4 ������������������ = 10 ������������ 11 ≤ ������ Thus, B = (0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 3, 4, 4 …) ������ = {������������}∞������=,0where Cr = r + 1 for each value of r, is the sequence (1, 2, 3, 4, 5…) and the sequence������ = {������������}∞������=w0 here for each r dr = r2 is the sequence(0, 1, 4, 9, 16, 25 …) • To the Sequence ������ = {������������}∞������=0, we will assign the symbol ∞ ������(������) = ������0 + ������1������ + ⋯ + ������������������������ = ∑ ������������������������ ������=0 • The expression A (X) is called aformal power series, ai is the coefficient of Xi, the term ai Xi is a term of degree I, and the term a0 X0 = 0 is called the constant term. • The formal power series ������(������) = ∑���∞��� ������������ ������������is called the generating function for the sequence������ = {������������}���∞���=0 • We will use the word ‘formal’ to distinguish between the abstract symbol ������(������) = ∑���∞��� ������������ ������������and the concept of Power series Example 2: The generating functions of example 1 ∞ ������(������) = ∑ 2������������������ ������=0 B (X) = 2 X5 + 2 X6 + 2 X7 + 2 X8 + 2 X9 + 3 X10 + 4 X11 + 4 X12 + … ∞ ������(������) = ∑(������ + 1)������������ ������=0 156 CU IDOL SELF LEARNING MATERIAL (SLM)

∞ ������(������) = ∑ ������2������������ ������=0 Definition: Given a numeric sequence the series is called the generating function of the sequence. To find the generating function for a sequence means to find a closed form formula for f(x), one that has no ellipses. Example 3: The generating function for the constant sequence, has closed form This is because the sum of the geometric series i (for all x less than 1 in absolute value). Example: Find the generating functions of the following sequences in closed form. Solution. Formally, we can differentiate and integrate a power series term by term. In other words, if 157 CU IDOL SELF LEARNING MATERIAL (SLM)

The same is true for integration in place of differentiation. (a) The generating function is (b) The generating function is Let ������(������) = ∑���∞���=0 ������������������������, ������(������) = ∑∞������=0 ������������������������be two formal power series then we can define following concept as follows: EQUALITY: A (X) = B (X) if and only if an = bn for each n ≥ 0. MULTIPLICATION BY A SCALAR NUMBER C:������������(������) = ∑∞������=0(������������������)������������ SUM: ������(������) + ������(������) = ∑∞ (������������ + ������������)������������ ������=0 PRODUCT:������(������)������(������) = ∑������∞=0 ������������������������ 158 CU IDOL SELF LEARNING MATERIAL (SLM)

• Pn Xn is the product of A(X) B (X) which is obtained by taking the sum of all possible products of one term from A(X) and one term from B(X) such that n = sum of the exponents • Thus, this can be accomplished by considering a0 which is a constant term of A (X) and multiply it with the coefficients bn of Xn in B(X) • Proceeding ahead, now coefficient a1 of X in A (X) and multiply it by the coefficient bn – 1 of Xn – 1 in B(X) and so on. • In product we are supposed to use the increasing powers of X in A(X) while decreasing powers of X in B(X) • So, we get Pn = a0 bn + a1 bn – 1 + a2 bn – 2 + … + an b0 = ∑∞������=0 ������������������������−������ Thus, A(X)B(X) = a0 b0 +( a0 b1 + a1 b0) X + (a0 b2 + a1 b1 + a2 b0) X2 + …+(a0 bn + a1 bn – 1 + a2 bn – 2 + … + an b0) Xn + … Example 4: If S (X) = a0 + a2X2 + a4X4 + a8X8 and T (X) = b0 + b4X4 + b6X6 + b8X8 (we assume the coefficients for the missing power of X is zero) • Then we can find the coefficient of Xr in S(X) T(X) by considering the powers {X0, X2, X4, X8} from the first factor and the powers {X0, X4, X6, X8} from the second factor such that their sum is r. • For instance, the coefficient of X8 can be obtained by using X0 in the first factor and X8 in the second; X2 in the first factor and X6 in the second. • Thus, the coefficient of X8 in the product S(X) T(X) is such that • P8 = a0b8 + a2b6 + a4b4 + a8b0, because (0, 8), (2, 6), (4, 4), and (8, 0) are the only pairs of exponents of S(X) and T(X) whose sum is 8. • Likewise, the coefficient of X6 in the product is a0 b6 + a2 b4, because there are only two pair of exponents of S(X) and T(X), whose sum is 6. Thus, if a0= 2, a2 = - 5, a4 = 7 + a8 = 3 b0 = 3, b4 = - 6, b6 = 8, b8 = 3 then P8 = (2)(3) + (-5) (8) + (7) (-6) + (3)(3) = - 67, The case where the entire non-zero coefficients are 1 is of special interest. We will have P8 = 4 We can now conclude that the coefficient of X8 in the product is just the number of pairs of exponents whose sum is 8 or in other words the number of integral solutions to the equation e1 + e2 = 8, where e1 and e2 represent the exponents of S(X) and T(X), respectively. 159 CU IDOL SELF LEARNING MATERIAL (SLM)

Remarks: a. The coefficient of Xr in the product (1 + X2 + X4 + X8) (1 + X4 + X6 + X8) is the number of integral solutions to the equation e1 + e2 = r subject to the constraints e1 = 0,2,4,8 and e2 = 0, 4, 6, 8. b. The exponents of the factors in the product reflect the constraint in the equation. c. We can compute the coefficient of Xrby algebra and then discover the number of integral solutions to the equation e1 + e2 =r subject to the constraints; or d. We can compute all the solutions of the equation subject to the constraints and then discover the coefficient of Xr. 8.3 PROPERTIES OF GENERATING FUNCTIONS Most generating functions share four important properties: 1. Under mild conditions, the generating function completely determines the distribution. 2. The generating function of a sum of independent variables is the product of the generating functions 3. The moments of the random variable can be obtained from the derivatives of the generating function. 4. Ordinary (pointwise) convergence of a sequence of generating functions corresponds to the special convergence of the corresponding distributions. Property 1 is most important. Often a random variable is shown to have a certain distribution by showing that the generating function has a certain form. The process of recovering the distribution from the generating function is known as inversion. Property 2 is frequently used to determine the distribution of a sum of independent variables. By contrast, recall that the probability density function of a sum of independent variables is the convolution of the individual density functions, a much more complicated operation. Property 3 is useful because often computing moments from the generating function is easier than computing the moments directly from the definition. The last property is known as the continuity theorem. Often it is easier to show the convergence of the generating functions than to prove convergence of the distributions directly 8.4 GENERATING FUNCTION MODELS • Let us consider the product of generating function A(X) and B(X), where the exponents of A(X) reflect the constraints on e1and the exponents of B(X) reflect the constraints on e2. • Xr is the coefficient of the product of generating function A(X) B(X) • Assume e1 can only be 0, 1, 9 then let A(X) = 1 + X + X9. If e2 can only be even and 0≤ e2 ≤ 8, then B(X) = 1 + X2 + X4+ X6 + X8 160 CU IDOL SELF LEARNING MATERIAL (SLM)

• And if e1can be any non-negative integer value, then we let 1 + X + X2 + … [ A(X) has infinite number of terms]. Also, if e2 can only take on the integral values like that are multiples of 5, then we let B (X) = 1 + X5 + X10 + … Hence, we can see endless possibilities. Now we can extend the definition of product of formal power series for 3 factors as below: ∞ ������(������) = ∑ ������������������������ ������=0 ∞ ������(������) = ∑ ������������������������ ������=0 ∞ ������(������) = ∑ ������������������������ ������=0 Then ∞ ������(������)������(������)������(������) = ∑ ������������������������ ������=0 where ������������ = ∑ ������������������������������������ ������+������+������=������ Thus, we can find the term PrXr by taking any one term aiXi from A(X), any one term bjXj from B(X) and any one term ckXk from C(X) such that the sum of exponents i + j + k = r. Assume each non-zero coefficient of each formal power series Ai(X) is 1. Then we have the coefficient of Xr in the product A1(X) A2(X) … An(X) indicates the number of integral solutions to the equation e1 + e2 + … + en = r where constraints on each ei is determined by the exponents of the ith factor of Ai(X). Conversely if we are supposed to count the number of non-negative integral solutions to an equation e1 + e2 + … + en = r with constraints on each ei then we can build a generating function A1(X) A2(X) … An(X) whose coefficient of Xr is the answer. 161 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 1: Find a generating function for ar = the number of non- negative integral solutions of e1 + e2 + e3 + e4 + e5 = r where 0 ≤ e1 ≤ 3, 0 ≤ e2 ≤ 3, 2 ≤ e3 ≤ 6, 2 ≤ e4 ≤ 6, e5 is odd, and 1 ≤ e5 ≤ 9. Let A1(X) = A2(X) = 1+ X + X2 + X3, A3(X) = A4(X) = X2 + X3 + X4 + X5 + X6 and A5(X) = X + X3 + X5 + X7 + X9. Thus, the generating function we want is A1(X) A2(X) A3(X) A4(X) A5(X) = (1+ X + X2 + X3)2 (X2 + X3 + X4 + X5 + X6 )2 (X + X3 + X5 + X7 + X9). Example 2: Find a generating function for ar = the number of non- negative integral solutions of e1 + e2 +…+ en = r where 0 ≤ ei ≤ 1. Let Ai(X) = 1 + X for each i = 1, 2, …, n. Thus, the generating function we want is A1(X) A2(X) … An(X) = (1 + X) n. As per the binomial theorem the answer to above is C (n, r) – the coefficient of Xr term. Example 3: Find the coefficient of X16 in (1 + X4+ X8 )10. The only solution to e1 + e2 + … + e10 = 16 where ei = 0, 4, 8 are those with four 4’s, no 8’s and six 0’s or two 8’s, no 4’s and eight 0’s; or two 4’s, one 8, and seven 0’s. Thus, the coefficient is 10 10 10 10 10 ( 4 )+( 2 )+8( 2 )= ( 4 )+9( 2 ) Example 4: Build a generating function for determining the number of ways of making change for a dollar bill in pennies, nickels, dimes, quarters, and half- dollar pieces. Which coefficient do we want? We can find the coefficient of X100 in the product of (1 + X + X2 + … + X100) (1 + X5 + X10 + … + X100) (1 + X10 + X20 + … + X100) (1 + X25 + X50 + X75 + X100) (1 + X50 + X100). Example 5: Find a generating function for the sequence ������ = {������������}∞������=0where 1 if 0 ≤ r ≤ 2 A = 3 if 3 ≤ r ≤ 5 0 if r ≥ 6 162 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: 1 + X + X2 + 3X3 + 3 X4 + 3X5 8.5 SUMMARY A generating function is just a different way of writing a sequence of numbers. Definition - Let (an) n ≥0 be a sequence of numbers. The generating function associated to this sequence is the series A(x) = ∑������≥0 ������������������������ Also, if we consider a class A of objects to be enumerated, we call generating function of this class the generating function A(x) = ∑������≥0 ������������������������ where an is the number of objects of size n in the class. One use for generating functions is get closed formulas for sequences which are defined recursively in terms of previous terms. Important concepts in Power Series: Equality:A (X) = B (X) If and Only If An = Bn For Each N ≥ 0. Multiplication by A Scalar NumberC:������������(������) = ∑∞ (������������������)������������ ������=0 SUM: ������(������) + ������(������) = ∑∞ (������������ + ������������)������������ ������=0 PRODUCT:������(������)������(������) = ∑∞������=0 ������������������������ Properties of Generating Functions 163 Most generating functions share four important properties: 1. Under mild conditions, the generating function completely determines the distribution. CU IDOL SELF LEARNING MATERIAL (SLM)

2. The generating function of a sum of independent variables is the product of the generating functions 3. The moments of the random variable can be obtained from the derivatives of the generating function. 4. Ordinary (pointwise) convergence of a sequence of generating functions corresponds to the special convergence of the corresponding distributions. Generating Function Model: If we are supposed to count the number of non-negative integral solutions to an equation e1 + e2 + … + en = r with constraints on each ei then we can build a generating function A1(X) A2(X) … An(X) whose coefficient of Xr 8.6 KEYWORDS • Generating function:A Generating function is a way of encoding an infinite sequence of numbers (an) by treating them as the coefficients of a formal power series. • Closed-form a closed-form expression is a mathematical expression expressed using a finite number of standard operations. • Constant term: is a term in an algebraic expression that has a value that is constant or cannot change, because it does not contain any modifiable variables • Power series, in mathematics, an infinite series that can be thought of as a polynomial with an infinite number of terms, such as 1 + x + x2 + x3 +⋯. • Scalar: A scalar is an element of a field which is used to define a vector space 8.7 LEARNING ACTIVITY 1. Explain basic prerequisites for Generating Function. 2. Find the generating function for the sequence {an} defined by a0 = 1 and an= 8an−1 + 10n−1 for n ≥ 1 Then find explicit formula for an. 8.8 UNIT END QUESTIONS 164 A. Descriptive Type Questions CU IDOL SELF LEARNING MATERIAL (SLM)

1. What is Generating Function? 2. Explain the closed form of Generating Function with example. 3. Discuss the properties of Generating Function 4. Explain the Generating Function Models. 5. Prove that the generating function for 1,1, 1, 1, ... is 1 1−������ B. Multiple Choice Questions: 1. What is the sequence depicted by the generating series 4 + 15x2 + 10x3 + 25x5 + 16x6+⋯? a) 10, 4, 0, 16, 25, … b) 0, 4, 15, 10, 16, 25, c) 4, 0, 15, 10, 25, 16, d) 4, 10, 15, 25, … 2. What is the generating function for the sequence 1, 6, 16, 216,.? a) (1+6x)x3 b) 1(1−6x) c) 1(1−4x) d) 1-6x2 3. What is multiplication of the sequence 1, 2, 3, 4,… by the sequence 1, 3, 5, 7, 11,….? a) 1, 5, 14, 30,… b) 2, 8, 16, 35,… c) 1, 4, 7, 9, 13,… d) 4, 8, 9, 14, 28,… 4. What will be the sequence generated by the generating function 4x/(1-x)2? a) 12, 16, 20, 24,… b) 1, 3, 5, 7, 9,… c) 0, 4, 8, 12, 16, 20,… d) 0, 1, 1, 3, 5, 8, 13,… 165 CU IDOL SELF LEARNING MATERIAL (SLM)

5. What is the recurrence relation for the sequence 1, 3, 7, 15, 31, 63,…? a) an = 3an-1−2an+2 b) an = 3an-1−2an-2 c) an = 3an-1−2an-1 d) an = 3an-1−2an-3 6. What is multiplication of the sequence 1, 2, 3, 4,… by the sequence 1, 3, 5, 7, 11,….? a) 1, 5, 14, 30,… b) 2, 8, 16, 35,… c) 1, 4, 7, 9, 13,… d) 4, 8, 9, 14, 28,… 7. What is the generating function for the generating sequence A = 1, 9, 25, 49,…? a) 1+(A-x2) b) (1-A)-1/x c) (1-A)+1/x2 d) (A-x)/x3 8. What is the generating function for the sequence with closed formula an=4(7n)+6(−2)n? a) (4/1−7x)+6! b) (3/1−8x) c) (4/1−7x)+(6/1+2x) d) (6/1-2x)+8 9. Suppose G is the generating function for the sequence 4, 7, 10, 13, 16, 19,…, the find a generating function (in terms of G) for the sequence of differences between terms. a) (1−x)G−4/x b) (1−x)G−4/x3 c) (1−x)G+6/x d) (1−x)G−x2 10. Find the sequence generated by 1/1−x2−x4.,assume that 1, 1, 2, 3, 5, 8,… has generating function 1/1−x−x2. a) 0, 0, 1, 1, 2, 3, 5, 8,… b) 0, 1, 2, 3, 5, 8,… 166 CU IDOL SELF LEARNING MATERIAL (SLM)

c) 1, 1, 2, 2, 4, 6, 8,… d) 1, 4, 3, 5, 7,… Answers: 1 – c; 2 – b ; 3 – a ; 4 – c ; 5 - b; 6 – a ; 7 – b; 8 – c; 9 – a; 10 – a. 8.9 REFERENCES • Kenneth Rosen, Discrete Mathematics and Its Applications with Combinatorics and Graph Theory (SIE) | 7th Edition, McGraw Hill Education; 7 editions • Jean-Paul Tremblay, R Manohar, Discrete Mathematical Structures with Applications to Computer Science, McGraw Hill Education; 1st edition • Susanna S. Epp, Discrete Mathematics with Applications, Cengage Learning • Seymour Lipschutz, Marc Lara’sLipson, Varsha H. Patil, Discrete Mathematics (Schaum's Outlines) | Revised 3rd Edition, McGraw Hill Education; Revised Third edition • C Liu, D. Mohapatra, Elements of Discrete Mathematics: A Computer Oriented Approach | 4th Edition, McGraw Hill Education • V.K. Balakrishnan, Introductory Discrete Mathematics (Dover Books on Computer Science),Dover Publications Inc • Miklos Bona Introduction to Enumerative and Analytic Combinatorics (Discrete Mathematics and Its Applications) 2nd Edition, Chapman and Hall/CRC • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 167 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 9- GENERATING FUNCTION 2 Structure 9.0. Learning Objectives 9.1. Introduction 9.2. Solution of recurrence relation using G.F, 9.3. Solution of combinatorial problem using G.F. 9.4. Summary 9.5. Keywords 9.6. Learning Activity 9.7. Unit End Questions 9.8. References 9.0 LEARNING OBJECTIVES: After studying this unit, you will be able to: • Outline the solution of Recurrence relation using Generating Function by translating a recurrence relation for the terms of a sequence into an equation involving a generating function. • Discuss to prove combinatorial identities using Generating Function. 9.1 INTRODUCTION In combinatorics, there are two powerful tools that help us to solve many problems, namely recurrence relation and generating function. Recurrence relation arises naturally in definitions of sequences or when we try to break the problem into cases, some of which is similar to the original problem. Generating functions are closely related to sequences, and can be used to solve recurrence relations and other kinds of problems such as enumeration problems and proving identities involving sequences. A generating function is a (possibly infinite) polynomial whose coefficients correspond to terms in a sequence of numbers an. Due to their ability to encode information about an integer sequence, generating functions are powerful tools that can be used for solving recurrence relations. Techniques such as partial fractions, polynomial multiplication, and derivatives can help solve the recurrence relations. 168 CU IDOL SELF LEARNING MATERIAL (SLM)

9.2 SOLUTION OF RECURRENCE RELATION USING G.F, Solving Recurrence Relation: We will consider the following example to clarify the different methods. 1. Solve the recurrence relation an = an – 1 + ƒ (n) for n ≥ 1 by substitution. a1=a0 + ƒ (1) a2 =a1 + ƒ (2) = [a0 + ƒ (1)] + ƒ (2) a3 =a2 + ƒ (3) = [a0 + ƒ (1) + ƒ (2)] + ƒ (3) . . . an = a0 + ƒ (1) + ƒ (2) + …+ ƒ (n) = ������0 + ∑∞������ ������(������) Moreover generally, if c is a constant then we can solve a0 = can- 1 + ƒ (n) for n ≥ 1 in the same way: a1=c a0 + ƒ (1) a2= c a1 + ƒ (2) = c [c a0 + ƒ (1)] + ƒ (2) = c2 a0 + c ƒ (1) + ƒ (2) a3 =c a2 + ƒ (3) = c [c2 a0 + c ƒ (1) + ƒ (2)] + ƒ (3) = c3 a0 + c2 ƒ (1) + c ƒ (2) + ƒ (3) . . . an= c an – 1 + ƒ (n) = c [ cn - 1 a0 + cn – 2 ƒ (1) + …+ c ƒ (n – 2) + ƒ (n – 1) + ƒ (n) = cn – 1a0 + cn – 1 ƒ (1) + cn – 2 ƒ (2) + …+ c ƒ (n – 1) + ƒ (n) Or 169 CU IDOL SELF LEARNING MATERIAL (SLM)

������ ������������ = ������������������0 + ∑ ������������ ������(������) ������=1 Solution by Generating Functions: First, we will try to understand the shifting properties of generating functions: • If ������(������) = ∑���∞���=0 ������������������������generates the sequence (a0, a1, a2, …), • Then X A(X) generates the sequence (0, a0, a1, a2, …); • X2 A(X) generates the sequence (0,0, a0, a1, a2, …); • In general, Xk A(X) generates the sequence (0, 0…0, a0, a1, a2…) where there are k zeros before a0. • If A(X) is the generating function for the sequence (a0, a1, a2…), then multiply A(X) by X amounts to shifting the sequence one place to the right and inserting a zero in front. • Similarly, if we multiply by Xk amounts to shifting the sequence k positions to the right and inserting k zeros in front. • The above process can be demonstrated in the formal power series expression as follows: ∞∞ ������������������(������) = ������������ ∑ ������������������������ = ������������ ∑ ������������+������ ������=0 ������=0 • If we replace n + k by r and then we will have n = r – k so we have new equation after substitution as ∑∞������=������ ������������−������������������ which signifies that it generates the sequence {������������}∞������=0where 0 = b0 =b1 = … = bk- 1, bk = a0, bk + 1 = a1 and in general br = ar – k if r ≥ k. Thus, the nth term in the new sequence is obtained from the old sequence by replacing an = an – k if n ≥ k and by 0 if n < k. • For instance, we know that 1 / (1 – X) =∑���∞���=0 ������������generates the sequence (1, 1, 1, …), that is, the sequence {������������}���∞���=0where an = 1 for each n ≥ 0. • Thus, ∞∞ ������ 1 − ������= ∑ ������������+1 = ∑ ������������ ������=0 ������=1 Generates (0, 1, 1, 1, …) and ∞∞ ������2 1 − ������ = ∑ ������������+2 = ∑ ������������ ������=0 ������=2 Generates (0,0, 1, 1, 1, …). Similarly, 170 CU IDOL SELF LEARNING MATERIAL (SLM)

∞∞ 1 (1 − ������)2 = ∑ ������(������ + 1, ������)������������ = ∑(������ + 1)������������ ������=0 ������=2 Generates the sequence (1, 2, 3, 4 …) so that ∞∞ ������ (1 − ������)2 = ∑(������ + 1)������������+1 = ∑ ������������������ ������=0 ������=1 Generates the sequence {������}���∞���=0= (0, 1, 2, 3, 4…). [∑∞������=1 ������������������describes the coefficient of X0 is 0 because the sum is taken from r = 1 to ∞, but still, we get same conclusion] So, we can write ∞∞ ������ (1 − ������)2 = ∑ ������������������ ������������������������������ = ∑ ������������������ ������=1 ������=0 Both the above expression indicates that the coefficient of ������0 is zero. Similarly, ∞∞ ������2 (1 − ������)2 = ∑(������ + 1)������������+2 = ∑(������ − 1)������������ ������=0 ������=2 Generates the sequence (0, 0, 1, 2, 3, 4…) that is the sequence {������������}∞������=0where br = r – 1 if r ≥ 2 but 0 = b0 = b1 . Since, the expression br = r – 1 equal to zero when r = 1, we can write the expression ������2 = ∑∞ (������ − 1)������������as∑∞ (������ − 1)������������. ������=2 ������=1 (1−������)2 Following the above procedure, 1 ∞ ∞(������ + 2)(������ + 1) = ∑ ������(������ + 2, ������)������������ = ∑ ������������ (1 − ������)3 2 ������=0 ������=0 Generates the sequence {(������ + 2)(������ + 1) ∞ 1.2 2.3 3.4 } =( , , 2 ������=0 2 2 2 , … ), and therefore, 171 CU IDOL SELF LEARNING MATERIAL (SLM)

generates ∞ 2 = ∑(������ + 2)(������ + 1)������������ (1 − ������)3 ������=0 {(������ + 2)(������ + 1)}���∞���=0 = (1.2,2.3,3.4, … ). But then, ∞∞ 2������ (1 − ������)3 = ∑(������ + 2)(������ + 1)������������+1 = ∑(������ + 1)(������)������������ ������=0 ������=1 generates the sequence (0, 1.2,2.3,3.4,…). Now since ������������ = (������ + 1)(������) equals 0 where r = 0, we can write 2������ ∞∞ − ������)3 (1 = ∑(������ + 1)(������)������������ = ∑(������ + 1)(������)������������ ������=1 ������=0 so that 2������ generates {(������ + 1)(������)}���∞���=0. (1−������)3 Similarly, 2������2 ∞ ∞∞ (1 − ������)3 = ∑(������ + 2)(������ + 1)������������+2 = ∑(������)(������ − 1)������������ = ∑(������)(������ − 1)������������ ������=0 ������=2 ������=0 generates the sequence (0,0,1.2,2.3,3.4,…) and the last sum can be taken from 0 to ∞ because the coefficient r ( r – 1) is 0 when r = 0, 1. In this way, we can combine these results to obtain generating functions for other sequences. For example, 2������ ������ ������(1 + ������) (1 − ������)3 − (1 − ������)2 = (1 − ������)3 generates the sequence {(������ + 1)(������) − ������}∞ = {������2}∞ = (0,1,4,9, … ) ������=0. ������=0. In the similar way, 1 ∞∞ (1 − ������)4 = ∑ ������(������ + 3, ������)������������ = ∑ (������ + 3)(������ + 2)(������ + 1) ������������ 6 ������=0 ������=0 172 CU IDOL SELF LEARNING MATERIAL (SLM)

generates{(������+3)(������+2)(������+1)}∞ ; 6 generates {( + )( + )( + )}∞ (1−������)4 ������ 3 ������ 2 ������ 1 ������=0; 6 ������=0 6������ ∞ (1 − ������)4 = ∑(������ + 3)(������ + 2)(������ + 1)������������+1 ������=0 ∞ = ∑(������ + 2)(������ + 1)(������)������������ ������=1 ∞ = ∑(������ + 2)(������ + 1)(������)������������ ������=0 generates{(������ + 2)(������ + 1)(������)}���∞���=0.; ������������������ 6������2 ∞ (1 − ������)4 = ∑(������ + 3)(������ + 2)(������ + 1)������������+2 ������=0 ∞ = ∑(������ + 1)(������)(������ − 1)������������ ������=1 ∞ = ∑(������ + 1)(������)(������ − 1)������������ ������=0 generates{(������ + 1)(������)(������ − 1)}���∞���=0. Since (������ + 3)(������ + 2)(������ + 1) = ������3 + 6������2 + 11������ + 6 then ������3 = (������ + 3)(������ + 2)(������ + 1) − 6������2 − 11������ − 6 so that {������3}∞������=i0s generated by 6 6(������)(1 + ������) ������ 6 ������(1 + 4������ + ������2) (1 − ������)4 − (1 − ������)3 − 11 (1 − ������)2 − (1 − ������) = (1 − ������)4 In similar way we can find the generating functions for the sequences{������4}∞ , {������5}∞ and so on. ������=0 ������=0 2. If ������(������) = ∑���∞���=0 ������������������������ generates the sequence (a0, a1, a2, …), then ������(������) − ������0 = ∑∞������=1 ������������������������generates the sequence (0, a1, a2, …) and in general 173 CU IDOL SELF LEARNING MATERIAL (SLM)

������(������) − ������0 − ������1������ − ⋯ − ������������−1������������−1 = ∑∞������=������ ������������������������generates( 0, 0, …,0, ak, ak+ 1…), where there are k zeros before ak.But when we divide it by powers of X shifts the sequence to the left like for example, ������(������)−������0 = ∑∞������=1 ������ ������������−1 generates the sequence (������ , ������ , ������ , … ); ������(������)−������0−������1������ generates ������ ������2 ������ 123 (������2, ������3, ������4, … ); and inn general for ������ ≥ 1, ������(������)−������0−������1������������−������⋯−������k−1������������−1generates(������������, ������������+1 , ������������+2 , … ). Similarly, if we substitute n – k = r and the expression ������−1 = ������(������)−������0−������1������−⋯−������������−1������ ������������ ∑∞������=������ ������������������������−������becomes ∑���∞���=0 ������������+������������������which generates the sequence(������������, ������������+1, ������������+2, … ). Other way round, the term ������������ in the original sequence is replaced by ������������+������ for each n, indicating that the sequence has been shifted k places to the left. Example 1: Solve the recurrence relation ������������ − 7������������−1 + 10������������−2 = 0 forn ≥ 0 Solution: We will number the steps of the procedure. 1. Let ������(������) = ∑���∞���=0 ������������������������. 2. Next multiply each term in the recurrence relation by Xn and sum from 2 to ∞: ∞∞ ∞ ∑ ������������������������ − 7 ∑ ������������−1������������ + 10 ∑ ������������−2������������ = 0 ������=2 ������=2 ������=2 3. Replace each infinite sum by an expression from the table of equivalent expressions: [A(X) – a0 – a1X] – 7 X [A(X) – a0] + 10 X2 [A(X)] 4. Then simplify: A(X) (1 – 7 X + 10 X2) = a0 + a1X – 7 a0X or ������(������) = ������0 + (������1 − 7������0)������ = ������0 + (������1 − 7������0)������ 1 − 7������ + 10������2 (1 − 2������)(1 − 5������) 5. Decompose A(X) as a sum of partial fractions: ������(������) = ������1 + ������2 1 − 2������ 1 − 5������ 174 CU IDOL SELF LEARNING MATERIAL (SLM)

where C1 and C2 are constants, as yet undetermined. 6. Express A(X) as a sum of familiar series: ������(������) = ������1 + ������2 ∞∞ = ������ ∑ 2������������������ + ������ ∑ 5������������������ 1 − 2������ 1 − 5������ 1 2 ������=0 ������=0 7. Express an as the coefficient of Xn in A(X) and in the sum of the other series: an = C1 2n + C2 5n 8. Now the constants C1 and C2 are uniquely determined once values for a0 and a1 are given. For example, if a0 = 10 and a1 = 41, we may use form of the general solution an = C1 2n + C2 5n , and let n = 0 and n = 1 to obtain the equations C1 + C2 = 10 and 2C1 + 5C2 = 41, which determine the values C1 = 3 and C2 =7. The unique solution of the recurrence relation is an= (3)2n + (7)5n THEOREM: If {������������}∞������=0 is a sequence of numbers which satisfy the linear recurrence relation with constant coefficients an + c1 an - 1 +… + ck an - k = 0, where ������������ ≠ 0, and n ≥ k, then the generating function ������(������) = ∑���∞���=0 ������������������������ equals P(X) / Q(X), where P(X) = a0 + (a1 + c1 a0 ) X + … +( ak- 1 + c1 ak - 2 + … + ck – 1 a0) Xk – 1 and Q(X) = 1 + c1 X + … + ck Xk. Conversely, If P(X) and Q(X) are polynomials given, where P(X) has degree less than k, there is a sequence {������������}∞������=w0 hose generating function is A(X) = P(X) / Q(X). The sequence {������������}∞������=s0atisfies a linear homogenous recurrence relation with constant coefficients of degree k, where the coefficients of the recurrence relation are the coefficients of Q(X). In fact, if Q(X) = b0 + b1 X + … + bkXk where������0 ≠ 0 and ������������ ≠ 0then ������(������) = ������ (1 + ������1 ������ + ⋯ + ������������ ������������) 0 ������0 ������0 175 CU IDOL SELF LEARNING MATERIAL (SLM)

= ������0(1 + ������1������ + ⋯ + ������������������������) where ci = bi/ b0 for i ≥ 1. Then ������(������) = ������(������) = 1 + 1 ������(������) ������������������������ ������(������) ������0 ������1������ + ⋯ and the coefficient of A(X) are discovered by using partial fractions and the factors of 1 + c1 X + … + ck Xk. then the recurrence relation satisfied by the coefficients of A(X) is an + c1 an- 1 + … + ck an – k = 0. Example 2: Solve the following recurrence relations using generating functions. a. an – 9an- 1 + 20an- 2 = 0 for n ≥ 2 and a0 = – 3, a1 = – 10 b. an – 5an- 1 + 6an- 2 = 0 for n ≥ 2 and a0 = 1 , a1 = – 2 c. an – 3an- 2 + 2an- 3 = 0 for n ≥ 3 and a0 = 1, a1 = 1, a2 = 2. d. an + an- 1 – 16 an- 2+ 20an- 3 = 0 for n ≥ 3 and a0 = 1, a1 = 1, a2= - 1 Solution: a. an = 2.5n – 5.4n b. A(X) = [1 – 7 X] / [1 – 5X + 6 X2] = [ 5 / 1 – 2X] – [ 4 / 1 – 3X]; an= 5(2n) – 4(3n) c. an = 8 / 9 – 6/ 9 n + 1/ 9 ( - 2 )n d. A(X) = [X / 1 + X – 16X2 + 20 X3] −2/49 7/49 5/49 = 1 − 2������ + (1 − 2������)2 − 1 + 5������ ������������ = −2/49(2������) + 7/49(������ + 1)(2������) − 5/49(−5)������ 9.3 SOLUTION OF COMBINATORIAL PROBLEM USING G.F. The problem is to calculate for all values of n: To accomplish this we construct the generating function 176 CU IDOL SELF LEARNING MATERIAL (SLM)

This is a formal inÖnite sum. No convergence is implied. The generating function for just one type, say Ak, looks like Thus we can select n objects in 1 way if Ak allows that. Here are a few examples of generating functions for just one type Note that the only coefficients we see are 1, the terms that don’t appear are the ones with coe¢ cient 0 and correspond to selections that the type does NOT allow. In the Örst case the type allows for 0 or 1 object to be selected. In the second case any number of objects. In the third case at least r objects. In the fourth case only an odd number of objects. Finally, the last case is when the type allows a number of objects that is a prime number. Going back to our general problem we deÖne the generating function for each type as The claim is that the original generating function is the product of the generating functions for the types: 177 CU IDOL SELF LEARNING MATERIAL (SLM)

The product on the right can be multiplied out more easily if we use different indices for n in each sum. When manipulating such sums, you should work with them as if they were multiple integrals with n1, ..., nk being the variables and be happy that no inÖnitesimals are messing up the calculations Thus, we must show that but this is simply our recurrence formula At this point we seem to have achieved absolutely nothing. When we get to the examples below, we shall see that the advantage of this method is that we really can work with generating functions as functions 9.4 SUMMARY A generating function is a (possibly infinite) polynomial whose coefficients correspond to terms in a sequence of numbers an. Due to their ability to encode information about an integer sequence, generating functions are powerful tools that can be used for solving recurrence relations. When generating functions are used to solve counting problems, they are usually considered to be formal power series. One potential benefit to the generating function approach for nonhomogeneous equations is that it does not require determining an appropriate form for the particular solution. However, the method of generating functions often requires that the resulting generating function be expanded using partial fractions. 178 CU IDOL SELF LEARNING MATERIAL (SLM)

9.5 KEYWORDS • Coefficient: is a number multiplied by a variable • Sequence: is an enumerated collection of objects in which repetitions are allowed and order matters. • Decompose:To breaking something into parts, that together are the same as the original. • Series: is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. • Determine: To fix or define the position, form, or configuration of. 9.6 LEARNING ACTIVITY 1. Solve the recurrence relation hn = 5hn−1 −6hn−2 with i. c. h0 = 1 and h1 = −2. 2. Find the generating function for the Fibonacci numbers {Fn}, using the initial conditions F0 = F1 = 1, and the recurrence relation Fn+2 = Fn+1 + Fn. 9.7 UNIT END QUESTIONS A. Descriptive Type Question 1. Discuss the concept of Recurrence Relation 2. Explain Recurrence Relations using Generating Function 3. What do you understand by solution of combinatorial problem using G.F.? 4. Explain shifting properties of Generating functions 5. Explain solution of recurrence relation by substitution B. Multiple choice Questions: 1. How many ways are there to make a sum of 10, using exactly one element from each of the following two sets: {2,3,6,7} and {3,4,5,8}? a) 3 ways of making 10 b) 5 ways of making 10 179 CU IDOL SELF LEARNING MATERIAL (SLM)

c) 7 ways of making 10 d) 9 ways of making 10 2. Find the generating function for the face value of 1 die a) R1(x) = x1- x2+ x3 + x4 - x5 + x6 b) R1(x) = x1 - x2+ x3 + x4 + x5 + x6 c) R1(x) = x1+ x2+ x3 + x4 + x5 + x6 d) R1(x) = x1+ x2+ x3 + x4 - x5 - x6 3. In general, Xk A(X) generates the sequence (0, 0…0, a0, a1, a2…) where there are zeros before a0. a) k-1 b) k c) k + 2 d) 2k 4. In the sum of terms, the highest degree of a term is the degree of the . a) recurrence b) Largest number c) Smallest number d) Denominator 5. What is the degree of linear recurrence? a) 0 b) 1 c) -2 d) 3 6. If the recurrence (without initial conditions) applies to the sequence consisting only of 0's then the recurrence is a) Normal b) Linear c) Standard d) homogeneous 180 CU IDOL SELF LEARNING MATERIAL (SLM)

7. If all the terms in a recurrence involve only previous terms and a constant multiplier, then the recurrence has a). Constant coefficients b). Linear coefficient c). Ascending coefficient d). Descending coefficient 8. A recurrence of order k needs initial terms to define it completely a). k b). k/2 c). 2k d). 2k+1 9. If A(X) is the generating function for the sequence (a0, a1, a2…), then multiply A(X) by amounts to shifting the sequence one place to the right and inserting a zero in front. a). 2X b). X c). 3X d). X/4 10. If P(X) and Q(X) are polynomials given, where P(X) has degree less than k, there is a sequence {������������}∞������=w0 hose generating function is a). A(X) = P(X) / Q(X). b). A(X) = P(X) / 2Q(X). c). A(X) = 2P(X) / Q(X). d). A(X) = P(X) + Q(X). 181 CU IDOL SELF LEARNING MATERIAL (SLM)

Answers: 1 – a; 2 – c; 3 –d; 4 – a; 5 – b; 6 – d; 7 – a; 8 – a; 9 – b; 10 – a. 9.8 REFERENCES • Kenneth Rosen, Discrete Mathematics and Its Applications with Combinatorics and Graph Theory (SIE) | 7th Edition, McGraw Hill Education; 7 editions • Susanna S. Epp, Discrete Mathematics with Applications, Cengage Learning • Seymour Lipschutz, Marc Lara’sLipson, Varsha H. Patil, Discrete Mathematics (Schaum's Outlines) | Revised 3rd Edition, McGraw Hill Education; Revised Third edition. • Jiri Matousek , Jaroslav Nesetril, Invitation to Discrete Mathematics,OUP Oxford • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond (Undergraduate Texts in Mathematics), Springer • Harry Lewis, Rachel Zax, Essential Discrete Mathematics for Computer Science, Princeton University Press • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 182 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 10- TREES STRUCTURE 10.0. Learning Objectives 10.1. Introduction 10.2. Definition 10.2.1 Basic Terminology: 10.3. Types of tree (rooted, binary), 10.4. Properties of trees, 10.5. Binary search tree, 10.6. Tree traversing (preorder, inorder, postorder). 10.7. Summary 10.8. Keywords 10.9. Learning Activity 10.10. Unit End Questions 10.11. References 10.0 LEARNING OBJECTIVES: After studying this unit, you will be able to: • Explain the concept of trees • State the types and properties of trees • Enumerate tree traversing 10.1 INTRODUCTION A powerful way to represent relationships between objects in visual form can be done using a mathematics structure called a graph. One uses dots called vertices to represent objects and line segments which join the dots, called edges, to represent some relationship between the object which the dots represent. Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes. A tree in which a parent has no more than two children is called a binary tree. A tree or general trees is defined as a non-empty finite set of elements called vertices or nodes having the property that each node can have minimum degree 1 and maximum degree n. It can be partitioned into n+1 disjoint subset such that the first subset contains the root of the tree and remaining n subsets includes the elements of the n subtree. 183 CU IDOL SELF LEARNING MATERIAL (SLM)

10.2 DEFINITION • A tree is a simple graph G such that there is a unique simple nondirected path between each pair of vertices of G. • A rooted tree is a tree in which there is one designated vertex, called a root. • A rooted tree is a directed tree if there is a root from which there is a directed path to each vertex. In such case there is exactly one such root. • The level of a vertex v in a rooted tree is the length of the path to v from the root. • A tree T with only one vertex is called a trivial tree; otherwise, it is a nontrivial tree. 10.2.1 Basic Terminology: 1. Root- • The first node from where the tree originates is called as a root node. • In any tree, there must be only one root node. • We can never have multiple root nodes in a tree data structure. Example- Fig 10.1: Representation of Root node 184 CU IDOL SELF LEARNING MATERIAL (SLM)

Here, node A is the only root node. 2. Edge- • The connecting link between any two nodes is called as an edge. • In a tree with n number of nodes, there are exactly (n-1) number of edges. Example- Fig 10.2: Representation of Edge 3. Parent- • The node which has a branch from it to any other node is called as a parent node. • In other words, the node which has one or more children is called as a parent node. • In a tree, a parent node can have any number of child nodes. Example- 185 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 10.1: Representation of Parent node Here, • Node A is the parent of nodes B and C • Node B is the parent of nodes D, E and F • Node C is the parent of nodes G and H • Node E is the parent of nodes I and J • Node G is the parent of node K 4. Child- • The node which is a descendant of some node is called as a child node. • All the nodes except root node are child nodes. Example- 186 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 10.4: Representation of child Here, • Nodes B and C are the children of node A • Nodes D, E and F are the children of node B • Nodes G and H are the children of node C • Nodes I and J are the children of node E • Node K is the child of node G 5. Siblings- • Nodes which belong to the same parent are called as siblings. • In other words, nodes with the same parent are sibling nodes. Example- 187 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 10.5: Representation of siblings Here, • Nodes B and C are siblings • Nodes D, E and F are siblings • Nodes G and H are siblings • Nodes I and J are siblings 6. Degree- • Degree of a node is the total number of children of that node. • Degree of a tree is the highest degree of a node among all the nodes in the tree. Example- 188 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 10.6: Representation of Degree 189 Here, • Degree of node A = 2 • Degree of node B = 3 • Degree of node C = 2 • Degree of node D = 0 • Degree of node E = 2 • Degree of node F = 0 • Degree of node G = 1 • Degree of node H = 0 • Degree of node I = 0 • Degree of node J = 0 • Degree of node K = 0 7. Internal Node- • The node which has at least one child is called as an internal node. • Internal nodes are also called as non-terminal nodes. • Every non-leaf node is an internal node. CU IDOL SELF LEARNING MATERIAL (SLM)

Example- Fig 10.7: Representation of Internal node Here, nodes A, B, C, E and G are internal nodes. 8. Leaf Node- • The node which does not have any child is called as a leaf node. • Leaf nodes are also called as external nodes or terminal nodes. Example- Fig 10.8: Representation of Leaf Node 190 CU IDOL SELF LEARNING MATERIAL (SLM)

Here, nodes D, I, J, F, K and H are leaf nodes. 9. Level- • In a tree, each step from top to bottom is called as level of a tree. • The level count starts with 0 and increments by 1 at each level or step. Example- Fig 10.9: Representation of Level 10. Height- • Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node. • Height of a tree is the height of root node. • Height of all leaf nodes = 0 Example- 191 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 10.10: Representation of Height Here, • Height of node A = 3 • Height of node B = 2 • Height of node C = 2 • Height of node D = 0 • Height of node E = 1 • Height of node F = 0 • Height of node G = 1 • Height of node H = 0 • Height of node I = 0 • Height of node J = 0 • Height of node K = 0 11. Depth- • Total number of edges from root node to a particular node is called as depth of that node. • Depth of a tree is the total number of edges from root node to a leaf node in the longest path. • Depth of the root node = 0 • The terms “level” and “depth” are used interchangeably. 192 CU IDOL SELF LEARNING MATERIAL (SLM)

Example- Fig 10.11: Representation of Depth 193 Here, • Depth of node A = 0 • Depth of node B = 1 • Depth of node C = 1 • Depth of node D = 2 • Depth of node E = 2 • Depth of node F = 2 • Depth of node G = 2 • Depth of node H = 2 • Depth of node I = 3 • Depth of node J = 3 • Depth of node K = 3 12. Subtree- • In a tree, each child from a node forms a subtree recursively. • Every child node forms a subtree on its parent node. CU IDOL SELF LEARNING MATERIAL (SLM)

Example- Fig 10.12: Representation of Subtree Example 1: Two trees, ������1 and ������2 are shown in figure 10.1. ������1 = (������, ������1)and������2 = (������, ������2) where ������ = {������, ������, ������, ������, ������, ������, ������, ℎ, ������, ������} ������1 = {{������, ������}, {������, ������}, {������, ������}, {������, ������}, {������, ������}, {������, ������}, {������, ������}, {ℎ, ������}, {������, ������}}and ������2 = {{������, ������}, {������, ������}, {������, ������}, {������, ������}, {������, ������}, {������, ������}, {������, ������}, {ℎ, ������}, {������, ������}} 194 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 10.13: Two kinds of nondirected trees Neither of these trees is a directed tree. If vertex c is designated as the root of each tree, vertex j is at level 4 in ������1 and at level 3 in������2. Example 2: A directed tree T is shown in figure 2 ������ = (������, ������)where������ = {������, ������, ������, ������, ������, ������, ������, ℎ} and ������ = {(������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ������), (������, ℎ)}. The root of T is the vertex a and the vertices at level 2 are e and f. Figure :10. 14Directedtrees Concept: Two vertices suppose a and b of a graph are said to be connected if there is a nondirected path from a to b in G and then the graph G is connected if each pair of its vertices is connected. If we define a Relation R on the vertices of a graph G by ������������������ if a and b are connected then R is an equivalence relation. We can partitioned the vertices of G into disjoint nonempty sets ������1, ������2, … , ������������ and the subgraphs ������1, ������2, … , ������������ of G induced by ������1, ������2, … ������������������������������, respectively are called the connected components of G or simply the components of G and it is generally denoted by C(G) and if C(G)=1 it implies G is connected. A connected subgraph H of a graph G is a component of G if for each connected subgraph F of G where ������ ⊆ ������ ⊂ ������, ������(������) ⊆ ������(������)and ������(������) ⊆ ������(������), then it follows that H = F. If a graph G is connected and e is an edge such that ������ − ������ is not connected, then e is said to be a bridge or a cut edge. If v is a vertex of G such that ������ − ������ is not connected, then v is a cut vertex. Example 3: Let G be the graph depicted in figure in unit7. This graph G has 3 components; the vertices a and d are connected as are i and g and j and k are not connected. Moreover, c is a cut vertex of the first component. THEOREM: A simple non-directed graph G is a tree if G is connected and contains no cycles. PROOF: Suppose that G is a tree. Since each pair of vertices are joined by a path, G is connected. If G contains a cycle containing distinct vertices u and v, then u and v are joined by at least two simple 195 CU IDOL SELF LEARNING MATERIAL (SLM)

paths, the one along one portion of the cycle and the other part completing the cycle. The above discussion contradicts the hypothesis which states that there is a unique path between u and v, and thus a tree has no cycles. Conversely, assume that G is connected and contains no cycles. Let a andb be any pair of vertices of G. If there are two different simple paths, ������1 and ������2 from a tob, then we can find cycle in G as follows: Since ������1 and ������2 are different paths there must be a vertex ������1 (like ������1 = ������) on both paths such that the vertex following ������1 on ������1 is not the same as the vertex following ������1 on ������2. Since ������1 and ������2 terminate at b, there is a first vertex after v1, call it’s������2, which ������1 and ������2 have common (possibly ������2 = ������). Thus, the part of ������1 from ������1 to ������2 form a cycle in G. This contradicts the assumption that G has no cycles. Therefore, G has exactly one path joining a andb. THEOREM: In every nontrivial tree there is at least one vertex of degree one. PROOF: Let us start at any vertex say ������1. If ������������������(������1) ≠ 1, move along any edge to vertex ������2 incident with ������1. If ������������������(������2) ≠ 1 continue to vertex ������3 along a different edge and continue it to produces a path ������1 − ������2 − ������3 − ������4 …( it indicates that there is an edge from ������1 to ������2, one from ������2 to ������3 and so on.) None of the ������������′������ is repeated in this path since then we would have circuit – which a tree may not have. Since the number of vertices in the graph is finite, the graph must end somewhere and there should be a vertex of degree 1 as we can enter this vertex but cannot leave it. THEOREM: A tree with n vertices has exactly n – 1 edge. PROOF: We will use mathematical induction on the number of vertices. If n = 1, there are no edges. Hence, the result is trivial for n = 1. Assume, then, for ������ ≥ 1 that all the trees with n vertices have exactly n – 1. Now consider an arbitrary tree with n + 1 edges. With reference to the previous theorem, there is a vertex v in T of degree 1. Let us consider the figure 3 where let us prune this tree by removing this vertex v and its associated edge e from T and consider it as ������′ = ������ − ������. Figure 10.15 Tree representing vertices and edge for stated Theorem 196 CU IDOL SELF LEARNING MATERIAL (SLM)

T’ has n vertices and one edge less than T. Also, T’ is connected as for any pair of vertices say a and b in T’, there is a unique simple path from a to b in T and this path is not affected by the removal of the vertex v and edge e. There are no cycles in T’ as there were none in T. Thus, T’ is a tree and inductive hypothesis implies that it has n – 1 edge and so T must have n edges as it has one more edge as compare to T’. COROLLARY: If G is a nontrivial tree then G contains at least two vertices of degree 1. PROOF: Let n be the number of vertices of graph G. By the sum of degrees formula, ������ ∑ ������������������(������������) = 2|������| = 2(������ − 1) = (2������ − 2) ������=1 Now if there is only one vertex, say ������1, of degree 1, then ������������������(������������) ≥ 2for������ = 2, … , ������ And ∑ ������ ������������������(������������) = 1 + ∑������������=2 ������������������(������������) ≥ 1 + 2������ − 2 = 2������ − 1 ������=1 But then 2������ − 2 ≥ 2������ − 1 ������������ − 2 ≥ −1, ������������������������������������������������������������������������������������ Example 4: There are 6 non-isomorphic trees with 6 vertices as depicted in Figure 10.16 as below. Figure 10.16: 6 non-isomorphic trees with 6 vertices for Example 4 THEOREM: If 2 non adjacent vertices of a tree T are connected by adding an edge, then the resulting graph will contain a cycle. PROOF: If T has n- vertices then T has n – 1 edge and if additional edge is added to the edges of T the resulting graph G has n vertices and n edges. Hence G cannot be a tree by previous theorem. Incase, if the addition of an edge has not affected the connectivity. Hence G must have cycle. 197 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 5: As shown in below figure, if any of the dotted line is added to the tree it will create a cycle. Figure 10. 17 Tree depicting how to create cycle for Example 5 THEOREM: A graph G is a tree if and only if G has no cycles and |������| = |������| − 1. PROOF: We are interested to show that if G has no cycles and |������| = |������| − 1 , then G is connected. Let us consider the components of the G and denote it by ������1, ������2, … , ������������where ������ ≥ 1. Assume |������������|= the number of vertices of ������������. Now each ������������ is a tree which contains no cycles and hence they are connected. Thus, ������������has |������������| − 1edges. Hence G has (|������1| − 1) + (|������2| − 1) + ⋯ + (|������������| − 1) = |������1| + |������2| + ⋯ + |������������| − ������ = |������| − ������ edges. Thus, k = 1, and G is connected. 10.3 TYPES OF TREES Ordered Trees: If in a tree at each level, an ordering is defined, then such a tree is called an ordered tree. Example 6: The trees shown in the figures represent the same tree but have different orders. 198 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 10. 18: Tree representing different order Rooted Trees: If a directed tree has exactly one node or vertex called root whose incoming degrees is 0 and all other vertices have incoming degree one, then the tree is called rooted tree. Figure 10. 19: Rooted tree 10.4 PROPERTIES OF TREES: 1. There is only one path between each pair of vertices of a tree. 2. If a graph G there is one and only one path between each pair of vertices G is a tree. 3. A tree T with n vertices has n-1 edges. 4. A graph is a tree if and only if it a minimal connected. 10.5 BINARY SEARCH TREES: If the outdegree of every node is less than or equal to 2, in a directed tree than the tree is called a binary tree. A tree consisting of the nodes (empty tree) is also a binary tree. A binary tree is shown in fig: Basic Terminology: Root: A binary tree has a unique node called the root of the tree. 199 Left Child: The node to the left of the root is called its left child. CU IDOL SELF LEARNING MATERIAL (SLM)


Like this book? You can publish your book online for free in a few minutes!
Create your own flipbook