Counting problem

Printable View

March 16th 2010, 05:56 PM
swtdelicaterose

Counting problem

If Set S = {1,2,3,4}, how many permutations of $\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
${ 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.
March 16th 2010, 06:13 PM
Dinkydoe

I assume you mean permutations of $\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 $\mathcal{P}(S)$ is 16!
March 16th 2010, 06:21 PM
swtdelicaterose

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!