Combinatorics and Counting Questions and Answers

Q: Consider 4 × 4 matrices with their elements from {0, 1}. The number of such matrices with even number of 1s in every row and every column is

There are 512 such matrices.Fill the top-left 3 × 3 block freely: \(2^{9} = 512\) ways. The last entry of each of the first three rows is then forced, to make that row's count of 1s even, and likewise the last entry of each of the first three columns.The bottom-right corner is forced twice, once by the last row and once by the last column, but both conditions give the same value, because each equals the parity of the 1s in the 3 × 3 block. So every free choice extends to exactly one valid matrix, and the count is \(2^{(4-1)^{2}} = 512\).1025, 1023 and 255 are not powers of 2, but the count must be a power of 2, since these matrices form a vector space over GF(2).

Q: Notation :C(n, r) = n!/(r!*(n-r)!))n! is factorial n.|A| cardinality of set A\(\overline{s}\) is negation of sC(2n, 2) = .....................

The answer is 2C(n, 2) + \(n^{2}\).\[ \begin{aligned} C(2n, 2) &= \frac{2n(2n-1)}{2} = 2n^{2} - n \\ 2C(n, 2) + n^{2} &= n(n-1) + n^{2} = 2n^{2} - n \end{aligned} \]A combinatorial reading gives the same thing: split 2n objects into two groups of n. A pair is either inside the first group, inside the second (2C(n, 2) ways together) or has one object from each group (\(n \times n = n^{2}\) ways).The others do not match: 2C(2n, 1) = 4n, nC(n, 1) + 2n = \(n^{2} + 2n\), and C(n, 2) + \(2n^{2}\) = \(2.5n^{2} - 0.5n\). Trying n = 2 confirms it: C(4, 2) = 6 and 2C(2, 2) + 4 = 6.

Q: A person with list of n items, collects 1st item one (unit) time, 2nd item two (2 units) times, 3rd item three (3 units) times, ........ rth items r times (r units) ....... to his cart while going around the mart ......... number of units will be in his cart by the time he reaches to billing counter, if he has list of 6(n = 6) items for that day procurement.

The cart holds 21 units.The person takes 1 unit of the first item, 2 of the second, and so on up to r units of the rth, so the total for n items is the sum of the first n natural numbers:\[ \begin{aligned} 1 + 2 + \dots + n &= \frac{n(n+1)}{2} \\ &= \frac{6 \times 7}{2} = 21 \end{aligned} \]6 counts only the items, not the units. 42 is \(n(n+1)\), forgetting to halve, and 14 matches no step of the sum.

Q: Given a group of \(n\) married women and their \(n\) husbands at least how many people be chosen from this group of \(2n\) people to guarantee the set contains a married couple ?

At least \(n + 1\) people must be chosen.Think of the \(n\) couples as \(n\) pigeonholes. With \(n + 1\) people chosen, two of them must belong to the same couple, by the pigeonhole principle, so a married couple is guaranteed.With only \(n\) people this can fail: choose all \(n\) wives (or one person from each couple) and no couple appears. So \(n\), and certainly \(n - 1\), are not enough, and \(n + 2\) is more than necessary.

Q: The number of positive integers, not greater than 100 which are not divisible by 2, 3 or 5, is :

There are 26 such integers.Count the numbers up to 100 divisible by 2, 3 or 5 using inclusion-exclusion:\[ \begin{aligned} &50 + 33 + 20 \\ &- (16 + 10 + 6) + 3 = 74 \end{aligned} \](multiples of 2, 3, 5; then of 6, 10, 15; then of 30). So \(100 - 74 = 26\) numbers are divisible by none of them.Check by Euler-type reasoning: in each block of 30 there are \(30(1/2)(2/3)(4/5) = 8\) such numbers, giving 24 up to 90, plus 91 and 97 between 91 and 100, a total of 26.

What is the number of terms in the given expression?

\(\left(x^{2} + \frac{2}{x}\right)^{11}\)

A.12
B.22
C.11
D.24

Exam Year(s)

DSSSB TGT - 2023,

Answer: A

The expression has 12 terms. In the binomial expansion of \((a+b)^{n}\) there are \(n+1\) terms, because the power of \(a\) runs from \(n\) down to 0, which gives \(n+1\) different values. Here \(a = x^{2}\), \(b = \frac{2}{x}\) and \(n = 11\), so \[ \text{number of terms} = 11 + 1 = 12 \] The number 11 is the power and not the count of terms, while 22 and 24 come from doubling the power or the count, which does not follow from the binomial theorem.

Discuss in Forum

Consider 4 × 4 matrices with their elements from {0, 1}. The number of such matrices with even number of 1s in every row and every column is

A.512
B.1025
C.1023
D.255

Exam Year(s)

GATE CS - 2026,

Answer: A

There are 512 such matrices.

Fill the top-left 3 × 3 block freely: \(2^{9} = 512\) ways. The last entry of each of the first three rows is then forced, to make that row's count of 1s even, and likewise the last entry of each of the first three columns.

The bottom-right corner is forced twice, once by the last row and once by the last column, but both conditions give the same value, because each equals the parity of the 1s in the 3 × 3 block. So every free choice extends to exactly one valid matrix, and the count is \(2^{(4-1)^{2}} = 512\).

1025, 1023 and 255 are not powers of 2, but the count must be a power of 2, since these matrices form a vector space over GF(2).

Discuss in Forum

Notation :
C(n, r) = n!/(r!*(n-r)!))
n! is factorial n.
|A| cardinality of set A
\(\overline{s}\) is negation of s

C(2n, 2) = .....................

A.2C(2n, 1)
B.nC(n, 1) + 2n
C.2C(n, 2) + \(n^{2}\)
D.C(n, 2) + \(2n^{2}\)

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: C

The answer is 2C(n, 2) + \(n^{2}\).

\[ \begin{aligned} C(2n, 2) &= \frac{2n(2n-1)}{2} = 2n^{2} - n \\ 2C(n, 2) + n^{2} &= n(n-1) + n^{2} = 2n^{2} - n \end{aligned} \]

A combinatorial reading gives the same thing: split 2n objects into two groups of n. A pair is either inside the first group, inside the second (2C(n, 2) ways together) or has one object from each group (\(n \times n = n^{2}\) ways).

The others do not match: 2C(2n, 1) = 4n, nC(n, 1) + 2n = \(n^{2} + 2n\), and C(n, 2) + \(2n^{2}\) = \(2.5n^{2} - 0.5n\). Trying n = 2 confirms it: C(4, 2) = 6 and 2C(2, 2) + 4 = 6.

Discuss in Forum

A person with list of n items, collects 1st item one (unit) time, 2nd item two (2 units) times, 3rd item three (3 units) times, ........ rth items r times (r units) ....... to his cart while going around the mart ......... number of units will be in his cart by the time he reaches to billing counter, if he has list of 6(n = 6) items for that day procurement.

A.6
B.14
C.21
D.42

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

The cart holds 21 units.

The person takes 1 unit of the first item, 2 of the second, and so on up to r units of the rth, so the total for n items is the sum of the first n natural numbers:

\[ \begin{aligned} 1 + 2 + \dots + n &= \frac{n(n+1)}{2} \\ &= \frac{6 \times 7}{2} = 21 \end{aligned} \]

6 counts only the items, not the units. 42 is \(n(n+1)\), forgetting to halve, and 14 matches no step of the sum.

Discuss in Forum

Given a group of \(n\) married women and their \(n\) husbands at least how many people be chosen from this group of \(2n\) people to guarantee the set contains a married couple ?

A.\(n - 1\)
B.\(n\)
C.\(n + 1\)
D.\(n + 2\)

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

At least \(n + 1\) people must be chosen.

Think of the \(n\) couples as \(n\) pigeonholes. With \(n + 1\) people chosen, two of them must belong to the same couple, by the pigeonhole principle, so a married couple is guaranteed.

With only \(n\) people this can fail: choose all \(n\) wives (or one person from each couple) and no couple appears. So \(n\), and certainly \(n - 1\), are not enough, and \(n + 2\) is more than necessary.

Discuss in Forum

The number of positive integers, not greater than 100 which are not divisible by 2, 3 or 5, is :

A.20
B.25
C.26
D.30

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: C

There are 26 such integers.

Count the numbers up to 100 divisible by 2, 3 or 5 using inclusion-exclusion:

\[ \begin{aligned} &50 + 33 + 20 \\ &- (16 + 10 + 6) + 3 = 74 \end{aligned} \]

(multiples of 2, 3, 5; then of 6, 10, 15; then of 30). So \(100 - 74 = 26\) numbers are divisible by none of them.

Check by Euler-type reasoning: in each block of 30 there are \(30(1/2)(2/3)(4/5) = 8\) such numbers, giving 24 up to 90, plus 91 and 97 between 91 and 100, a total of 26.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Combinatorics and Counting Questions and Answers || Combinatorics and Counting MCQ Questions and Answers || Combinatorics and Counting GK Questions and Answers || Combinatorics and Counting GK MCQ Questions || Combinatorics and Counting Multiple Choice Questions and Answers || Combinatorics and Counting GK || GK on Combinatorics and Counting || Discrete Mathematics Questions and Answers || Discrete Mathematics MCQ Questions and Answers || Discrete Mathematics GK Questions and Answers || GK on Discrete Mathematics

Combinatorics and Counting Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications