3
$\begingroup$

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

  • 0
    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?2011-04-06

4 Answers 4

6

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.

  • 0
    Hey, I still don't understand why we use (n-m+1). Can this be explained more?2017-05-18
4

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

2

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

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.