I have the following exercise. Assume you have 5 cars of brand A, 6 cars of brand B and 5 cars of brand M. Each car is considered unique i.e no repetitions.

How many ways can I arrange the cars where there are at least two cars brand M in a row.

I started to evaluate the problem in the following way. As we have 5 cars brand M, and the restriction is at least 2, it means that the complement would be never two cars or more in a row. From there I calculated that scenario which was:

$$\frac{11!}{(6!*5!)} * \frac{12!}{(12-5)!*5!}$$

Then I subtracted the result from the total of options which would be 16!.

Is that correct??

  • $\begingroup$ Welcome to MSE. Please edit and use MathJax to properly format math expressions. $\endgroup$ – Lee David Chung Lin Aug 15 at 16:59
  • $\begingroup$ Welcome to MathSE. It would help readers of your question if you explained how you arrived at your answer since that makes it easier to detect any errors you may have made. $\endgroup$ – N. F. Taussig Aug 15 at 17:53

Your strategy is correct, but you forgot to account for the fact that each car is unique.

There are $16!$ ways to arrange the cars. We must subtract those arrangements in which no two brand M cars are adjacent. We can line up the other eleven cards in $11!$ ways, creating twelve spaces in which to place the brand M cars, ten between successive cars and two at the ends of the row. $$\square c \square c \square c \square c \square c \square c \square c \square c \square c \square c \square c \square$$ To ensure that we separate the brand M cars, we must choose five of these twelve spaces in which to place a brand M car. The five brand M cars can be arranged in the selected spaces in $5!$ ways. Hence, the number of arrangements in which no two brand M cars are adjacent is $$11!\binom{12}{5}5!$$ Hence, the number of arrangements of the sixteen cars in which at least two of the brand M cars are adjacent is $$16! - 11!\binom{12}{5}5!$$ Had you multiplied your count of the arrangements in which no two brand M cards are adjacent by the $5!$ ways of arranging the brand A cars, $6!$ ways of arranging the brand B cars, and $5!$ ways of arranging the brand M cars, you would have obtained the correct answer. Observe that $$\frac{11!}{5!6!} \cdot \frac{12!}{5!7!} \cdot \color{red}{5!6!5!} = 11!\binom{12}{5}5!$$


You have the correct approach (enumerate the complement and subtract), but the wrong working. I will go through finding the number of arrangements with no two adjacent brand-M cars more carefully.

There are $6$ spaces between and around the $5$ cars of brand M: $$\square M\blacksquare M\blacksquare M\blacksquare M\blacksquare M\square$$ In the $4$ middle spaces, there must be at least one of the $11$ other cars; the end spaces do not have this restriction. Thus, ignoring the distinction between same-brand cars for the moment, we need to place $7$ cars in $6$ spaces with possibly $0$ cars in a space. By stars and bars the number of ways to do this is $$\binom{7+6-1}7=\binom{12}7$$ Given an arrangement of the brands, we can permute the individual cars in $5!11!$ ways. Thus there are $\binom{12}75!11!$ inadmissible arrangements where no two brand-M cars are adjacent.

  • $\begingroup$ Hi Parcly, thank you so much for your reply. I just get a little confused in this section: we need to place 7 cars in 6 spaces with possibly 0 cars in a space. Why did you use 7 cars?? I mean, the cars of brand A are 5 and brand B are 6, so i think it would be 11 cars, isn't it?? Sorry if it is a naive question. $\endgroup$ – ManuelVillamil Aug 15 at 17:10
  • $\begingroup$ @ManuelVillamil We ignore the five M brand cars and four cars that must be placed to separate the M cars. This leaves $7$. $\endgroup$ – Parcly Taxel Aug 15 at 17:12
  • $\begingroup$ @N.F.Taussig Corrected. Please remove your comment. $\endgroup$ – Parcly Taxel Aug 15 at 23:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.