Combinatorics · Discrete Mathematics · GATE CSE

The number of arrangements of six identical balls in three identical bins is ___________.

The number of $$4$$ digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the se...

The recurrence relation capturing the optional execution time of the Towers of Hanoi problem with $$n$$ discs is

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 student have taken ...

Let $$A$$ be a sequence of $$8$$ distinct integers sorted in ascending order. How many distinct pairs of sequence, $$B$$ and $$C$$ are there such that...

$$n$$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied...

$$m$$ identical balls are to be placed in $$n$$ distinct bags. You are given that $$m \ge kn$$, where $$k$$ is a natural number $$ \ge 1$$. In how man...

The minimum number of colors required to color the vertices of a cycle with $$n$$ nodes in such a way that no two adjacent nodes have the same colour...

The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from same suit is

The solution to the recurrence equation $$T\left( {{2^k}} \right)$$ $$ = 3T\left( {{2^{k - 1}}} \right) + 1$$, $$T\left( 1 \right) = 1$$ is:...

The number of binary strings of $$n$$ zeros and $$k$$ ones such that no two ones are adjacent is:

There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: - Th...

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ...

The coefficient of $${x^{12}}$$ in $${\left( {{x^3} + {x^4} + {x^5} + {x^6} + ...} \right)^3}\,\,\,\,\,\,$$ is _____________.

There are 5 bags labeled 1 to 5. All the coins in given bag have the same weight. Some bags have coins of weight 10 gm, other have coins of weight 11 ...

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-p...

The number of distinct positive integral factors of 2014 is _______ .

Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contain no consecutive $$0s$$. The value of $${x_5}$$ is

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...

The exponent of $$11$$ in the prime factorization of $$300!$$ is

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

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 \ri...

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...

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...

Consider the polynomial $$P\left( x \right) = {a_0} + {a_1}x + {a_2}{x^2} + {a_3}{x^3},$$ where $${a_i} \ne 0,\forall i$$. The minimum number of mult...

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 correspon...

What is the cardinality of the set of integers $$X$$ defined below? $$X = $$ {$$n\left| {1 \le n \le 123,\,\,\,\,\,n} \right.$$ is not divisible by ...

What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs $$(a, b)$$ and $$(c, d)...

Let $$G\left( x \right) = 1/\left( {1 - x} \right)2 = \sum\limits_{i = 0}^\infty {g\left( i \right)\,{x^1}} \,\,\,,$$ where $$\left| x \right| < ...

Let $$n = {p^2}q,$$ where $$p$$ and $$q$$ are distinct prime numbers. How many numbers $$m$$ satisfy $$1 \le m \le n$$ and $$gcd\left( {m.n} \right) =...

Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of $$k$$ colours, such ...

In how many ways can we distribute 5 distinct balls, $${B_1},{B_2},......,{B_5}$$ in 5 distinct cells, $${C_1},{C_2},.....,{C_5}$$ such that Ball $${B...

The recurrence equation $$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$ $$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \right) + n,\,n \ge 2$$ evaluate...

How many 4 digit even numbers have all 4 digits distinct?

Two girls have picked 10 roses, 15 sunflowers and 14 daffodils. What is the number of ways they can divide the flowers among themselves?

In a room containing 28 people, there are 18 people who speak English, 15 people who speak Hindi and 22 people who speak Kannada, 9 persons speak both...

Solve the following recurrence relation $$\,\,\,\,\,\,\,{x_n} = 2{x_{n - 1}} - 1\,\,n > 1$$ $$\,\,\,\,\,\,\,{x_1} = 2$$

The recurrence relation $$\,\,\,\,\,$$ $$T\left( 1 \right) = 2$$ $$T\left( n \right) = 3T\left( {{n \over 4}} \right) + n$$ has the solution $$T(n...

The number of substrings (of all length inclusive) that can be formed from a character string of length $$n$$ is

How many sub strings can be formed from a character string of length $$n$$?

Solve the recurrence equations: $$\,\,\,\,\,\,\,\,\,\,T\left( n \right) = \left( {{n \over 2}} \right) + 1$$ $$\,\,\,\,\,\,\,\,\,\,\,T\left( 1 \right...

(a) Solve the recurrence equations $$\,\,\,\,\,\,\,\,\,T\left( n \right) = T\left( {n - 1} \right) + n$$ $$\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1T$$...