GATE CS 2008 Q24 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Let $\text{S}$ be the set of all ternary strings defined over the alphabet $\{a, b, c\}$. Consider all strings in $\text{S}$ that contain at least one occurrence of two consecutive symbols, that is, $\text{"aa"}$, $\text{"bb"}$ or $\text{"cc"}$. The number of such strings of length $5$ that are possible is __________. (Answer in integer).

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

Let $U=\{1,2, \ldots, 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=\emptyset$. We say that a permutation of $U$ separates $A$ from $B$ if one of the following is true. All members of $A$ appear in the …

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 \geq 0}$ defined below? $$a_{n} = \left\{\begin{matrix} n + 1, & \text{n is odd} & \\ 1, & \text{otherwise} & \end{matrix}\right.$$

Consider the following recurrence: $$\begin{array}{} f(1) & = & 1; \\ f(2n) & = & 2f(n) – 1, & \; \text{for}\; n \geq 1; \\ f(2n+1) & = & 2f(n) + 1, & \; \text{for}\; n \geq 1. \end{array}$$ Then, which of the following statements is/are $\text{TRUE}?$