# Choose between Combinations & Permutations

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)?

-
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

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.

-
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

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)?

-

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)