# Recent questions and answers in Combinatory 1
Find the least number of cables required to connect eight computers to four printers to guarantee that for every choice of four of the eight computers, these four computers can directly access four different printers. Justify your answer.
2
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 ______.
3
Let $P =\sum_{\substack{1\le i \le 2k \\ i\;odd}} i$ and $Q = \sum_{\substack{1 \le i \le 2k \\ i\;even}} i$, where $k$ is a positive integer. Then $P = Q - k$ $P = Q + k$ $P = Q$ $P = Q + 2k$
4
How many $4$-digit even numbers have all $4$ digits distinct $2240$ $2296$ $2620$ $4536$
5
Suppose that a basketball league has $32$ teams, split into two conferences of $16$ teams each. Each conference is split into three divisions. Suppose that the North Central Division has five teams. Each of the teams in the North Central Division plays four games ... the other conference. In how many different orders can the games of one of the teams in the North Central Division be scheduled?
6
Suppose that a weapons inspector must inspect each of five different sites twice, visiting one site per day. The inspector is free to select the order in which to visit these sites, but cannot visit site $\text{X},$ the most suspicious site, on two consecutive days. In how many different orders can the inspector visit these sites?
7
How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books? $4$ $6$ $7$ $9$
8
Given a standard deck of cards, there $52!$ are different permutations of the cards. Given two identical standard decks of cards, how many different permutations are there?
9
Let $a_n$ be the number of $n$-bit strings that do NOT contain two consecutive $1's$. Which one of the following is the recurrence relation for $a_n$? $a_n = a_{n-1}+ 2a_{n-2}$ $a_n = a_{n-1}+ a_{n-2}$ $a_n = 2a_{n-1}+ a_{n-2}$ $a_n = 2a_{n-1}+ 2a_{n-2}$
1 vote
10
Let $A$ be a set of $n$ elements. The number of ways, we can choose an ordered pair $(B,C)$, where $B,C$ are disjoint subsets of $A$, equals $n^2$ $n^3$ $2^n$ $3^n$
11
What is the minimum number of students needed in a class to guarantee that there are at least $6$ students whose birthdays fall in the same month ? $6$ $23$ $61$ $72$ $91$
12
Let $U = \{1, 2, \dots , n\}$ Let $A=\{(x, X) \mid x \in X, X \subseteq U \}$. Consider the following two statements on $\mid A \mid$. $\mid A \mid = n2^{n-1}$ $\mid A \mid = \Sigma_{k=1}^{n} k \begin{pmatrix} n \\ k \end{pmatrix}$ Which of the above statements is/are TRUE? Only I Only II Both I and II Neither I nor II
13
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 ________.
14
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-$ ... $(1,2)$ is not the same as the pennant $(2,1)$. The number of $10-$pennants is________
15
What is the remainder when $4444^{4444}$ is divided by $9?$ $1$ $2$ $5$ $7$ $8$
16
The coefficient of $x^{3}$ in the expansion of $(1 + x)^{3} (2 + x^{2})^{10}$ is. $2^{14}$ $31$ $\left ( \frac{3}{3} \right ) + \left ( \frac{10}{1} \right )$ $\left ( \frac{3}{3} \right ) + 2\left ( \frac{10}{1} \right )$ $\left ( \frac{3}{3} \right ) \left ( \frac{10}{1} \right ) 2^{9}$
17
If the ordinary generating function of a sequence $\left \{a_n\right \}_{n=0}^\infty$ is $\large \frac{1+z}{(1-z)^3}$, then $a_3-a_0$ is equal to ___________ .
18
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
19
Let $G(x) = \frac{1}{(1-x)^2} = \sum\limits_{i=0}^\infty g(i)x^i$, where $|x| < 1$. What is $g(i)$? $i$ $i+1$ $2i$ $2^i$
20
It is required to divide the $2n$ members of a club into $n$ disjoint teams of $2$ members each. The teams are not labelled. The number of ways in which this can be done is: $\frac{\left ( 2n \right )!}{2^{n}}$ $\frac{\left ( 2n \right )!}{n!}$ $\frac{\left ( 2n \right )!}{2^n . n!}$ $\frac{n!}{2}$ None of the above.
21
In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,\ldots 5$ and each cell contains exactly one ball? $44$ $96$ $120$ $3125$
22
There are four bus lines between $A$ and $B$; and three bus lines between $B$ and $C$. The number of way a person roundtrip by bus from $A$ to $C$ by way of $B$ will be $12$ $7$ $144$ $264$
23
Mala has the 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. Both prints of a letter can also be coloured with the same colour. What is the minimum value of $k$ that satisfies this requirement? $9$ $8$ $7$ $6$
24
A line $L$ in a circuit is said to have a $stuck-at-0$ fault if the line permanently has a logic value $0$. Similarly a line $L$ in a circuit is said to have a $stuck-at-1$ fault if the line permanently has a logic value $1$. A circuit is said to have a multiple $stuck-at$ ... total number of distinct multiple $stuck-at$ faults possible in a circuit with $N$ lines is $3^N$ $3^N - 1$ $2^N - 1$ $2$
25
$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 party is $^{2n}\mathrm{C}_n\times 2^n$ $3^n$ $\frac{(2n)!}{2^n}$ $^{2n}\mathrm{C}_n$
26
Let $A$ be a sequence of $8$ distinct integers sorted in ascending order. How many distinct pairs of sequences, $B$ and $C$ are there such that each is sorted in ascending order, $B$ has $5$ and $C$ has $3$ elements, and the result of merging $B$ and $C$ gives $A$ $2$ $30$ $56$ $256$
27
Two girls have picked $10$ roses, $15$ sunflowers and $15$ daffodils. What is the number of ways they can divide the flowers among themselves? $1638$ $2100$ $2640$ None of the above
28
The number of binary strings of $n$ zeros and $k$ ones in which no two ones are adjacent is $^{n-1}C_k$ $^nC_k$ $^nC_{k+1}$ None of the above
29
15. a) How many cards must be chosen from a standard deck of 52 cards to guarantee that at least two of the four aces are chosen? b) How many cards must be chosen from a standard deck of 52 cards to guarantee that at least two of the four aces and at least ... many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of two different kinds?
30
How many pairs $(x,y)$ such that $x+y <= k$, where x y and k are integers and $x,y>=0, k > 0$. Solve by summation rules. Solve by combinatorial argument.
31
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
32
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
33
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
34
Give a big-O estimate for the function $f$ given below if $f$ is an increasing function. $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
1 vote
35
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
36
Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.
37
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find $f (5)$ $f (125)$ $f (3125)$
Suppose that $f (n) = 2f (n/2) + 3$ when $n$ is an even positive integer, and $f (1) = 5.$ Find $f (2)$ $f (8)$ $f (64)$ $(1024)$
Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find $f (3)$ $f (27)$ $f (729)$