N working antennas and M defective ones (combinatorics problem)

146 Views Asked by At

PROBLEM

Consider a set of $N$ antennas of which $M$ are defective. How many linear orderings are there in which no two defectives are consecutive?

What I can do think of is: we need to put one defective antenna and then one working antenna and then so on alternating between defecting and working ones. So how many possible ways we can do it?

${n \choose m}$ ?

2

There are 2 best solutions below

0
On

Assuming that the antenna are identical otherwise, let the positions of the defective antennas be $x_1,x_1+x_2,x_1+x_2+x_3,\ldots,x_1+\ldots +x_m$, where $x_1 \geq 1$, $x_i \geq 2$ for $i \geq 2$, and $x_1+\ldots+x_m \leq n$. This is equivalent to the number of solutions to $y_1+y_2+\ldots+y_m \leq n-m+1$ with $y_i \geq 1$. Can you complete it?

4
On

Place all the $N-M$ working antennas in a line. Now there are $N-M+1$ places available for the defective antennas. Therefore, the total ways are$${N-M+1}\choose M$$