Probability of selecting a set of three numbers from S={1,2,3,..,20}

Question

Let S={1,2,3,...,20}. Find the probability of choosing a subset of three numbers from the set S so that no two consecutive numbers are selected in the set. "I am getting problem in forming the required number of sets."

Answer 1

To remove from unanswered queue:

Consider the related problem of counting how many quadruples $(x_1,x_2,x_3,x_4)$ of non-negative integers exist such that $x_1+x_2+x_3+x_4=15$

Count the number of such possible quadruples using stars and bars.

Recognize that there is a bijection between the sets of non-negative integer quadruples adding to $15$ and the three-element subsets of $\{1,2,3,\dots,20\}$ containing no consecutive numbers.

Explicitly the bijection takes a set $\{a,b,c\}$ and maps it to $(a-1,b-a-2,c-b-2,20-c)$ in the one direction, or it takes a quadruple $(x_1,x_2,x_3,x_4)$ and maps it to $\{(x_1+1),(x_2+x_1+3),(x_3+x_2+x_1+5)\}$ in the other direction. You should conform that this truly is a bijection between the sets.

Now, this tells us how many three-element subsets of $\{1,2,3,\dots,20\}$ have the property we want. Taking the ratio then with the total number of three-element subsets of $\{1,2,3,\dots,20\}$ will give us the probability that a uniformly randomly selected three-element subset will have the desired property.

$\dfrac{\binom{18}{3}}{\binom{20}{3}}$

---

In retrospect, after writing this answer I realize the bijection could also instead be formed with the three-element subsets of $\{1,2,3,\dots,18\}$ instead. Let $\{a,b,c\}$ be a three-element subset from $\{1,2,3,\dots,18\}$ with $a<b<c$. Map this to $\{a,b+1,c+2\}$ which will be a three-element subset of $\{1,2,3,\dots,20\}$ with no consecutive numbers.

Answer 2

Count the total ways to select any three numbers from the set of twenty.

Count the ways to select a number, its immediate successor, and any other number that is not the first number's immediate predecessor (to avoid overcounting).   There will be two cases to consider: first select $1$ or first select from $\{2..19\}$

Subtract and divide as appropriate to get the probability.

---

Alternately:

Count ways to select any three numbers from $\{2..19\}$, so you can then subtract one from the least and add one to the greatest to ensure they are not consecutive and come from $\{1..20\}$.

Count the total ways to select any three numbers from the set of twenty.

Divide and answer.

Answer 3

$\underline{Another\; approach}$

For any chosen subset of $3$, there will be $17$ left unchosen, and the three chosen must have come from any $3$ of $18$ gaps (including ends) marked with an uparrow,

$\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\bullet\uparrow\quad$thus $\dfrac{\binom{18}{3}}{\binom{20}{3}}$

Answer 4

Inclusion-Exclusion Principle:-
Suppose $A_i$ denote the event that both the numbers $i,$ and $i+1$ ($i=1,2,...,19$) are included in the set.
$n(\bigcup\limits_{i=1}^{19} A_i)$ will denote the total number of cases where we can find at least two consecutive integers.

Here, $n(\bigcup\limits_{i=1}^{19} A_i)=\sum_{i=1}^{19}n(A_i)-\sum \sum_{i\ne j}n(A_i\cap A_j)$
[Terms like $n(A_i,A_j,A_k)$ and others vanishes]

Now, for an instance if you choose $1,2$ then there are $18$ other choices. So, $n(A_i)=18$, $i=1,2,....19$

$n(A_i\cap A_j)$ just requires how many consecutive tuples like $(1,2,3),(2,3,4)$ you may have. Obviously this number is $18$
So,$n(\bigcup\limits_{i=1}^{19} A_i)=18\times 19 -18=324$

Required probability $=1-\frac{324}{\binom{20}{3}}=\frac{816}{\binom{20}{3}}$