# Number of sequences with $k$ subsequences of $11$

Let $S_n = \{0,1\}^n$.

Let $S_{i,n} \subseteq S_n$ be a set such that $s \in S_{i,n}$ if and only if $s$ contains exactly $i$ occurences of $11$.

Example for $n=3$. \begin{align*} S_3 &= \{000, 001, 010, 011, 100, 101, 110, 111\}\\ S_{0,3} &= \{000,001,010,100,101\}\\ S_{1,3} &= \{011,110\} \\ S_{2,3} &=\{111\} \end{align*}

Example for $n=4$. \begin{align*} S_4 &= \{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 \}\\ S_{0,4} &= \{0000,0001,0010,0100,0101,1000,1001,1010\}\\ S_{1,4} &= \{0110,0110,1100, 1011,1101\} \\ S_{2,4} &=\{0111,1110\}\\ S_{3,4} &=\{1111\} \end{align*} Therefore $|S_{0,4}| = 8 , |S_{1,4}| = 5, |S_{2,4}| = 2, |S_{3,4}| = 1$.

Is it possible to find a formula for $|S_{i,n}|$ ? Upper and lower bounds would also be nice to have

This sequence can also be found in OEIS but no formula is available

• Maybe get a recurrence by looking at the number of length n that end in 0, 01, 11. – marty cohen Jan 25 '18 at 2:39

## 2 Answers

We can derive a two-variable two generating functions. Define $a_{i,n}:=|S_{i,n}(0)|,\,b_{i,n}:=|S_{i,n}(1)|.$ and $f(x,y)=\sum_{n=0}^\infty\sum_{i=0}^na_{i,n}x^iy^n,\,g(x,y)=\sum_{n=0}^\infty\sum_{i=0}^{n-1}b_{i,n}x^iy^n$. From the recursion relation of the previous answer, we obtain $$\begin{cases} f&=y\,f+y\,g, \\ g &= y\,f+xy\,g+\frac1{1-x}\Big(\frac1{1-y}-\frac1{1-xy}\Big) \end{cases}$$ Then solve for $(f,g)$. \begin{align} f &= \frac{\frac1{1-x}\Big(\frac1{1-y}-\frac1{1-xy}\Big)}{\frac1y-1-x-y+xy}, \\ g &= \Big(\frac1y-1\Big)\,f \end{align}

• Nice attempt!! Is there a way to get upper and lower bounds for the solutions using your generating functions ? – vkonton Feb 4 '18 at 12:24
• @vkonton: You mean an asymptotics for, say, $i=\lfloor \frac n2\rfloor$ as $n\to\infty$? It is possible. I can look into that. – Hans Feb 5 '18 at 0:51
• I found a way around this problem, so I don't really need a solution anymore. I will accept your answer as it is but if you want to investigate this problem further feel free to edit it afterwards! Thanks!! – vkonton Feb 5 '18 at 2:42
• By "found a way around this problem", do you mean that you have circumvented this problem so that you do not have to answer the question to reach the goal of another problem, or that you have found an ingeneous solution to this problem? If it is the latter case, would you mind sharing your solution? If it is the former case, please confirm that as well. Thanks. – Hans Feb 6 '18 at 6:26
• It's the first one, it turns out I don't need to solve this problem after all... – vkonton Feb 7 '18 at 13:41

Let $S_{i,n}(0)$ be the subset of $S_{i,n}$ with its elements each having $0$ at its left most position, and $S_{i,n}(1)$ be that having $1$ at its left most position. We have the recursion relation

$$\begin{cases} |S_{i,n}|&=|S_{i,n}(0)|+|S_{i,n}(1)|, \\ |S_{i,n}(0)|& =|S_{i,n-1}|, \\ |S_{i,n}(1)| &= |S_{i,n-1}(0)|+|S_{i-1,n-1}(1)|+1 \end{cases}$$ Perhaps we can form a system of two two-variable generating functions.