9
$\begingroup$

I am a newbie in combinatorics and still don't have enough tools to handle this kind of problems.

Assuming I have a set of integers: $ \{1,2,3,4,\dots,n\} $

In how many ways, can I choose $k$ numbers out of those $n$, such that none of them are consecutive?

For instance, for the following set $ \{1,2,3,4,5\} $

For $ k=3 $ I have only 1 option: $\{1,3,5\}$

My purpose is first of all to understand the way you would think about this problem, not necessarily the solution itself (I have the final answer for it).

Thanks.

$\endgroup$
9
$\begingroup$

Place $n - k$ blue balls in a row, leaving gaps between them. We now have $n - k - 1$ spaces between successive blue balls and the two spaces at the ends of the row for a total of $n - k + 1$ spaces in which to place $k$ green balls. We choose $k$ of these $n - k + 1$ spaces for the green balls. We now number the balls from left to right. The numbers on the green balls are the desired set of non-consecutive integers. Hence, the number of ways of selecting $k$ integers from the set $\{1, 2, 3, \ldots, n\}$ so that no two of them are consecutive is $$\binom{n - k + 1}{k}$$

To illustrate the idea, let $n = 10$ and $k = 4$. We start with $n - k = 6$ blue balls.

$$\color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}$$

We choose four of the seven available spaces in which to place a green ball.

$$\color{green}{\bullet}\color{blue}{\bullet}\color{green}{\bullet} \color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{blue}{\bullet}$$

If we number the balls from left to right, we see that this particular selection corresponds to the subset $\{1, 3, 6, 9\}$.

$\endgroup$
3
  • $\begingroup$ Very nice approach (+1) $\endgroup$
    – drhab
    Mar 26 '16 at 9:42
  • $\begingroup$ Thanks. I wonder, how did you think about placing n-k balls at the first place? is this some kind of pattern you often use? $\endgroup$ Mar 26 '16 at 10:02
  • 1
    $\begingroup$ Yes, but the key idea is using gaps. When we wish to count arrangements in which objects are non-consecutive, it is useful to create gaps in which to place them. If we wish to count arrangements of four men and four women in which no two of the men sit in consecutive seats, we first line up the four women in one of $4!$ ways, which leaves five spaces for the four men (three between successive women and two at the ends of the row). We place the men in those gaps in $5 \cdot 4 \cdot 3 \cdot 2$ ways, giving $4! \cdot 5 \cdot 4 \cdot 3 \cdot 2 = 4!5!$ possible arrangements. $\endgroup$ Mar 26 '16 at 10:11
7
$\begingroup$

Denote the # of ways to choose $k$ non-consecutive numbers from $\{1, 2, \cdots, n\}$ as $C_{n, k}$. There are two cases.

  • $n$ is chosen. In this case, you have to choose $k - 1$ non-consecutive numbers from $\{1, 2, \cdots, n - 2\}$, i.e, $C_{n - 2, k - 1}$.

  • $n$ is not chosen. In this case, you have to choose $k$ non-consecutive numbers from $\{1, 2, \cdots, n -1 \}$, i.e., $C_{n-1, k}$.

In other words, $C_{n, k} = C_{n-2,k-1} + C_{n-1,k}$.

$\endgroup$
1
  • $\begingroup$ Sorry for my ignorance, but how can you evalute each of those C's ? $\endgroup$ Mar 26 '16 at 10:08
0
$\begingroup$

Start with $k$ sticks (representing the numbers chosen) and $n-k$ dots (representing the other numbers),

and remove $k-1$ dots (which will be our "blockers").

This leaves $k$ sticks and $n-2k+1$ dots, which can be arranged in $\color{blue}{\dbinom{n-k+1}{k}}$ ways;

and then we can insert the $k-1$ blockers between the sticks to make sure they are not consecutive.

$\endgroup$

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.