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.

Q: Notation :C(n, r) = n!/(r!*(n-r)!))n! is factorial n.|A| cardinality of set A\(\overline{s}\) is negation of sThe number of ways to place r indistinguishable balls in n(n \(\lt\) r) distinct boxes, with no box left empty, is........... .

The number of ways is C(r - 1, n - 1).Line the r identical balls up in a row. There are \(r - 1\) gaps between them, and dividing the row into n non-empty groups means choosing \(n - 1\) of those gaps for the dividers. Each choice gives one distribution with no box empty, and every such distribution arises once:\[ \binom{r-1}{n-1} \]C(n + r - 1, n - 1) is the stars-and-bars count when boxes may be left empty. C(n + r - 1, r - 1) and C(n - 1, r - 1) swap or misplace the parameters; the last is 0 here, since \(n \lt r\).

Q: Identify the number of distinct string of length 2 of the combinations of blue and yellow beads. The both ends of the strings are not marked due to this they are indistinguishable if interchanging the ends of one will results other. Denote b and y as a blue and yellow beads. Let us consider bb, by, yb and yy are the four different strings of length 2 when equivalence between strings is not taken into the consideration. The number of equivalent classes into which the set s = (bb, by, yb, yy) is divided by equivalent relation induced by the group of permutation \([\{\Pi_1, \Pi_2\}, 0]\) where :\(\Pi_1 = \begin{pmatrix} bb & by & yb & yy \\ bb & by & yb & yy \end{pmatrix}\)\(\Pi_2 = \begin{pmatrix} bb & by & yb & yy \\ bb & yb & by & yy \end{pmatrix}\)

There are 3 equivalence classes.The group has two permutations: the identity \(\Pi_1\), and \(\Pi_2\), which swaps by and yb (reversing the string) and fixes bb and yy. Two strings are equivalent when some permutation in the group maps one to the other.So the classes are {bb}, {by, yb} and {yy}: three distinct strings once the ends are indistinguishable. Burnside's lemma agrees: \(\Pi_1\) fixes 4 strings and \(\Pi_2\) fixes 2, and \((4 + 2)/2 = 3\).Four is the count before the equivalence is applied; 5 and 6 are larger than the set itself.

Q: 11 students plan to have dinner together for multiple days. They will be seated at the round table. Their plan is to ensure that each student sits next to different neighbours at every dinner. How many days can this arrangement be sustained ?

The arrangement can be sustained for 5 days.Model the students as vertices of the complete graph \(K_{11}\); each seating at a round table is a Hamiltonian cycle, and different neighbours each day means the cycles share no edge. Each student has 10 possible neighbours and gains 2 per dinner, so at most 10/2 = 5 dinners are possible.\[ \frac{n - 1}{2} = \frac{11 - 1}{2} = 5 \]For odd n, \(K_n\) does decompose into exactly \((n-1)/2\) edge-disjoint Hamiltonian cycles, so 5 is achieved. Eleven would need 22 neighbours each, and 4 or 7 do not match the bound.

Q: Explore all 5 letter combinations formed using the letters a through h. How many of these words contains no repeats, also do not include the subword "bad" ?

There are 6660 such words.Words of length 5 with no repeated letter from 8 letters:\[ P(8, 5) = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 6720 \]Words containing 'bad': treat 'bad' as one block, then choose 2 more distinct letters from the remaining 5 and arrange the block with them.\[ \begin{aligned} \binom{5}{2} \times 3! &= 10 \times 6 = 60 \\ 6720 - 60 &= 6660 \end{aligned} \]The other figures do not follow from this count: subtracting the 60 forbidden words is the only correction needed, since 'bad' cannot occur twice in five distinct letters.

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

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

The number of ways to place r indistinguishable balls in n(n \(\lt\) r) distinct boxes, with no box left empty, is........... .

A.C(r - 1, n - 1)
B.C(n + r - 1, n - 1)
C.C(n + r - 1, r - 1)
D.C(n - 1, r - 1)

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: A

The number of ways is C(r - 1, n - 1).

Line the r identical balls up in a row. There are \(r - 1\) gaps between them, and dividing the row into n non-empty groups means choosing \(n - 1\) of those gaps for the dividers. Each choice gives one distribution with no box empty, and every such distribution arises once:

\[ \binom{r-1}{n-1} \]

C(n + r - 1, n - 1) is the stars-and-bars count when boxes may be left empty. C(n + r - 1, r - 1) and C(n - 1, r - 1) swap or misplace the parameters; the last is 0 here, since \(n \lt r\).

Discuss in Forum

Identify the number of distinct string of length 2 of the combinations of blue and yellow beads. The both ends of the strings are not marked due to this they are indistinguishable if interchanging the ends of one will results other. Denote b and y as a blue and yellow beads. Let us consider bb, by, yb and yy are the four different strings of length 2 when equivalence between strings is not taken into the consideration. The number of equivalent classes into which the set s = (bb, by, yb, yy) is divided by equivalent relation induced by the group of permutation \([\{\Pi_1, \Pi_2\}, 0]\) where :

\(\Pi_1 = \begin{pmatrix} bb & by & yb & yy \\ bb & by & yb & yy \end{pmatrix}\)

\(\Pi_2 = \begin{pmatrix} bb & by & yb & yy \\ bb & yb & by & yy \end{pmatrix}\)

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: A

There are 3 equivalence classes.

The group has two permutations: the identity \(\Pi_1\), and \(\Pi_2\), which swaps by and yb (reversing the string) and fixes bb and yy. Two strings are equivalent when some permutation in the group maps one to the other.

So the classes are {bb}, {by, yb} and {yy}: three distinct strings once the ends are indistinguishable. Burnside's lemma agrees: \(\Pi_1\) fixes 4 strings and \(\Pi_2\) fixes 2, and \((4 + 2)/2 = 3\).

Four is the count before the equivalence is applied; 5 and 6 are larger than the set itself.

Discuss in Forum

11 students plan to have dinner together for multiple days. They will be seated at the round table. Their plan is to ensure that each student sits next to different neighbours at every dinner. How many days can this arrangement be sustained ?

A.5
B.11
C.4
D.7

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: A

The arrangement can be sustained for 5 days.

Model the students as vertices of the complete graph \(K_{11}\); each seating at a round table is a Hamiltonian cycle, and different neighbours each day means the cycles share no edge. Each student has 10 possible neighbours and gains 2 per dinner, so at most 10/2 = 5 dinners are possible.

\[ \frac{n - 1}{2} = \frac{11 - 1}{2} = 5 \]

For odd n, \(K_n\) does decompose into exactly \((n-1)/2\) edge-disjoint Hamiltonian cycles, so 5 is achieved. Eleven would need 22 neighbours each, and 4 or 7 do not match the bound.

Discuss in Forum

10.

Explore all 5 letter combinations formed using the letters a through h. How many of these words contains no repeats, also do not include the subword "bad" ?

A.6660
B.6667
C.6578
D.6312

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: A

There are 6660 such words.

Words of length 5 with no repeated letter from 8 letters:

\[ P(8, 5) = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 6720 \]

Words containing 'bad': treat 'bad' as one block, then choose 2 more distinct letters from the remaining 5 and arrange the block with them.

\[ \begin{aligned} \binom{5}{2} \times 3! &= 10 \times 6 = 60 \\ 6720 - 60 &= 6660 \end{aligned} \]

The other figures do not follow from this count: subtracting the 60 forbidden words is the only correction needed, since 'bad' cannot occur twice in five distinct letters.

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