-
Counting problem
If Set S = {1,2,3,4}, how many permutations of $\displaystyle \mathcal{P}{(S)}$ are there so that no subset is ever followed by a subset of smaller size?
So this is what I did:
Possible sizes are 0, 1, 2, 3, 4
$\displaystyle { 4 \choose 0 },{ 4 \choose 1 },{ 4 \choose 2 },{ 4 \choose 3 },{ 4 \choose 4 }$
which is 1, 4, 6, 4, 1, respectively
So I choose smallest first, which is still in respective order, so:
I did 1! * 4! * 6! * 4! * 1! which came out to be 414720
However, I doubt this is right. Anyone know if I did anything wrong?
Thanks.
-
I assume you mean permutations of $\displaystyle \mathcal{P}(S)$ (the set of all subsets of S)
What you did was indeed correct. Not very surprising, considering the total amount of permutations of $\displaystyle \mathcal{P}(S)$ is 16!
-
Yeah whoops that's what I meant. I wasn't sure if this was correct because it seemed too easy for an assignment question. Anyways, thanks for the help!