GATE CSE 2008 | Combinatorics Question 17 | Discrete Mathematics

PREVIOUS NEXT

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contains no consecutive $$0s$$.

Which of the following recurrences does $${x_n}$$ satisfy?

$${x_n} = 2{x_{n - 1}}$$

$${x_n} = {x_{\left[ {n/2} \right]}} + 1$$

$${x_n} = {x_{\left[ {n/2} \right]}} + n$$

$${x_n} = {x_{n - 1}} + {x_{n - 2}}$$

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $$(i, j)$$ then it can move to either $$(i+1, j)$$ or $$(i, j+1)$$

How many distinct path are there for the robot to reach the point $$(10, 10)$$ starting from the initial position $$(0, 0)$$?

$$\left( {\matrix{ {20} \cr {10} \cr } } \right)$$

$${2^{20}}$$

$${2^{10}}$$

None of the above

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Suppose that the robot is not allowed to traverse the line segment from $$(4, 4)$$ to $$(5,4)$$. With this constraint, how many distinct path are there for the robot to reach $$(10, 10)$$ starting from $$(0,0)$$?

$${2^{9}}$$

$${2^{19}}$$

$$\left( {\matrix{ 8 \cr 4 \cr } } \right) \times \left( {\matrix{ {11} \cr 5 \cr } } \right)$$

$$\left( {\matrix{ {20} \cr {10} \cr } } \right) - \left( {\matrix{ 8 \cr 4 \cr } } \right) \times \left( {\matrix{ {11} \cr 5 \cr } } \right)$$

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

For each elements in a set of size $$2n$$, an unbiased coin in tossed. The $$2n$$ coin tosses are independent. An element is chhoosen if the corresponding coin toss were head.The probability that exactly $$n$$ elements are chosen is

$${{\left( {\matrix{ {2n} \cr n \cr } } \right)} \over {{4^n}}}$$

$${{\left( {\matrix{ {2n} \cr n \cr } } \right)} \over {{2^n}}}$$

$${1 \over {\left( {\matrix{ {2n} \cr n \cr } } \right)}}$$

$${1 \over 2}$$

PREVIOUS NEXT