MFC-UNIT-2-5.Inclusion-Exclusion

 

	Inclusion-Exclusion
1.	Which one of the following problem types does inclusion-exclusion principle belong to? a) Numerical problems b) Graph problems c) String processing problems d) Combinatorial problems Answer: d Explanation: Inclusion-Exclusion principle is a kind of combinatorial problem. It is a counting technique to obtain the number of elements present in sets( two, three , etc.,).	D
2.	Which of the following is a correct representation of inclusion exclusion principle (|A,B| represents intersection of sets A,B)? a) |A U B|=|A|+|B|-|A,B| b) |A,B|=|A|+|B|-|A U B| c) |A U B|=|A|+|B|+|A,B| d) |A,B|=|A|+|B|+|A U B| Answer: a Explanation: The formula for computing the union of two sets according to inclusion-exclusion principle is |A U B|=|A|+|B|-|A,B| where |A,B| represents the intersection of the sets A and B.	A
3.	____________ is one of the most useful principles of enumeration in combinationatorics and discrete probability. a) Inclusion-exclusion principle b) Quick search algorithm c) Euclid’s algorithm d) Set theory Answer: a Explanation: Inclusion-exclusion principle serves as one of the most useful principles of enumeration in combinationatorics and discrete probability because it provides simple formula for generalizing results.	A
4.	Which of the following is not an application of inclusion-exclusion principle? a) Counting intersections b) Graph coloring c) Matching of bipartite graphs d) Maximum flow problem Answer: d Explanation: Counting intersections, Graph coloring and Matching of bipartite graphs are all examples of inclusion-exclusion principle whereas maximum flow problem is solved using Ford-Fulkerson algorithm.	D
5.	Who invented the concept of inclusion-exclusion principle? a) Abraham de Moivre b) Daniel Silva c) J.J. Sylvester d) Sieve Answer: a Explanation: The concept of inclusion- exclusion principle was initially invented by Abraham de Moivre in 1718 but it was published first by Daniel Silva in his paper in 1854.	A
6.	According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is even. a) True b) False Answer: b Explanation: According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is odd and excluded if n is even.	B
7.	With reference to the given Venn diagram, what is the formula for computing |AUBUC| (where |x, y| represents intersection of sets x and y)? a) |A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C| b) |A, B,C|=|A|+|B|+|C|-|A U B|-|A U C|-|B U C|+|A U B U C| c) |A, B,C|=|A|+|B|+|C|+|A,B|-|A,C|+|B,C|+|A U B U C| d) |A U B U C|=|A|+|B|+|C| + |A,B| + |A,C| + |B,C|+|A, B,C| Answer: a Explanation: The formula for computing the union of three sets using inclusion-exclusion principle is|A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C| where |A,B|, |B,C|, |A,C|, |A,B,C| represents the intersection of the sets A and B, B and C, A and C, A, B and C respectively.	A
8.	Which of the following statement is incorrect with respect to generalizing the solution using the inclusion-exclusion principle? a) including cardinalities of sets b) excluding cardinalities of pairwise intersections c) excluding cardinalities of triple-wise intersections d) excluding cardinalities of quadraple-wise intersections Answer: c Explanation: According to inclusion-exclusion principle, an intersection is included if the intersecting elements are odd and excluded, if the intersecting elements are even. Hence triple-wise intersections should be included.	C
9.	Counting intersections can be done using the inclusion-exclusion principle only if it is combined with De Morgan’s laws of complementing. a) true b) false Answer: a Explanation: The application of counting intersections can be fulfiled if and only if it is combined with De Morgan laws to count the cardinality of intersection of sets.	A
10.	Using the inclusion-exclusion principle, find the number of integers from a set of 1-100 that are not divisible by 2, 3 and 5. a) 22 b) 25 c) 26 d) 33 Answer: c Explanation: Consider sample space S={1,…100}. Consider three subsets A, B, C that have elements that are divisible by 2, 3, 5 respectively. Find integers that are divisible by A and B, B and C, A and C. Then find the integers that are divisible by A, B, C. Applying the inclusion-exclusion principle, 100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.	C

 

MFC-UNIT-2-4.Generating Functions

 

	Generating Functions
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,… Answer: c Explanation: Consider the coefficients of each xn term. So a0=4, since the coefficient of x0 is 4 (x0=1 so this is the constant term). Since 15 is the coefficient of x2, so 15 is the term a2 of the sequence. To find a1 check the coefficient of x1 which in this case is 0. So a1=0. Continuing with these we have a2=15, a3=10, a4=25, and a5=16. So we have the sequence 4, 0, 15, 10, 25, 16,…	C
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 Answer: b Explanation: For the sequence 1, 6, 36, 216,… the generating function must be 1/(1−6x,) when basic generating function: 1/1−x.	B
3.	What is the generating function for generating series 1, 2, 3, 4, 5,… ? a) 2/(1−3x) b) 1/(1+x) c) 1/(1−x)2 d) 1/(1−x2) Answer: c Explanation: Basic generating function is 1/1−x. If we differentiate term by term in the power series, we get (1 + x + x2 + x3 +⋯)′ = 1 + 2x + 3x2 + 4x3 +⋯ which is the generating series for 1, 2, 3, 4,….	C
4.	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 Answer: b Explanation: The generating function for the sequence A. Using differencing: A = 1 + 9x + 25x2 + 49x3 + ⋯(1) −xA = 0 + x + 9x2 + 25x3 + 49x4 + ⋯(2) (1−x)A = 1 + 8x + 16x2 + 24x3 +⋯. Since 8x + 16x2 + 24x3 + ⋯ = (1-x)A-1 ⇒ 8 + 16x + 24x2 +…= (1-A)-1/x.	B
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 Answer: b Explanation: The recurrence relation for the sequence 1, 3, 7, 15, 31, 63,… should be an = 3an-1−2an-2. The solution for A: A=1/1 − 3x + 2x2.	B
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,… Answer: a Explanation: The first constant term is 1⋅1, next term will be 1⋅3 + 2⋅1 = 5, the next term: 1⋅5 + 2⋅3 + 3⋅1 = 14, another one: 1⋅7 + 2⋅5 + 3⋅3 + 4⋅1 = 30. The resulting sequence is 1, 5, 14, 30,…	A
7.	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,… Answer: c Explanation: The sequence should be 0, 4, 8, 12, 16, 20,…for the generating function 4x/(1-x)2, when basic generating function: 1/(1-x).	C
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 Answer: c Explanation: For the given sequence after evaluating the formula the generating formula will be (4/1−7x)+(6/1+2x).	C
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 Answer: a Explanation: (1−x)G = 4 + 3x + 6x2 + 9x3 +⋯ which can be accepted. We can compute it like this: 3 + 6x + 9x2 + ⋯ = (1−x)G−4/x.	A
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,… c) 1, 1, 2, 2, 4, 6, 8,… d) 1, 4, 3, 5, 7,… Answer: a Explanation: Based on the given generating function, the sequence will be 0, 0, 1, 1, 2, 3, 5, 8,… which is generated by 1/1−x2−x4.	A