Counting Specific Permutations of Elements in a Multiset

Question

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.

Answer 1

UPDATE. I've simplified the exposition of my approach below and added an example of $k=2$.

Construct a 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, 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

Answer 2

Say a sequence of 0s and 1s is good if it meets the specified conditions, that is, if, for every even $k \ge 2$, each subsequence of length $k+1$ contains at least $k/2$ 1s. Let $a(n,m)$ denote the number of good permutations of the multiset $\{1^n,0^m\}$. Then $a(n-m,m)$ is the answer to the question posed.

Since 3 consecutive 0s are forbidden, a good permutation $p$ has one of the 3 mutually exclusive forms (i) 1$p'$, (ii) 01$p'$, (ii) 001$p'$, where $p'$ is good. Conversely, if $p'$ is good, then certainly $1p'$ and $01p'$ are good. The key observation is that $001p'$ is good iff $0p'$ is good, and good permutation of the form $0p'$ are obtained by discarding the $1p'$ permutations from all good permutations of that length.

So, for $n+m\ge 3$, the 3 cases are counted respectively by (i) $a(n-1,m),$ (ii) $ a(n-1,m-1),$ (iii) $ a(n-1,m-1)-a(n-2,m-1)$. Together with initial conditions for small $n,m$, this gives a recurrence for $a(n,m)$, leading to the rational expression $$ F(x,y)=\frac{1 + y - x y + y^2}{1 - x - 2 x y + x^2 y} $$ for the generating function $F(x,y):=\sum_{n,m\ge 0}a(n,m)x^n y^m$.