Revisit : $20\choose 5$ subsets without 3,4 or 5 consecutive numbers

combinatoricscombinatorics-on-wordsinclusion-exclusionrecurrence-relations

Addendum-2 just added to my question.

Addendum just added to my question.

$\underline{\textbf{Overview}}$

This is a self-answer question of
this original question.
I strongly suspect that the original question will soon be closed and then deleted.

I’m trying to get the amount of combinations of 5 numbers from one to twenty
without duplicates and without 3,4,and 5 consecutive running numbers.

$\underline{\textbf{Clarification}}$

Let $N = \{1,2,\cdots, 20\}$.
How many distinct subsets of $N$ are there where:

  • The subset has exactly $5$ elements.
  • The subset does not contain $3$ consecutive elements.
    Here, consecutive elements are elements $(k), (k+1), (k+2).$

For example, both of the following sets are satisfactory:

  • $\{1, 2, 4, 5, 7\}$
  • $\{1, 3, 5, 7, 9\}$.

Further, each of the following sets are unsatisfactory:

  • $\{1, 2, 3, 14, 18\}$
  • $\{2, 3, 4, 5, 17\}$
  • $\{8, 9, 10, 11, 12\}$.

$\underline{\textbf{My Background}}$

About $50$ years ago I took a Probability course in college and did ok. I have
forgotten much of the theory, and usually rely exclusively on intuition to attack
Probability (or Combinatorics) problems.

If relevant, some decades ago I survived but have forgotten much of:

  • "Real Analysis : Volume 1 : 2nd Ed." (Apostol, 1966).

  • The first $(2/3)$ of "Elementary Number Theory" (Uspensky and Heaslett, 1938)
    [through quadratic reciprocity].

$\underline{\textbf{Problem Relevance}}$

In my experience, there are three typical approaches to this type of problem:

  • The Direct Approach
  • Recursion
  • Inclusion-Exclusion

This particular problem interested me, because of the challenge involved in providing three distinct solutions, one for each of the above approaches. However, exploring Inclusion-Exclusion,
I concluded that the math involved was too ugly to be reasonably feasible.

However, I was able to find two distinct Direct Approaches to offer.

$\underline{\textbf{My Work}}$

See my self – answers.
For clarity, I have provided a separate answer for :

  • A Direct Approach
  • An Alternate Direct Approach
  • Recursion

Addendum

Given the answers provided by others, it seems to me that the one pending challenge is to find some elegant solution that is based primarily on Inclusion-Exclusion.

I would be very interested if someone could present such a solution.

Edit
Mike Earnest added an Inclusion-Exclusion response to his answer.

Addendum-2

Finally conquered my own private Inclusion-Exclusion challenge for this problem. Just added a separate Inclusion-Exclusion answer.

Best Answer

According to the beautiful explanation , these $5$ numbers can consists of two ways suchthat

  • No consecutive numbers

  • Only one pair of consecutive numbers

So ,

  • For no consecutive numbers :

Lets represent the numbers by letters such that the selected numbers is represened by $\color{blue}{S}$ , and non-selecteds by $\color{red}{S}$.

Now , we must have $15\color{red}{S'}$ and $5\color{blue}{S'}$. Now ,we will distribute these $5$ blue $S'$ among and ends of $15\color{red}{S'}$ . We can do it by $C(16,5)$ ways.For example , one of the distribution is $$\color{blue}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}$$

Now , think that $$1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20=\color{blue}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}$$

So , we select the numbers $\{1,5,8,10,12\}$

  • For only one pair of consecutive numbers :

Select one of the possible place among $16$ gaps (ends and between the red letters), and place two blue letters in that place. We can do it by $C(16,1)$ ways.By using the same logic , select $3$ place for the remaining letters among $15$ suitable places by $C(15,3)$.For example , $$\color{blue}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}$$

Above ,we select $\{1,5,8,11,12\}$

So , the answer is $$C(16,5) + C(16,1) \times C(15,3) = 4368+16 \times455 =11648$$

$\mathbf{EDITION}$: We can also have two separate consecutive numbers such as $\{1,2,5,7,8\}$

So , select $2$ places among $16$ suitable places by $C(16,2)$ to place double blue letters and select one place for the remaining by $C(14,1)$.

For example , $$\color{blue}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{red}{S}\color{blue}{S}\color{blue}{S}$$

We select $\{1,2,10,19,20\}$

So , the answer is $$C(16,5) + [C(16,1) \times C(15,3) ]+ [C(16,2) \times C(14,1)] = 4368+[16 \times455] +[120 \times 14] = \color{blue}{13,328}$$

Related Question