combinatorics

Consider a relational database schema with a relation $R(A, B, C, D)$. If $\{A, B\}$ and $\{A, C\}$ are the only two candidate keys of the relation $R$, then the number of superkey...

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

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

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

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

When six unbiased dice are rolled simultaneously, the probability of getting all distinct numbers (i.e., 1, 2, 3, 4, 5, and 6) is

A functional dependency $F: X \to Y$ is termed as a useful functional dependency if and only if it satisfies all the following three conditions: $X$ is not the empty set. $Y$ is no...

Let $$U = \{ 1,2,3\} $$. Let 2$$^U$$ denote the powerset of U. Consider an undirected graph G whose vertex set is 2$$^U$$. For any $$A,B \in {2^U},(A,B)$$ is an edge in G if and on...

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

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

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

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

The number of possible min-heaps containing each value from $$\left\{ {1,2,3,4,5,6,7} \right\}$$ exactly once is _____.

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 number of ways in which the numbers $$1, 2, 3, 4, 5, 6, 7$$ can be inserted in an empty binary search tree, such that the resulting tree has height $$6,$$ is _____________. $$N...

The coefficient of $${x^{12}}$$ in $${\left( {{x^3} + {x^4} + {x^5} + {x^6} + ...} \right)^3}\,\,\,\,\,\,$$ 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 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}$$?

The maximum number of superkeys for the relation schema $$R(E, F, G, H)$$ with $$E$$ as key is ______.

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

The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is _______________

Suppose n and p are unsigned int variables in a C program. We wish to set p to $${}^n{C_3}$$. If n is large, which one of the following statements is most likely to set p correctly...

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?

What is the probability that in a randomly choosen group of r people at least three people have the same birthday?

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

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

What is the maximum number of different Boolean functions involving $$n$$ Boolean variables?

When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many d...

The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets...

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

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

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}$$)

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

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

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

If a fair coin is tossed four times, what is the probability that two heads and two tails will result?

Two n bit binary stings, S1 and, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where th...

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

How many perfect matchings are there in a complete graph of 6 vertices?

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

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

Let $$A$$ be a set of $$n\left( { > 0} \right)$$ elements. Let $${N_r}$$ be the number of binary relations on $$A$$ and Let $${N_r}$$ be the number of functions from $$A$$ to $$A$$...

how many undirected graphs (not necessarily connected) can be constructed out of a given $$\,\,\,\,V = \left\{ {{v_1},\,\,{v_2},\,....,\,\,{v_n}} \right\}$$ of $$n$$ vertices?

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = { v 1 ,v 2 ,........,v n } of n vertices?

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

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 number of binary strings of $$n$$ zeros and $$k$$ ones such that no two ones are adjacent 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?

How many substrings (of all lengths inclusive ) can be formed from a character string of length $$n$$? Assume all characters to be distinct. Prove your answer.