Permutations on a set with certain conditions.

Question

Suppose we have a set $S=\{1,2,3,x,y\}$. There are $5!$ ways to rearrange the elements in the set, but I am confused about how to find the number of ways to rearrange the set given that $3$ comes before $2$ which comes before $1$ (or something like that). For instance, we could write

$$\{3,2,1,x,y\}\\ \{3,2,x,1,y\}\\ \{3,2,x,y,1\} \ \text{etc}...$$

It is easy to do by a brute force method, consisting of writing down all the possible sets, but is there a short, mathematical, way to do so?

There are $\binom{5}{3}$ ways to determine the set of places where the numbers will go. Once we have done that their position is determined. There are then $2!$ ways to arrange $x$ and $y$ in the leftover spots, for a total of $\binom{5}{3}2!$. — André Nicolas, Mar 16 '15 at 05:29
Seems so obvious after I read your answer @AndréNicolas, thank you! — FinneganJ, Mar 16 '15 at 05:34

score 3 · Answer 1 · answered Mar 16 '15 at 05:31

Given the condition that 3 comes before 2 which comes before 1, out of those $5!$ arrangements, the arrangements of $\{1,2,3\}$ within themselves have to be according to the condition.

So, out of the $3!$ possibilities of $\{1,2,3\}$ arranging within themselves, the only one that satisfies the given condition is $\{3,2,1\}$, that is one out of $3!$.

Hence, total number of arrangements is $\frac{5!}{3!}$.

score 2 · Answer 2 · answered Mar 16 '15 at 05:39

To make things clearer and simpler, start by considering $\{1,2,3,4,5\}$ as a starting set

Also notice that you can just as well count permutations with $ 1' < 2' < 3'$ (I hope the notation is intuitive enough).

Then just count how many positions are valid for $1,2,3$, leaving $4,5$ aside. You can "count on your fingers" or see that there is some inductive formula to count this. You should get $10$.

Then for every valid positioning of $1,2,3$, you have $2!=2$ ways of positioning $4,5$.

So in your example, answer should be $20$.

Permutations on a set with certain conditions.

2 Answers2