We are given a binary sequence $x\in \{0,1\}^n$ and an integer $l\leq n$. Let $A$ denote the set of integer sequences $\alpha=(\alpha_1,\ldots,\alpha_l)$ satisfying $1\leq\alpha_1<\alpha_2<\ldots<\alpha_l\leq n$. For $\alpha\in A$ and $y\in\{0,1\}^n$, let $f_\alpha(y)$ be the length $l$ subsequence of $y$ with indices $\alpha_i$; that is, $$ f_\alpha(y)=(y_{\alpha_1},\ldots,y_{\alpha_l}). $$ What is the size of the following set? $$ \{f_\alpha(y)\mid y\in\{0,1\}^n,\,\alpha\in A,\, \neg f_\alpha(x)\vee f_\alpha(y)=(1,\ldots,1)\} $$ For example, suppose $n=7$, $l=5$ and $x=1101111$. The set contains four elements, namely $$ 01111,\,10111,\,11011,\,11111. $$ We can express each element as $f_\alpha(y)$ for some $\alpha,y$ satisfying the condition as follows. Note that we can do so in more than one way, but we only want to count each length 5 sequence once. $$\begin{eqnarray*} 01111&=&f_{3,4,5,6,7}(0001111),\\ 10111&=&f_{1,3,5,6,7}(1000111),\\ 11011&=&f_{1,2,3,6,7}(1100011),\\ 11111&=&f_{3,4,5,6,7}(0011111). \end{eqnarray*}$$
Incorrect solution: Let $||x||_1$ denote the hamming weight of $x$. Given that $||x||_1 = k$, there exist $2^{n-k}$ binary sequences $y \in \{0,1\}^n$, that have a $1$ at at least all the indices where $x$ is $1$. Hence, such $y$ satisfies the desired condition for each $\alpha\in A$. Hence, the number of $l$-out-of-$n$ combinations from such sequences (that is, sequences of the form $f_\alpha(y)$) that are part of the solution is given by the expression: $2^{n-k} \dbinom{n}{l}$. Similarly, if we consider the $y's$ that match the $1$ bits of $x$ at exactly $k-1$ spots, then the number of such $y's$ is also $2^{n-k}$ as we are still fixing the value of exactly $k$ bits. In this manner, we get the total count for the $l$-out-of-$n$ combinations from $\{0,1\}^n$ that match $x$ as: \begin{equation} 2^{n-k} \cdot \sum\limits_{w=0}^k \dbinom{n-w}{l}. \end{equation} But, the above expression clearly overcounts as the $l$-out-of-$n$ combinations from different $y's$ overlap. Now, we can go with an inclusion-exclusion principle based solution but I wasn't able to find a closed-form expression by moving in that direction. Note that all that we are given is the hamming weight of $x$, and we have no knowledge of the exact number of transitions (i.e., $0$ to $1$ or vice-versa) in $x$. It is easy to see that the hamming weight of a binary sequence can be used to upper and lower bound the number of transitions in it. But, I am not sure if doing that is of any help here.
An algorithm to solve the problem might maintain a counter $c$ initialized to $0$ to store the count. It should first list all $l$-out-of-$n$ combinations one by one for each $y \in \{0,1\}^n$. Hence, we consider the $|A|=\dbinom{n}{l}$ ways to select unique sets of $l$ indices $\alpha$. Next, for each $\alpha$, we select the corresponding sub-sequences of $x$ and $y$, which are denoted as $f_\alpha(x)$ and $f_\alpha(y)$, respectively. Finally, we see whether $\neg f_\alpha(x) \vee f_\alpha(y)$ gives an $l$ bits long sequence of $1's$. If yes, then the counter $c$ is incremented by $1$. But, we must avoid the overcounting scenario as described in the example above.
Thanks for your help!