Question

Consider a set of n antennas of which m are defective and n-m are functional and assume that all of the defectives and all of the functionals are considered indistinguishable. How many linear orderings are there in which no two defectives are consecutive?

Answer 1

@ganeshie8 @PaxPolaris @sangya21 @Compassionate @uri

Answer 2

freaky

Answer 3

lol the phrasing is freaky but the problem is simple

Answer 4

its equivalent to below problem :

you have `n` students of which `m` are girls, find the number of possible arrangements such that no two girls are together

Answer 5

if it didn't matter where the defectives go ... the answer would simply be (n choose m)

Answer 6

if m > n/2 ... the answer would be 0

Answer 7

@ganeshie8

Answer 8

i could recursively calculate that for any number of n and m ... but no idea what the general formula would be :(

Answer 9

*correction
if m>(n+1)/2 the answer would be 0.
if m=(n+1)/2 the answer would be 1.

Answer 10

\[\text{if }m=2, \to {n\choose 2}-(n-1)={n-1 \choose 2}\]\[\text{if }m=3, \to {n-2 \choose 3}\text{ for }\]\[\text{if }m=4, \to {n-3 \choose 4}\]


general formula: ((n-m+1) choose m)

Answer 11

what's the simple way to get this ? @ganeshie8

Answer 12

@perl

Answer 13

so basically you have m F's and n-m S's

Answer 14

set { F F F F F , S S S S S }

and you want no two F's together

Answer 15

FSFSFSFSSS , for example

Answer 16

lets use smaller numbers,

{ F F S S SS }

F S F S SSS

so you have this
F S F , that is moving 1 step to the right, how many steps is it moving?

Answer 17

do you see how 'FSF' is moving

F S F S S S
S F S F S S
S S S F S F

Answer 18

this should work \[\rm \binom{n-m+2}{m} (n-m)!\]


Notice, the problem makes sense only when \(\rm m >= \frac{n}{2}+1\)

Answer 19

the answer is:\[\large{n-m+1 \choose m}\]

it has to always be smaller than (n choose m)

Answer 20

yes that looks good as the objects are indistinguishable