Combination with a minimum number of elements in a fixed length subset
For each particular $m,k$ you can get a recurrence formula and solve it. Perhaps this way you can obtain a general formula. Here is how to find the recurrence formula:


The language of all valid sequence is regular. Construct a DFA (deterministic finite automaton) that accepts the language. (An optimization: construct a "partial" DFA in which sometimes there is no outgoing edge labeled $0$.)
Suppose the transition matrix is $A$, the initial state is $s$, and the accepting states are $F$. Then the number of sequences of length $n$ is $\alpha_n = 1_F A^n 1_s$.
Compute the Jordan normal form of $A$, decompose $1_F,1_s$ according to the Jordan basis, and so obtain a formula for $\alpha_n$.


Instead of using DFAs, you can use generating functions, which really amounts to the same.

Here is a very simple example: $m = 2$ and $k = 1$. The regular language here is all words not containing $00$, that is $1^*(10)^*1^*$. The minimal partial DFA has two states $s_0,s_1$ which correspond to the two possible "histories" (we can assume that the part of the sequence before it actually starts consists entirely of 1s) - in general there will be $2^{m-1}$ states (if $k &lt; m-1$ then actually less, since some of them would be invalid). The transitions are: On $0$, transition from $s_1$ to $s_0$; On $1$, transition from $s_0,s_1$ to $s_1$. The starting state is $s_1$. All states are accepting (this will always be the case with a minimal partial DFA). The transition matrix is
$$ A = \begin{pmatrix} 0 &amp; 1 \\ 1 &amp; 1 \end{pmatrix}. $$
Therefore
$$ \alpha_n = \begin{pmatrix} 1 &amp; 1 \end{pmatrix} \begin{pmatrix} 0 &amp; 1 \\ 1 &amp; 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$
The matrix $A$ has two eigenvalues $(1 \pm \sqrt{5})/2$, and furthermore
$$ A = \begin{pmatrix} 1 &amp; 1 \\ \frac{1-\sqrt{5}}{2} &amp; \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} &amp; 0 \\ 0 &amp; \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1}{2} + \frac{\sqrt{5}}{10} &amp; -\frac{\sqrt{5}}{5} \\ \frac{1}{2} - \frac{\sqrt{5}}{10} &amp; \frac{\sqrt{5}}{5} \end{pmatrix}. $$
Thus
$$
\begin{align*}
\alpha_n &amp;= \begin{pmatrix} \frac{3-\sqrt{5}}{2} &amp; \frac{3+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} &amp; 0 \\ 0 &amp; \frac{1+\sqrt{5}}{2} \end{pmatrix}^n \begin{pmatrix} -\frac{\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} \end{pmatrix} \\ &amp;=
\frac{5-3\sqrt{5}}{10} \left( \frac{1-\sqrt{5}}{2} \right)^n +
\frac{5+3\sqrt{5}}{10} \left( \frac{1+\sqrt{5}}{2} \right)^n.
\end{align*}
$$
The first few numbers (starting with $\alpha_0$) are $1,2,3,5,8,13,\ldots$, and we recognize the Fibonacci sequence: $\alpha_n = F_{n+2}$.



An alternative to following these steps is noticing that $\alpha_n$ is always defined by a recurrence relation of length at most $2^{m-1}$. So for general $m,k$, all you have to do is calculate enough of the sequence $\alpha_n$ to determine the coefficients: you need to calculate $\alpha_0,\ldots,\alpha_{2^m-1}$, which will give you $2^{m-1}$ equations.

Here is how to do it for $(m,k) = (2,1)$: $\alpha = 1,2,3,5$. If $\alpha_n = c_1 \alpha_{n-1} + c_2 \alpha_{n-2}$ then $3 = 2c_1 + c_2$ and $5 = 3c_1 + 2c_2$. We deduce that $c_1 = c_2 = 1$ and so the recurrence is $\alpha_n = \alpha_{n-1} + \alpha_{n-2}$.

Having recovered the recurrence relation, we solve it as usual. It will usually be the case that all roots of the characteristic polynomial are distinct, and that the asymptotics of the sequence are given by the largest root (though in principle it depends on the actual sequence).