Take the 2-minute tour ×

What is the most natural way to choose either permutations or combinations when encountering a particular combinatorial problem?

For example, in the following problem:

Given $n$ antennas of which $m$ are defective and $n-m$ are functional, how many linear 'orderings' are there in which no two defectives are consecutive?

What seems to be the natural way of doing this (P or C)?

share|improve this question
Apart from defective and functional, do you have any way to distinguish the antennas? –  Fabian Apr 6 '11 at 5:55
all the functional & all the defective are considered indistinguishable. (That's what book (Sheldon Ross') says.) –  Amit L Apr 6 '11 at 5:58
Does this help you? What do you know about Combinations & Permutations? The question is a bit misleading. There is not a natural ay of doing this. There is only a correct and a wrong way of doing this. Combinations and permutations are two ways of counting. –  Fabian Apr 6 '11 at 6:01
when I saw 'orderings'(arrangements instead of just group/combinations of participating objects) in the book, I started doing it by permutations which's wrong way of doing it as the book says. At least could someone solve the problem for me so that I can have a view of how that someone does it? –  Amit L Apr 6 '11 at 6:05
add comment

4 Answers

up vote 4 down vote accepted

The puzzlement is understandable. You want to count sequences, which brings permutations to mind. However, the most efficient way to solve this particular problem will use "combinations."

Put the $n-m$ working antennas in a row, leaving nice big gaps between them. If we want the bad antennas to be never next to each other, where can a bad antenna go? Into one of the gaps, or at either end. So there are $n-m+1$ potential places for bad antennas. We have to CHOOSE $m$ of these places. The number of ways to do this is $$\binom{n-m+1}{m}$$ (If $m$ is larger than $n-m+1$, then the job cannot be done at all. We can consider that the answer is still given by the above formula, if we define $\binom{x}{y}$ to be $0$ if $y>x$. Or else we can make the explicit restriction $m \le n-m+1$.)

It is (sadly) all too easy for a plausible sounding argument to be not correct. So one might check whether the above formula gives the right answer in "small" cases where one can count explicitly. And in addition one might see what happens for something like $n=10$, $m=3$, where you can take $7$ pennies, lay them out in a row, and try to think about where one can put $3$ dimes, so that no $2$ dimes are next to each other.

share|improve this answer
well. And when we put m defective ones in those (n-m+1) places, we're not bothered about different possible arrangements of them among themselves, are we? –  Amit L Apr 6 '11 at 17:48
@Amit L: That's right, because we are assuming that good antennas are indistinguishable, as are the bad ones. If instead of antennas we have people, $m$ men and $n-m$ women, the reasonable thing would be to multiply the above answer by $m!(n-m)!$. –  André Nicolas Apr 6 '11 at 18:01
Considering some distinguishing characteristics possible, above multiplication by m!(n-m)! is to enumerate all possible 'orderings' among defective (m) & functional(n-m) ones, since we've a way to distinguish them & hence we can 'order' them. –  Amit L Apr 6 '11 at 19:01
add comment

Combinations and permutations are different ways of counting. As hinted in my comment: for combinations you consider the object as indistinguishable, in the case of permutations distinguishable.

Hint: if you select $k$ objects from $n$ know that the answer can only be combination or permutation the following might help

  • if you select $k=n$ objects, do you have 1 possibility (combination) or $n!$ possibilities (permutation)?

  • is it the same to select $k$ or $n-k$ objects (combination)?

share|improve this answer
add comment

You can answer your own question if you take small numbers.

For example, suppose there are three antennae of which two are defective and one functional. Do you think:

  1. There are three possible patterns: $DDF$, $DFD$, and $FDD$, of which $DFD$ is the only one with no two defectives consecutive. (combinations)
  2. There are six possible patterns: $D_1 D_2 F$, $D_1 F D_2$, $F D_1 D_2$, $D_2 D_1 F$, $D_2 F D_1$, and $F D_2 D_1$, of which $D_1 F D_2$ and $D_2 F D_1$ are the only two with no two defectives consecutive. (permutations)
share|improve this answer
add comment

To get an idea, start by doing some small examples and try to see a pattern. Even if you know what combinations and permutations are, this example might still be tricky to solve. If you totally give up, I can give you the solution. However, these kind of problems are meant to think about for some time until you get the hang out of it. You won't just "see it", unless you have gotten some practice. So take your time.

share|improve this answer
add comment

Your Answer


