Combinatorics and Counting Questions and Answers

Q: Let us consider the letters from a through h, and all 5 letters are made using these letters. (words are just strings of letters). How many of these words contain no repeated letters ?

The number of five-letter words with no repeated letter is 6720.There are 8 letters, a to h. With no repetition, the first position has 8 choices, the next 7, then 6, 5 and 4: these are permutations of 8 objects taken 5 at a time.\[ P(8, 5) = 8 \times 7 \times 6 \times 5 \times 4 = 6720 \]6072, 7260 and 7630 are rearrangements of the digits of the right answer, a common trap. Allowing repetition would give \(8^{5} = 32768\), which is not offered.

11.

Let us consider the letters from a through h, and all 5 letters are made using these letters. (words are just strings of letters). How many of these words contain no repeated letters ?

A.6720
B.6072
C.7260
D.7630

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: A

The number of five-letter words with no repeated letter is 6720.

There are 8 letters, a to h. With no repetition, the first position has 8 choices, the next 7, then 6, 5 and 4: these are permutations of 8 objects taken 5 at a time.

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

6072, 7260 and 7630 are rearrangements of the digits of the right answer, a common trap. Allowing repetition would give \(8^{5} = 32768\), which is not offered.

Discuss in Forum

12.

The number of bit strings of length eight that will either start with a 1 bit or end with two bits 00 shall be

A.32
B.64
C.128
D.160

Exam Year(s)

UGC NET - 2012,

Answer: D

Count the strings starting with 1: the first bit is fixed and the other seven are free, so there are 2^7 = 128. Strings ending with 00: the last two bits are fixed and six are free, so 2^6 = 64. Strings that do both (start with 1 and end with 00) have 5 free bits, so 2^5 = 32.

\[ 128 + 64 - 32 = 160 \]

By inclusion and exclusion, the number of strings is 160. The value 32 counts only the strings that do both, 64 is only those ending in 00, and 128 is only those starting with 1, so each of them leaves something out.

Discuss in Forum

13.

Suppose that someone starts with a chain letter. Each person who receives the letter is asked to send it on to 4 other people. Some people do this, while some do not send any letter. How many people have seen the letter, including the first person, if no one receives more than one letter and if the chain letter ends after there have been 100 people who read it but did not send it out ? Also find how many people sent out the letter ?

A.122 & 22
B.111 & 11
C.133 & 33
D.144 & 44

Exam Year(s)

UGC NET - 2012,

Answer: C

Let s be the number of people who sent the letter. Each of them sent it to 4 others, so the number of people who received it is 4s. Counting the first person, the total who have seen the letter is 1 + 4s. Also, those who have seen it consist of the s senders and the 100 who did not send it.

\[ 1 + 4s = s + 100 \Rightarrow 3s = 99 \Rightarrow s = 33 \]

So 33 people sent out the letter and 1 + 4(33) = 133 people saw it. The other pairs, 122 and 22, 111 and 11, and 144 and 44, do not satisfy 1 + 4s = s + 100.

Discuss in Forum

14.

The no. of ways to distribute n distinguishable objects into k distinguishable boxes, so that \(n_i\) objects are placed into box i, i = 1, 2, …. k equals which of the following ?

A.\(\frac{n!}{n_1! + n_2! + \cdots + n_k!}\)
B.\(\frac{n_1! + n_2! + \cdots + n_k!}{n_1!\, n_2!\, n_3! \cdots n_k!}\)
C.\(\frac{n!}{n_1!\, n_2!\, n_3! \cdots n_k!}\)
D.\(\frac{n_1!\, n_2! \cdots n_k!}{n_1! - n_2! - n_3! \cdots - n_k!}\)

Exam Year(s)

UGC NET - 2012,

Answer: C

The number of ways to distribute n distinguishable objects into k distinguishable boxes so that box i gets \(n_i\) objects is the multinomial coefficient

\[ \frac{n!}{n_1!\, n_2! \cdots n_k!} \]

The reasoning is that the n objects can be arranged in n! orders, and the order inside each box does not matter, so the count is divided by \(n_i!\) for each box. The options with sums of factorials in the numerator or denominator have no such combinatorial meaning. The keyed answer is the third option.

Discuss in Forum

15.

How many solutions do the following equation have

\(x_1 + x_2 + x_3 = 11\)

where \(x_1 \ge 1, x_2 \ge 2, x_3 \ge 3\)

A.\(C(7, 11)\)
B.\(C(11, 3)\)
C.\(C(14, 11)\)
D.\(C(7, 5)\)

Exam Year(s)

UGC NET - 2012,

Answer: D

To count the solutions of \(x_1 + x_2 + x_3 = 11\) with \(x_1 \ge 1\), \(x_2 \ge 2\) and \(x_3 \ge 3\), substitute \(y_1 = x_1 - 1\), \(y_2 = x_2 - 2\) and \(y_3 = x_3 - 3\), which are non-negative. Then

\[ y_1 + y_2 + y_3 = 11 - 6 = 5 \]

The number of non-negative solutions of this equation in 3 variables is

\[ C(5 + 3 - 1, 5) = C(7, 5) = 21 \]

The option C(11, 3) = 165 and C(14, 11) = 364 are too large, and C(7, 11) has no meaning. The keyed answer is C(7, 5).

Discuss in Forum

16.

The number of distinct bracelets of five beads made up of red, blue, and green beads (two bracelets are indistinguishable if the rotation of one yield another) is,

A.243
B.81
C.51
D.47

Exam Year(s)

UGC NET - 2012,

Answer: C

Counting bracelets of five beads in three colours, where two are the same if one is a rotation of the other, is counting necklaces under the cyclic group of order 5, by Burnside's lemma. The identity fixes all \(3^5 = 243\) colourings, and each of the four non-trivial rotations fixes only the 3 single colour ones, because 5 is prime. So

\[ \frac{3^5 + 4 \times 3}{5} \]\[ = \frac{243 + 12}{5} = 51 \]

The keyed answer is 51. The number 243 counts all colourings, 81 is \(3^4\) and 47 does not come from the formula.

Discuss in Forum

17.

Consider the following pseudocode segment :

K := 0
for i₁ := 1 to n
  for i₂ := 1 to i₁
    :
    :
    :
      for i_m := 1 to i_m-1
        K := K + 1

The value of K after the execution of this code shall be

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

Exam Year(s)

UGC NET - 2012,

Answer: A

The loops are nested m deep, with n at least i1, i1 at least i2, and so on down to im, which is at least 1, and K is increased once for each such sequence. So K counts the non-increasing sequences of m values chosen from 1 to n, that is, the combinations of m items from n with repetition allowed, which is \(C(n + m - 1, m)\). A check with m = 1 gives K = n, which is \(C(n, 1)\), and m = 2 gives n(n+1)/2, which is \(C(n + 1, 2)\). Option (B) would count combinations without repetition, and options (C) and (D) choose n items instead of m, so they are wrong. The answer is option (A).

Discuss in Forum

18.

Number of binary trees formed with 5 nodes are

A.32
B.36
C.120
D.42

Exam Year(s)

UGC NET - 2012,

Answer: D

The number of different binary trees that can be formed with n nodes is the Catalan number, the binomial coefficient of 2n over n divided by n + 1. For n = 5 this is

\[ \frac{1}{6}\binom{10}{5} = \frac{252}{6} = 42 \]

So there are 42 binary trees with 5 nodes, option (D). The values 32 and 120 are 2 to the power 5 and 5 factorial, which do not count binary tree shapes, and 36 is not the Catalan number.

Discuss in Forum

19.

If n and r are non-negative integers and \(n \ge r\), then \(p(n + 1, r)\) equals to

A.\(\frac{p(n, r)(n + 1)}{(n + 1 - r)}\)
B.\(\frac{p(n, r)(n + 1)}{(n - 1 + r)}\)
C.\(\frac{p(n, r)(n - 1)}{(n + 1 - r)}\)
D.\(\frac{p(n, r)(n + 1)}{(n + 1 + r)}\)

Exam Year(s)

UGC NET - 2013,

Answer: A

The number of permutations is p(n, r) = n! / (n - r)!. For n + 1 objects it is p(n + 1, r) = (n + 1)! / (n + 1 - r)!. Writing (n + 1)! = (n + 1) n! and (n + 1 - r)! = (n + 1 - r)(n - r)! gives the result.

\[ p(n+1, r) = \frac{(n+1)\, n!}{(n+1-r)(n-r)!} \]\[ = \frac{p(n, r)(n+1)}{n+1-r} \]

So the first option is right. The other options change the sign of 1 or r in the denominator or the factor n + 1 in the numerator, which does not agree with the derivation.

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