On this page
How many ways can you pick 3 numbers from 1 to 10 so that no two are next to each other? Seats in a row where no two friends sit together is the same problem. The trick is to stop counting the chosen numbers and count the gaps between them.
What is the formula for choosing r numbers with no two consecutive?
The number of ways to choose r numbers from 1, 2, ..., n with no two consecutive is (n - r + 1)Cr. Toufik Mansour and Yidong Sun's paper on combinations without certain separations opens by noting that Kaplansky published a derivation of this count in 1943. The paper also gives the general form: if every pair of chosen numbers must have at least p unchosen numbers between them, the count is (n - p(r - 1))Cr. Put p = 1 and you get (n - r + 1)Cr.
Why does the gap method give (n - r + 1)Cr?
Let the chosen numbers be a1 < a2 < ... < ar. Instead of tracking them, track the unchosen numbers around them. There are n - r unchosen numbers, and they fall into r + 1 gaps:
g0, before the first chosen number (can be 0)
g1 to g(r-1), between neighbouring chosen numbers (each at least 1, because no two chosen numbers may touch)
gr, after the last chosen number (can be 0)
So g0 + g1 + ... + gr = n - r, and each choice matches exactly one list of gaps.
Now take one unchosen number out of each of the r - 1 middle gaps. That leaves n - 2r + 1 to share among r + 1 gaps, each 0 or more.
That is exactly the stars and bars set-up. The stars and bars theorem) says the number of ways to write a whole number N as an ordered sum of k non-negative integers is (N + k - 1)C(k - 1). Here N = n - 2r + 1 and there are k = r + 1 gaps, so the count is (n - 2r + 1 + r)Cr = (n - r + 1)Cr.
How do you check it by listing?
Always test a new formula on a case small enough to list in full. Take n = 6 and r = 3. The formula says (6 - 3 + 1)C3 = 4C3 = 4. The full list is:
{1, 3, 5}
{1, 3, 6}
{1, 4, 6}
{2, 4, 6}
Four sets, as promised. This check catches a common slip: writing (n - r)Cr because you forgot one of the end gaps.
Is there a faster way to see it?
Yes, and it is a good second check. Shift the chosen numbers: subtract 0 from a1, 1 from a2, 2 from a3, and so on. Because each chosen number is at least 2 more than the one before, the shifted numbers are still strictly increasing, and the largest is at most n - (r - 1) = n - r + 1. So every valid choice becomes an ordinary r-number choice from 1 to n - r + 1, and adding the shifts back reverses it. That is (n - r + 1)Cr again.
The gap method still pays off on harder versions: for "at least two between", take two from each middle gap and you get (n - 2(r - 1))Cr.
You can check the circle formula from Mansour and Sun on n = 6, r = 2: it gives 6/4 times 4C2 = 9. Counting directly, there are 15 pairs from 6 seats in a circle and 6 of them are neighbours, which leaves 9.
How should you handle these questions in an exam?
When a question says "no two adjacent", run through this:
Decide whether the positions are in a line or a circle.
Write the gaps, and mark which ones must be at least 1 (or at least p).
Remove the minimum from those gaps, apply stars and bars, then check on a case with n of 6 or 7 by listing.
Worked example: 10 chairs in a row, 3 students, no two side by side. That is 7 empty chairs in 4 gaps; remove 2 for the middle gaps and share 5 among 4: 8C3 = 56. If the students are different people, multiply by 3! to get 336.
If stars and bars itself still feels shaky, the Fermi Concept Library has every mathematics concept with its own lesson and its place in the map. For practice, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
