1
$\begingroup$

Hello! I have an interesting problem that seemed simple to me, but I'm unable to solve it on my own.

Suppose I am drawing k numbers out of n numbers labeled from 1 to n. Considering all $\binom{n}{k}$ combinations of numbers drawn, how often does the maximal difference q between two consecutive numbers – but also between zero and the lowest number, or the highest number and n – occur.

I already found an algorithm to compute the sequence, but it's too computationally intense for large n, so I'm looked for an explicit formula. If it's too complicated to find a formula a distribution would also be fine.

I think someone must already have worked on this problem, but I can't find anything.

The resulting series is:
(Read: n,m:: q:number of combinations with q as maximal difference)
2,1:: 1:2
3,1:: 1:1, 2:2
3,2:: 1:3
4,1:: 1:0, 2:2, 3:2
4,2:: 1:3, 2:3
4,3:: 1:4
5,1:: 2:1, 3:2, 4: 2
...
10,1:: 8:2, 9:2, 5:2, 6:2, 7:2
10,2:: 3:3, 4:12, 5:12, 6:9, 7:6, 8:3
10,3:: 2:4, 3:36, 4:40, 5:24, 6:12, 7:4
10,4:: 2:45, 3:90, 4:50, 5:20, 6:5
10,5:: 1:6, 2:120, 3:90, 4:30, 5:6
10,6:: 1:35, 2:126, 3:42, 4:7
10,7:: 1:56, 2:56, 3:8
10,8:: 1:36, 2:9
10,9:: 1:10

Where the problem arose: I'm doing a masters thesis in bioinformatics on a quick clustering algorithm. So I'm looking for shared q-grams (substrings with length q) of pairs of sequences with the length n that differ in at most m sites. I want to find the biggest q possible so that 99% of all sequences of length n with m randomly distributed differences share a substring of length q.

Illustration of the problem: (n=10, m=3; X for mismatch, "." for match)

X....X...X -> 4
..X..X..X. -> 2
.......XXX -> 7

Here's the python script:

import itertools
def f(n,m):
    rdict={}
    for d in itertools.combinations(range(n),m):
        t=[-1]+list(d)+[n]
        m=max([x[0]-x[1] for x in zip(t[1:],t[:-1])])-1
        if not rdict.has_key(m):
            rdict[m]=1
        else:
            rdict[m]+=1
    return rdict
$\endgroup$
1
  • $\begingroup$ When you say "or the highest number and $n$," do you mean $n+1$? $\endgroup$ Jun 19, 2012 at 12:25

1 Answer 1

2
$\begingroup$

Choices of $k$ out of $n$ correspond to ordered $k+1$-tuples of nonnegative numbers which add up to $n-k$ by counting the dots between the Xs.

The number of such $k+1$-tuples so that $a$ particular terms are at least $q$, with no restrictions on the others, is $n-aq \choose k$ [edit: when $n-aq \ge 0$, and $0$ otherwise], since subtracting $q$ from each of the terms we know are at least $q$ gives an unrestricted $k+1$-tuple adding to $n-aq$. So, the technique of inclusion-exclusion lets us count $f(n,k,q)$, the number of $k+1$-tuples with no term which is at least $q$:

$$ f(n,k,q) = \sum_{a=0}^{k+1} (-1)^a {k+1\choose a}{n-aq\choose k}.$$

To count sequences where the maximum is exactly $q$, take $f(n,k,q+1)-f(n,k,q)$.


Edit: The above formula is incorrect because it includes the terms where $n-aq$ is negative. For these terms, replace $n-aq \choose k$ with $0$, or change the upper limit of the sum:

$$ f(n,k,q) = \sum_{a=0}^{\lfloor n/q \rfloor} (-1)^a {k+1\choose a}{n-aq\choose k}.$$

$\endgroup$
2
  • $\begingroup$ If I implement your f, it always sums up to 0 $\endgroup$
    – Christoph
    Jun 21, 2012 at 8:39
  • $\begingroup$ Oops, I should not have included the terms where $n-aq$ is negative. $\endgroup$ Jun 21, 2012 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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