My real-life Problem: Suppose I have $n$ numbered balls increasingly arranged in a row: $1, 2, 3, 4, \dots, (n-1), n$. Here, $n$ is an even integer. Now the goal is to draw a total of $m$ pairs with replacement from these balls, with the restriction that it is not allowed that the pairs $\{1,2\}, \{3,4\}, \dots, \{(n-1),n\}$ occur.

How many possible configurations of my $m$ pairs are there?

My thoughts:

For each pair, there are $\binom{n}{2}$ possibilities to draw balls without any restrictions. There are $n/2$ "bad" pairs, so the number of "good" pairs is $$ \binom{n}{2} - \frac{n}{2} = \frac{n^2}{2} - n. $$

Thus, we have in total $m (\frac{n^2}{2} - n)$ possible configurations for our $m$ pairs.

  • $\begingroup$ I mean I draw $m$ times one pair (at once, without replacement) out of $n$ balls and THEN replace it. $\endgroup$ – NoBackingDown Sep 16 '15 at 13:44
  • $\begingroup$ There are $\left(\frac{n^2}{2}-n\right)^m$ different sequences of draws. $\endgroup$ – André Nicolas Sep 16 '15 at 13:55
  • $\begingroup$ @AndréNicolas Of course you are right and the $m$ goes into the exponent. Embarrassing blunder. Thank's for confirming the result. $\endgroup$ – NoBackingDown Sep 16 '15 at 14:20
  • $\begingroup$ You are welcome. In my comment I wrote sequences of draws, for clarity. That's because I was unsure as to what you meant by configurations. If all we are interested in is which pairs we got (including multiplicity, since we are drawing with replacement) then the answer is quite different. What exactly do you mean by configuration? $\endgroup$ – André Nicolas Sep 16 '15 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.