Q1. Which of the following statements are true and which are false? Give reasons for your answer.
- (i)) 'x² + y² - 3 is not dividible by 4.' is a mathematical statement. (75 words)
- (ii)) The number of onto functions from {1,2,3,4,5,6} to {a, b, c, d} is 4!S. (75 words)
- (iii)) The generating function associated with a sequence can never be a polynomial. (75 words)
- (iv)) nlogn∈ O(n²). (75 words)
- (v)) Selection sort is faster than insertion sort in worst case. (75 words)
- (vi)) an = an + n, a1 = 0, where n is a power of 2, is a linear recurrence relation. (75 words)
- (vii)) The generating function of the sequence {1,2, 3, 4, ..., n...} is (1 – z)−2. (75 words)
- (viii)) If g(x) is the generating function for {an}n>1, then (1 - x)g(x) is the generating function for the sequence {bn}n>1 where bn = an − 1, ∀n. (75 words)
- (ix)) The number of partitions of 10 with no part larger than 5 is Qio. (75 words)
- (x)) The number of integer solutions of the equation x1 + x2 + . . . + x10 = 50 in positive integers is (49). (75 words)
Key Points:
- A mathematical statement must have an unambiguous true/false value.
- Onto functions count: `n! * S(m,n)` (Stirling numbers of the second kind).
- Generating functions can be polynomials for finite sequences.
- Big-O notation: `n log n` is asymptotically bounded by `n²`.
Answer: This response provides a comprehensive analysis of ten discrete mathematics statements, classifying each as true or false and providing detailed reasoning based on standard definitions, formulas, and concepts from the BMTC-103 course. Each sub-question addresses a specific topic within discrete mathematics, including logic, combinatorics, generating functions, algorithm analysis, recurrence relations, and integer partitions. The explanations adhere to the specified word limits for each sub-quest...