For all $n\in\mathbb{N}$, let $a_n$ denote the number of strings of length $n$ over $\{1,2,3,4\}$ such that:

Question

For all $n\in\mathbb{N}$, let $a_n$ denote the number of strings of length $n$ over $\{1,2,3,4\}$ in which all of the even digits appear before the odd digits, and digit 1 appears exactly once.

Compute: $a_4$ and $a_{2015}$

Hey everyone. I've tried thinking about small cases, for example when $n=3$. In that case $a_3=11$. I thought about solving it using a recurrence relation but I don't know how to compose it. I tried defining $b_n$- number of strings of length $n$ as required that end with a 3. $c_n$- number of strings of length $n$ as required that end with 1. $d_n$- number of strings of length $n$ as required, without any odd digits, and so $a_n=b_n+c_n+d_n$... But I don't think this is the right way. I would love to get some help on that question. Thanks in advance :)

Edit: could it be solved using the binomial theorem?

Answer 1

I am not sure if I interpreted the question right (correct me if I'm wrong), but for $n=3$ I have $a_3 = 11$.

Using a different approach, given a string of length $n$. Since there are 2 even digits, there are $2^k$ ways to arrange the first $k$ letters of the string (where $k=0,...,n-1$, since each string has a single $1$-digit).

For the odd string section (where we now have $n-k$ letters left to fill in), there are $(n-k)$ ways to do this, since we can select one position out of $n-k$ unfilled letters to be the $1$-digit, and then fill the rest to be the digit $3$.

Thus, we have: $$a_n = \sum_{k=0}^{n-1} 2^k (n-k)$$

Using the Geometric sum formula (and differentiating the formula to find the closed form of $\sum {k2^k}$) we have: $$a_n = 2^{n+1} - (n+2)$$

So we have $a_4 = 26$ and $a_{2015} = 2^{2016} - 2017$.

---

To find a possible recurrence relation (which I don't have a interpretation for right now), we can use generating functions, where if we let $A(x) = \sum_{n\geq 0} a_n x^n$ we have:

$$\begin{align} A(x) &= \frac{2}{1-2x} - \frac{x}{(1-x)^2} - \frac{2}{1-x} \\ &= \frac{x}{(1-x)^2 (1-2x)} \end{align}$$

If we log both sides, differentiate and then multiply both sides by $x$, we have: $$\frac{x A'(x)}{A(x)} = \frac{\sum_{n\geq 0} n a_n x^n}{\sum_{n\geq 0} a_n x^n} = 1 + \frac{2}{1-2x} + \frac{2}{1-x}$$ $$\sum_{n\geq 0} n a_n x^n = \left(1 + \frac{2}{1-2x} + \frac{2}{1-x}\right) \sum_{n\geq 0} a_n x^n \tag{1}$$

Equating the coefficients on both sides of $(1)$ we have the recurrence: $$a_n = \frac{2}{n-1} \sum_{k=1}^{n-1} (2^{k-1} + 1)a_{n-k}$$ Where we take $a_1 =1$ and $a_0 = 0$.