Finding the number of ways of choosing 4 distinct integers from first n natural numbers so that no two are consecutive.

Question

Question:

Show that the number of ways of choosing 4 distinct integers from the first $n$ numbers so that no two are consecutive is $\binom{n-3}{4}$.

I tried to find it by the principle of inclusion and exclusion. The total number of ways of choosing 4 integers here is $\binom{n}{4}$, number of ways to choose them such that at least 2 are consecutive is $\binom{n-2}{2}×(n-1)$ and at least three are consecutive is $\binom{n-3}{1}×(n-2)$ and all 4 can be consecutive in $n-3$ ways.

Thus total number of ways such that no two are consecutive by principle of inclusion and exclusion should be $$\binom{n}{4} - \binom{n-2}{2}\times(n-1) + \binom{n-3}{1}\times(n-2) - (n-3) $$

How can I show this is $\binom{n-3}{4}$? Or did I do anything wrong? Please help. Thanks in advance.

Answer 1

You must have done something wrong, since for $n=7$ your expression is $35-60+20-4=-9.$

To use inclusion-exclusion, your events should be something like "includes $i$ and $i+1$". Now the number of choices which include $i$ and $i+1$ is $\binom{n-2}{2}$, and there are $n-1$ possible $i$, so you should start $$\binom{n}{4}-(n-1)\binom{n-2}{2}...$$ Then how many ways are there to have $i$ and $i+1$ and $j$ and $j+1$, for $i<j$? If $j=i+1$ there are $n-3$ ways (and there are $n-2$ choices for $i$). If not there is $1$ way, and $\binom{n-1}{2}-(n-2)=\binom{n-1}2$ choices for $i,j$ (the number of pairs minus the number where $i,j$ are consecutive). So it should continue $$\binom{n}{4}-(n-1)\binom{n-2}{2}+(n-3)(n-2)+\binom{n-2}2...$$ For the final term, the only way three events can happen is if $i+1=j,j+1=k$, for which there are $n-3$ options. So overall you get $$\binom{n}{4}-(n-1)\binom{n-2}{2}+(n-3)(n-2)+\binom{n-2}2-(n-3).$$

[This is very close to what you had, the only difference is the extra term for having two separate consecutive pairs of $+\binom{n-2}2$.]

To see that the above is the same as $\binom{n-3}{4}$, note that $(n-1)\binom{n-2}2=3\binom{n-1}3$. Also $(n-3)(n-2)=2\binom{n-2}{2}$, so this can be written as $$\binom{n}4-\binom31\binom{n-1}3+\binom32\binom{n-2}2-\binom33\binom{n-3}1.$$ This is precisely the inclusion-exclusion formula for the number of choices of $4$ numbers from the first $n$ which don't include any of the last $3$, so is $\binom{n-3}4$.

Answer 2

Each admissible choice is a binary word of length $n$ containing exactly four ones, and satisfying the extra condition that after the first three ones there is at least one zero.

Given an admissible word $w$ remove the first zero after each of the first three ones, and you obtain a binary word $w'$ of length $n-3$ containing four ones, and satisfying no extra condition. Conversely: Given any binary word $w'$ of length $n-3$ containing four ones insert a zero after the first three ones, and you obtain an admissible word $w$ of length $n$.

The number of admissible words of length $n$ therefore is ${\displaystyle{n-3\choose 4}}$.

Answer 3

Assume $n>=7$.

Starting from the set {1,3,5,7}, any solution set can be reached by increasing the gaps between the chosen integers : you have to place $n-7$ gaps in any of the 5 following spots: before the 1, between 1 and 3, between 3 and 5, between 5 and 7, or after 7.

For instance, if $n=20$, you can place the $n-7=13$ extra gaps in the 5 spots like that: (2,5,0,2,4) ; then the set becomes {3,10,12,16} : the 4 digits have been increased by 2, then the three last digits have been increased by 5, then the two last digits have been increased by 0, then the last digit has been increased by 2, and the 4 biggest integers in {1,...,20} are not used.

In that way you reach all the solutions once and only once. That means the number of solutions is the number of ways to place $n-7$ items in $5$ boxes.

Generally the number of ways to place $k$ items in $l$ boxes is $\binom{l+k-1}{k-1}$ ; Hence the solution to your problem is $\binom{n-7+5-1}{5-1}$=$\binom{n-3}{4}$

Answer 4

A recursive proof:

Let $A(k,n)$ be the number of ways to pick k integers from {1,...n} s.t. no two consecutives numbers are picked. If $n<2k-1$, then $A(k,n)=0$. $A(k,2k-1)=1$.

If you pick k integers from {1,...n} s.t. no two consecutives numbers are picked, there are two cases:

• Either n is not picked. Then the $k$ integers are picked in {1,...,n-1}. The number of such solutions is $A(k,n-1)$.
• Either n is picked. Then n-1 isn't picked and $k-1$ integers are picked in {1,...,n-2}. The number of such solutions is $A(k-1,n-2)$.

Building from $A(0,n)=1$ and $A(1,n)=n$ with the recursive rule $A(k,n)=A(k,n-1)+A(k-1,n-2)$, you reconstruct the Pascal tree and conclude that $A(k,n)=\binom{n-3}{k}$