3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Closely related question - mathoverflow.net/q/67359/41291 - maybe even contains an answer? $\endgroup$ – მამუკა ჯიბლაძე Dec 9 '15 at 20:37
  • $\begingroup$ Thanks for the suggestion. I believe pairing (as described in the question) will not work as sequences of $...0011...$ are allowed suggesting I can not split the $0$s and the $1$s and try to pair them. $\endgroup$ – Nikola Dec 10 '15 at 11:24
2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ This solves the question for $k=3$, and for every specific $k$, one can argue that there is a rational g.f. as in your case... but can one attack the general $k$ case? $\endgroup$ – Per Alexandersson Dec 9 '15 at 23:42
  • 1
    $\begingroup$ I think this is $k=2$ in the context of the original problem? We take $k$ even and look at runs of length $k+1$. $\endgroup$ – John Machacek Dec 10 '15 at 2:58
  • $\begingroup$ Thank you for the answer! This sheds a lot of light on how to tackle the specific case of $k=2$. But can the recurrence relations presented, be somehow generalized to be able to address the general $k$ case. In the case of $k=2$ the only thing that is not allowed in a good permutation is the sequence $000$. In the general case, however, any sequence of $k+1$ elements must not contain $\frac{k}{2} +1$ $0$s which can be arbitrarily permuted within the sequence itself. I find it hard to see the recurrence relation that could describe this. $\endgroup$ – Nikola Dec 10 '15 at 11:07
  • $\begingroup$ Nikola, you're missing something. In my solution above, a good permutation is one in which, for every even k >=2, each subsequence of length k+1 contains at least k/2 1s. If a good permutation was defined to be merely one that avoids 000, then the answer would be different. So my solution correctly and completely answers your original question. But your question could be generalized along the following lines. Fix A,B,C,D,E. How many permutations have the property that for all k>=A, every subsequence of length Bk+C contains at least Dk+E 1s? $\endgroup$ – David Callan Dec 10 '15 at 18:47
  • $\begingroup$ Re last comment, the case A=1, B=2, C=1, D=1, E=0 is equivalent to the original question. $\endgroup$ – David Callan Dec 10 '15 at 18:47

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.