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

Question

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

Answer 1

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}

Answer 2

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.