Maximal difference between k randomly drawn numbers from 1 to n – Looking for formula to sequence - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:27:57Z http://mathoverflow.net/feeds/question/99995 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99995/maximal-difference-between-k-randomly-drawn-numbers-from-1-to-n-looking-for-for Maximal difference between k randomly drawn numbers from 1 to n – Looking for formula to sequence Christoph 2012-06-19T11:43:18Z 2012-06-21T10:00:09Z <p>Hello! I have an interesting problem that seemed simple to me, but I'm unable to solve it on my own.</p> <p>Suppose I am drawing <em>k</em> numbers out of <em>n</em> numbers labeled from <em>1 to n</em>. Considering all $\binom{n}{k}$ combinations of numbers drawn, how often does the <strong>maximal difference q</strong> between two consecutive numbers – but also between zero and the lowest number, or the highest number and n – occur.</p> <p>I already found an algorithm to compute the sequence, but it's too computationally intense for large <em>n</em>, so I'm looked for an explicit formula. If it's too complicated to find a formula a distribution would also be fine.</p> <p>I think someone must already have worked on this problem, but I can't find anything.</p> <p>The resulting series is:<br> (Read: n,m:: q:number of combinations with q as maximal difference)<br> 2,1:: 1:2<br> 3,1:: 1:1, 2:2<br> 3,2:: 1:3<br> 4,1:: 1:0, 2:2, 3:2<br> 4,2:: 1:3, 2:3<br> 4,3:: 1:4<br> 5,1:: 2:1, 3:2, 4: 2<br> ...<br> 10,1:: 8:2, 9:2, 5:2, 6:2, 7:2<br> 10,2:: 3:3, 4:12, 5:12, 6:9, 7:6, 8:3<br> 10,3:: 2:4, 3:36, 4:40, 5:24, 6:12, 7:4<br> 10,4:: 2:45, 3:90, 4:50, 5:20, 6:5<br> 10,5:: 1:6, 2:120, 3:90, 4:30, 5:6<br> 10,6:: 1:35, 2:126, 3:42, 4:7<br> 10,7:: 1:56, 2:56, 3:8<br> 10,8:: 1:36, 2:9<br> 10,9:: 1:10 </p> <p>Where the problem arose: I'm doing a masters thesis in bioinformatics on a quick clustering algorithm. So I'm looking for shared <em>q</em>-grams (substrings with length q) of pairs of sequences with the length <em>n</em> that differ in at most <em>m</em> sites. I want to find the biggest <em>q</em> possible so that 99% of all sequences of length <em>n</em> with <em>m</em> randomly distributed differences share a substring of length <em>q</em>.</p> <p>Illustration of the problem: (n=10, m=3; X for mismatch, "." for match)</p> <pre><code>X....X...X -&gt; 4 ..X..X..X. -&gt; 2 .......XXX -&gt; 7 </code></pre> <p>Here's the python script:</p> <pre><code>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 </code></pre> http://mathoverflow.net/questions/99995/maximal-difference-between-k-randomly-drawn-numbers-from-1-to-n-looking-for-for/99998#99998 Answer by Douglas Zare for Maximal difference between k randomly drawn numbers from 1 to n – Looking for formula to sequence Douglas Zare 2012-06-19T12:44:25Z 2012-06-21T10:00:09Z <p>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.</p> <p>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$:</p> <p>$$f(n,k,q) = \sum_{a=0}^{k+1} (-1)^a {k+1\choose a}{n-aq\choose k}.$$</p> <p>To count sequences where the maximum is exactly $q$, take $f(n,k,q+1)-f(n,k,q)$.</p> <hr> <p>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:</p> <p>$$f(n,k,q) = \sum_{a=0}^{\lfloor n/q \rfloor} (-1)^a {k+1\choose a}{n-aq\choose k}.$$</p>