# Recent questions and answers in Combinatory

1
Find the characteristic roots of the linear homogeneous recurrence relation $a_{n} = 2a_{n-1} - 2a_{n-2}.$ [Note: These are complex numbers.] Find the solution of the recurrence relation in part $(A)$ with $a_{0} = 1\:\text{and}\: a_{1} = 2.$
2
Give a big-O estimate for the function $f$ in question $12$ if $f$ is an increasing function.
3
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 \mod 5$ $4$ $6$ $16$ $24$
4
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 $3$ $8$ $9$ $12$
5
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$
6
$m$ identical balls are to be placed in $n$ distinct bags. You are given that $m \geq kn$, where $k$ is a natural number $\geq 1$. In how many ways can the balls be placed in the bags if each bag must contain at least $k$ ... $\left( \begin{array}{c} m - kn + n + k - 2 \\ n - k \end{array} \right)$
7
In how many ways can a given positive integer $n \geq 2$ be expressed as the sum of $2$ positive integers (which are not necessarily distinct). For example, for $n=3$, the number of ways is $2$, i.e., $1+2, 2+1$. Give only the answer ... positive integer $n \geq k$ be expressed as the sum of $k$ positive integers (which are not necessarily distinct). Give only the answer without explanation.
8
A $1 \times 1$ chessboard has one square, a $2 \times 2$ chessboard has five squares. Continuing along this fashion, what is the number of squares on the regular $8 \times 8$ chessboard? $64$ $65$ $204$ $144$ $256$
9
Find the recurrence relation satisfied by $R_{n},$ where $R_{n}$ is the number of regions that a plane is divided into by $n$ lines, if no two of the lines are parallel and no three of the lines go through the same point. Find $R_{n}$ using iteration.
1 vote
10
Find a recurrence relation for the number of bit strings of length $n$ that contain the string $01.$ I am getting a recurrence like An = 2^(n-2) + 2A(n-1) - A (N-2) .Answer is not given for this question.Please help and explain your steps.
11
Solve the simultaneous recurrence relations $a_{n} = 3a_{n-1} + 2b_{n-1}$ $b_{n} = a_{n-1} + 2b_{n-1}$ with $a_{0} = 1 \: \text{and}\: b_{0} = 2.$
12
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?
13
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$
14
In how many ways can $b$ blue balls and $r$ red balls be distributed in $n$ distinct boxes? $\frac{(n+b-1)!\,(n+r-1)!}{(n-1)!\,b!\,(n-1)!\,r!}$ $\frac{(n+(b+r)-1)!}{(n-1)!\,(n-1)!\,(b+r)!}$ $\frac{n!}{b!\,r!}$ $\frac{(n + (b + r) - 1)!} {n!\,(b + r - 1)}$
15
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)$. How many distinct paths are there for the robot to reach the point $(10,10)$ starting from the initial position $(0,0)$? $^{20}\mathrm{C}_{10}$ $2^{20}$ $2^{10}$ None of the above
16
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$
17
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
18
What is the remainder when $4444^{4444}$ is divided by $9?$ $1$ $2$ $5$ $7$ $8$
19
The value of the expression $13^{99}\pmod{17}$ in the range $0$ to $16$, is ________.
20
The value of $3^{51} \text{ mod } 5$ is _____
21
Provide short answers to the following questions: 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.
22
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.
23
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
24
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
25
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.
1 vote
26
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
27
Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.
28
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
29
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)$
30
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)$
31
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)$
32
How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example $5?$
33
Determine a value for the constant C in Example $4$ and use it to estimate the number of bit operations needed to multiply two $64$-bit integers using the fast multiplication algorithm.
34
Express the fast multiplication algorithm in pseudocode.
35
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.
36
How many comparisons are needed to locate the maximum and minimum elements in a sequence with $128$ elements using the algorithm in Example $2$?
37
How many comparisons are needed for a binary search in a set of $64$ elements?
1 vote
Prove Theorem $6:$Suppose that $\{a_{n}\}$ satisfies the liner nonhomogeneous recurrence relation $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k} + F(n),$ where $c_{1}.c_{2},\dots,c_{k}$ ... is $m,$ there is a particular solution of the form $n^{m}(p_{t}n^{t} + p_{t-1}n^{t-1} + \dots + p_{1}n + p_{0})s^{n}.$
Prove Theorem $4:$ Let $c_{1},c_{2},\dots,c_{k}$ be real numbers. Suppose that the characteristic equation $r^{k}-c_{1}r^{k-1}-\dots c_{k} = 0$ has $t$ distinct roots $r_{1},r_{2},\dots,r_{t}$ with multiplicities $m_{1},m_{2},\dots,m_{t},$ ... $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$
Solve the recurrence relation $T (n) = nT^{2}(n/2)$ with initial condition $T (1) = 6$ when $n = 2^{k}$ for some integer $k.$ [Hint: Let $n = 2^{k}$ and then make the substitution $a_{k} = \log T (2^{k})$ to obtain a linear nonhomogeneous recurrence relation.]