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