GATE CS Combinatorics: Counting, Recurrence Relations, Generating Functions questions

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

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 easiest job. Every computer gets at least one job. The number of ways in which this can be done is ___________.

Let $S$ be a set consisting of $10$ elements. The number of tuples of the form $(A,B)$ such that $A$ and $B$ are subsets of $S$, and $A \subseteq B$ is ___________

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, \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?

The value of $3^{51} \text{ mod } 5$ is _____

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

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

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

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

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

The value of the expression $13^{99}\pmod{17}$ in the range $0$ to $16$, is ________.

$\sum\limits_{x=1}^{99}\frac{1}{x(x+1)}$ = ______.

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

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-$pennants is ${(2), (1,1)}$ and the set of all $3-$pennants is ${(2,1), (1,1,1), (1,2)}$. …