1
$\begingroup$

Witness a draw of lotto numbers, say '$6$ out of $45$'—or $49$, or $59$, this may vary by locality—and watch out for two (or more) consecutive numbers in the draw, e.g. $\,\lbrace 3,15,20,26,27,36\rbrace$. This appears to happen fairly often.

How many draws are there, if a draw consists of $\,k\,$ numbers out of $\,\lbrace 1,2,\dots,n\rbrace\:$?

Assume that $\,n\,$ and $\,1\,$ are not adjacent, that $k>1$, and that $k\leqslant\frac n2\,$ if $\,n\,$ is even, or
$k\leqslant\frac{n+1}2\,$ for odd $\,n$.

The preceding bounds for $\,k\,$ are reasonable upon regarding the draws $\,\lbrace 2,4,\ldots,n\rbrace$ or $\,\lbrace 1,3,\ldots,n\rbrace$.

  • My first approach was to choose the consecutive pair first, having $n-1$ possibilities, then drawing $k-2\,$ out of the remaining $\,n-2\,$ numbers, yielding $\,(n-1)\binom{n-2}{k-2}\,$ draws.
    But the associated probability $${(n-1)\binom{n-2}{k-2}\over\binom{n}{k}}\:=\:\frac{k\,(k-1)}n$$ shows this cannot be correct. There must be some overcounting when the secondly drawn $k-2$ numbers are adjacent to the already fixed pair.

  • A more weird approach was to consider the random variable $$ X(d_1,\dots,d_k):=\sum_{i=1}^k(d_{i+1}-d_i)^2\;\text{ where }d_{k+1}=d_1$$ on the set of all draws $(d_1,\dots,d_k)$ and somehow exploit that at least one summand equals $1$ when evaluated at a draw of interest. (It's then expected to be smaller than $E[X]$.)

$\endgroup$
3
$\begingroup$

Use the stars and bars method:

Drawing $k$ numbers out of $n$ means that you have $k$ 'bars' that you need to place between or at the end of $n-k$ other numbers (which are the 'stars'), i.e the $k$ 'bars' need to be in any of $n-k+1$ spots. Hence, you have:

$$n-k+1 \choose k$$

possible ways to have a draw without having any consecutive numbers. If you want the numbers of draws with consecutive numbers, then that is of course that number subtracted from all possible drawing, so that is:

$${n \choose k} - {n-k+1 \choose k}$$

Example: Draw 3 out of 7, i.e $k=3$ and $n=7$

Then you have $4$ numbers not drawn which are the stars:

$$****$$

And now you need to place the 'bars' between or at the end of them, but you cannot place two or more bars in the same spot. That is, place $3$ bars in any of the $5$ open slots:

$$.*.*.*.*.$$

For example, one possibility is:

$$|*|**|*$$

which corresponds to drawing numbers $1$,$3$, and $6$

$\endgroup$
  • $\begingroup$ @Hanno Yes, they should be the bars. Good eyes! Just updated it ... $\endgroup$ – Bram28 Nov 13 '17 at 21:07
  • $\begingroup$ I find this remarkable: For $\,k=6\,$ out of $\,n=49$ one has $\binom{49-6+1}{6}\big/\binom{49}{6}=0.50480$, whence draws with consecutive numbers are (almost) equally likely as those without! $\endgroup$ – Hanno Nov 13 '17 at 22:23
  • $\begingroup$ @Hanno Huh! That's pretty cool, thanks for sharing! It reminds me of the birthday problem in that our (mistaken!) intuition is that the chance of getting consecutives is a good bit less than 50% $\endgroup$ – Bram28 Nov 13 '17 at 22:28

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.