# Arrangement of things using inclusion-exclusion principle

How many ways are there to arrange 4 pairs of shoes in a row so that 2 shoes of the same pair are never next to each other?

I started by making a visual representation of the 8 shoes in a row in pairs,

shoes -> II II II II

Since there 4 pairs, I considered 4 conditions

$C_i$ = pair of shoes are never together (1 ≤ i ≤ 4)

N($\bar{C_1}\bar{C_2}\bar{C_3}\bar{C_4})$ = $S_0 - S_1 + S_3 - S_4$

$S_0$ = All possible arrangements = $\frac{8!}{(2!)^4}$ since there are 8 shoes, and 4 pairs are identical.

$S_1$ = One pair of shoes is identical = $4 \choose 1$$\frac{7!}{(2!)^3} Assuming, 2 shoes to be one pair, we are left with 7 shoes, and there's only 3 identical pairs left now Following a similar pattern, S_2 = 4 \choose 2$$\frac{6!}{(2!)^2}$

$S_3$ = $4 \choose 3$$\frac{5!}{(2!)} S_4 = 4 \choose 4$${4!}$

$N(\bar{C_1}\bar{C_2}\bar{C_3}\bar{C_4})$ = $\frac{8!}{(2!)^4}$ - $4 \choose 1$$\frac{7!}{(2!)^3} + 4 \choose 2$$\frac{6!}{(2!)^2}$ - $4 \choose 3$$\frac{5!}{(2!)} + 4 \choose 4$${4!}$

I'm not sure if what I did is correct, any suggestions would be appreciated.

• The left and right shoes in a pair are distinguishable. – N. F. Taussig Jan 19 '17 at 0:22
• I suppose you can find a few posts about this problem on this site, it is often formulated using married couples. For example, a question about four couples and a question about three couples. – Martin Sleziak Jan 19 '17 at 3:42
• BTW if the main point of your question is to ask for checking and criticism of your solution (as opposed to asking for any solution from others), you should add the tag (solution-verification) to indicate this. See the tag-info for more details. – Martin Sleziak Jan 19 '17 at 3:44