GATE CSE 2014 Set 1 | Combinatorics Question 9 | Discrete Mathematics

GATE CSE 2014 Set 1

Numerical

-0

A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)} and the set of all 3-pennants is {(2,1),(1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10-pennants is _________.

Your input ____

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 2008

MCQ (Single Correct Answer)

-0.6

When $$n = {2^{2k}}$$ for some $$k \ge 0$$, the recurrence relation $$$T\left( n \right) = \sqrt 2 T\left( {n/2} \right) + \sqrt n ,\,\,T\left( 1 \right) = 1$$$
evaluates to

$$\sqrt n \left( {\log \,n + 1} \right)$$

$$\sqrt n \,\log \,n$$

$$\sqrt n \,\log \,\sqrt n $$

$$n\,\log \sqrt n $$

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

In how many ways can $$b$$ blue balls and $$r$$ red balls be distributed in $$n$$ distinct boxes?

$${{\left( {n + b - 1} \right)!\left( {n + r - 1} \right)!} \over {\left( {n - 1} \right)!b!\left( {n - 1} \right)!r!}}$$

$${{\left( {n + \left( {b + r} \right) - 1} \right)!} \over {\left( {n - 1} \right)!\left( {n - 1} \right)!\left( {b + r} \right)!}}$$

$${{n!} \over {b!r!}}$$

$${{\left( {n + \left( {b + r} \right) - 1} \right)!} \over {n!\left( {b + r - 1} \right)!}}$$