Combinatorics

Which one of the following options is correct for the given data in the table? Iteration ($i$) 0 1 2 3 Input ($I$) 20 $-$4 10 15 Output ($X$) 20 16 26 41 Output ($Y$) 20 $-$80 $-$800 $-$12000

A shop has 4 distinct flavors of ice-cream. One can purchase any number of scoops of any flavor. The order in which the scoops are purchased is inconsequential. If one wants to purchase 3 scoops of ice-cream, in how many...

Let $S$ be the set of all ternary strings defined over the alphabet $\{a, b, c\}$. Consider all strings in $S$ that contain at least one occurrence of two consecutive symbols, that is, "aa", "bb" or "cc". The number of s...

In the sequence 6, 9, 14, $x$, 30, 41, a possible value of $x$ is

Let $T(n)$ be the recurrence relation defined as follows: $T(0) = 1$ $T(1) = 2$, and $T(n) = 5T(n - 1) - 6T(n - 2)$ for $n \geq 2$ Which one of the following statements is TRUE?

A rectangular paper of 20 cm × 8 cm is folded 3 times. Each fold is made along the line of symmetry, which is perpendicular to its long edge. The perimeter of the final folded sheet (in cm) is

Two wizards try to create a spell using all the four elements, water, air, fire, and earth . For this, they decide to mix all these elements in all possible orders. They also decide to work independently. After trying al...

The Lucas sequence $$L_n$$ is defined by the recurrence relation: $${L_n} = {L_{n - 1}} + {L_{n - 2}}$$, for $$n \ge 3$$, with $${L_1} = 1$$ and $${L_2} = 3$$. Which one of the options given is TRUE?

Let $$U = \{ 1,2,....,n\} $$, where n is a large positive integer greater than 1000. Let k be a positive integer less than n. Let A, B be subsets of U with $$|A| = |B| = k$$ and $$A \cap B = \phi $$. We say that a permut...

A series of natural numbers $$F_1,F_2,F_3,F_4,F_5,F_6,F_7,\,.....$$ obeys $$F_{n+1}=F_n+F_{n-1}$$ for all integers $$n\ge2$$. If $$F_6=37$$, and $$F_7=60$$, then what is $$F_1$$ ?

Which one of the following is the closed form for the generating function of the sequence (a n } n $$\ge$$ 0 defined below? $${a_n} = \left\{ {\matrix{ {n + 1,} & {n\,is\,odd} \cr {1,} & {otherwise} \cr } } \right.$$

The number of arrangements of six identical balls in three identical bins 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: - The fastest computer gets the toughest job and the slowest computer gets...

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

Let U = {1, 2 ,..., n}. Let A = {(x, X) | x ∈ X, X ⊆ U}. Consider the following two statements on |A|. I. |A| = n2 n–1 II. |A| = $$\sum\limits_{k = 1}^n {k\left( {\matrix{ n \cr k \cr } } \right)} $$ Which of the above s...

Which one of the following is a closed form expression for the generating function of the sequence $$\left\{ {{a_n}} \right\},$$ where $${a_n} = 2n + 3$$ for all $$n = 0,1,2,....?$$

Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislikes the colour white. Gulab and Neel like a...

Let $${a_n}$$ be the number of $$n$$-bit strings that do NOT contain two consecutive $$1s.$$ Which one of the following is the recurrence relation for $${a_n}$$?

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

Consider the recurrence relation $${a_1} = 8,\,{a_n} = 6{n^2} + 2n + {a_{n - 1}}.$$ Let $${a_{99}} = K \times {10^4}.$$ The value of $$K$$ is ____________.

A cube is built using $$64$$ cubic blocks of side one unit. After it is built, one cubic block is removed from every corner of the cube. The resulting surface area of the body (in square units) after the removal is _____...

$$\sum\limits_{x = 1}^{99} {{1 \over {x\left( {x + 1} \right)}}} $$ = _____________.

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 set $${1, 2, 3}$$ is____________.

Let $${a_n}$$ represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for $${a_n}$$?

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

Let $$G$$ be a complete undirected graph on $$6$$ vertices. If vertices of $$G$$ $$\,\,\,\,$$ are labeled, then the number of distinct cycles of length $$4$$ in $$G$$ is equal to

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

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

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

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?

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)$$ Suppose...

Given a set of elements N = {1, 2, ....., n} and two arbitrary subsets $$A\, \subseteq \,N\,$$ and $$B\, \subseteq \,N\,$$, how many of the n! permutations $$\pi $$ from N to N satisfy $$\min \,\left( {\pi \,\left( A \ri...

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 either $$2, 3$$ or $$5$$ }

The following function computes the value of m C n correctly for all legal values m and n (m≥1,n≥0 and m>n) int func(int m, int n) { if (E) return 1; else return(func(m -1, n) + func(m - 1, n - 1)); } In the above functi...

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| < 1$$ What is $$g(i)$$?

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)$$ in the chosen set such that $$a \equiv c$$ mod $$3$$ and $$b \equiv d...

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 student have taken Computer Organization coures; 50 students have taken both Programming...

How many graphs on $$n$$ labeled vertices exist which have at least $$\left( {{n^2} - 3n} \right)/2\,\,\,$$ edges?

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_i}$$ is not in cell $${C_i}$$, $$\forall i = 1,2,....,5$$ and each ce...

The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (Note: power ($$2,$$ $$x$$) is same as $${2^x}$$)

The number of different $$n \times n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is

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

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 that the colour-pairs used to colour any two letters are different. Bo...

In an M$$ \times $$N matrix such that all non-zero entries are covered in $$a$$ rows and $$b$$ columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is

$$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 many ways can the balls be placed in the bags if each bag must contain at...

$$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 by her husband. The number of different gatherings possible at the par...

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 i) Each is sorted in ascending order. ii) $$B$$ has $$5$$ and $$C$$ h...

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

A multiset is an unordered collection of elements where elements may repeat ay number of times. The size of a multiset is the number of elements in it counting repetitions. (a) what is the number of multisets of size 4 t...

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

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

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

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 English and Hindi, 11 persons speak both Hindi and Kannada where as 1...

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

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$$?

What is the generating function G (z) for the sequence of Fibonacci numbers?

(a) How many binary relations are there on a set A with n elements? (b) How many one - to - one functions are there from a set A with n elements onto itself

(a) Solve the recurrence equations $$\,\,\,\,\,\,\,\,\,T\left( n \right) = T\left( {n - 1} \right) + n$$ $$\,\,\,\,\,\,\,\,\,T\left( 1 \right) = 1T$$ (b) What is the generating function? $$\,\,\,\,\,\,\,\,\,G\left( z \ri...