I have a question regarding counting permutations of a multiset's elements. The problem is the following:


Given a multi-set $M=\{0^{m}, 1^{n-m}\}$ the number of all possible permutations of its elements is given by the formula $\frac{n!}{m!(n-m)!}$. How can I come up with a formula that gives the number of permutations in which every sequence of length $k+1$, where $k$ is even, contains at least $\frac{k}{2}$ $1$s.


E.g. for $n=6, m=3, k=2$ the permutation $101010$ should be counted, but the permutation $111000$ should not be counted.


I tried to employ the inclusion-exclusion principle, but was unable to come up with a solution to the problem. I would appreciate any ideas, references or solutions.


Thanks!


**UPDATE:**
Thank you @Max and @DavidCallan for your solutions and helpful discussions! I can now completely follow your answers. Indeed I have formulated the question vaguely. My goal is to find the following: I need a function $A(m,n,k)$, which basically gives the number of permutations of the multi-set $M=\{0^{m}, 1^{n-m}\}$ in which every sequence of length $k+1$ contains at least $\frac{k}{2}$ $1$s. $A$ will then be evaluated for even $k$s *only*. I need this because I would like to know what is the probability that a random permutation of the aforementioned multi-set satisfies the condition for different $k$s. Having this in mind I think @Max's solution can directly give me the answer I need.



Counting Specific Permutations of Elements in a Multiset
**UPDATE**. I've simplified the exposition of my approach below and added an example of $k=2$.


Construct a [de Bruijn graph](https://en.wikipedia.org/wiki/De_Bruijn_graph) $G$ with the vertices representing the $(k+1)$-mers that have at least $k/2$ ones, which we denote $u\_1, u\_2, \dots, u\_d$. Then every restricted permutation of $M$ corresponds to a walk of length $n-(k+1)$ in $G$. However, not every such walk represents a permutation of $M$ because of a possible imbalance between zeroes and ones.


To account for the number of ones and zeroes in walks in $G$, we can assign algebraic weights to the arcs of $G$. Namely, to an arc $u\to v$ we assign the weight 1 whenever $v$ ends in one, and the weight $y$ whenever $v$ ends in zero. Let $A$ be the weighted transfer (adjacency) matrix of $G$.


Let us also define $w(u)$ be the number of zeroes in a $(k+1)$-mer $u$. Now, by the [transfer matrix method](http://www-math.mit.edu/~rstan/pubs/pubfiles/79.pdf), we can express the number $a\_{n,m}$ of restricted permutations of $M$ as the coefficient of $y^m$ in $g\_{n-(k+1)}(y)$, where
$$g\_q(y) = [y^{w(u\_1)},\dots,y^{w(u\_d)}]\cdot A^q\cdot [1,\dots,1]^T.$$
Recalling that $A$ is a zero of its characteristic polynomial, the powers of $A$ (and thus $g\_q(y)$) satisfy a linear recurrent relation, which allows us to obtain the (rational) generating function for $g\_q(y)$ and then for $a\_{n,m}$.


**EXAMPLE**. For $k=2$, the graph $G$ contains seven vertices: $001, 010, 011, 100, 101, 110, 111$ and its transfer matrix is
$$A = \begin{pmatrix}
0 & y & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & y & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & y & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & y & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & y & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & y & 1
\end{pmatrix}
$$
The minimal polynomial of $A$ is $f(x) = x^3 - x^2 - xy - y^2$. It allows us to obtain the generating for $g\_q(y)$:
$$G(x,y) = \sum\_{q=0}^\infty g\_q(y)\cdot x^q = \frac {{y}^{4}{x}^{2}+2\,{x}^{2}{y}^{3}+{x}^{2}{y}^{2}+2\,x{y}^{3}+3\,x{y}^{2}+xy+3\,{y}^{2}+3\,y+1}{1-x-x^2y-x^3y^2}.$$
From $G(x,y)$, we can further derive the following generating function for the number $a\_{n,m}$ of restricted permutations of $M$:
$$\sum\_{n,m} a\_{n,m} x^n y^m = G(x,y)\cdot x^{k+1} + \sum\_{i=0}^k x^i (1+y)^i = \frac {{x}^{2}{y}^{2}+xy+1}{1-x-x^2y-x^3y^2}.$$


P.S. Similar approach for a different problem was used in my preprint <http://arxiv.org/abs/1510.07926>


