Permutations of the Power Set [duplicate]

If you have 5 Letters (A, B, C, D, E) : these letters can be chosen in 2^5 = 32 different ways (power set 2^n):

1] "none"              "A"                 "B"                 "C"                 "D"                 "E"                 "A & B"             "A & C"             "A & D"            
[10] "A & E"             "B & C"             "B & D"             "B & E"             "C & D"             "C & E"             "D & E"             "A & B & C"         "A & B & D"        
[19] "A & B & E"         "A & C & D"         "A & C & E"         "A & D & E"         "B & C & D"         "B & C & E"         "B & D & E"         "C & D & E"         "A & B & C & D"    
[28] "A & B & C & E"     "A & B & D & E"     "A & C & D & E"     "B & C & D & E"     "A & B & C & D & E"

My Question: Suppose "B & C" was different from "C & B" - that is, if the order was important, how many ways could these 5 letters be ordered now? Is there a formula for this?

Thanks

Solution 1:

You are asking how many "words" we can form using the letters A, B, C, D, E without re-using the letters.

How many words of length one are there? There are five (A, B, C, D, E).

How many words of length two are there? For all of the five choices of the first letter, there are four choices for the second. Therefore we have 5x4=20 words of length two.

How many words of length three are there? For all of the five choices of the first letter, there are four choices for the second letter. For all 5x4 choices of the first two letters, there are three choices for the third letter. So there are 5x4x3=60 words of length three.

How many words of length four are there? For all of the five choices of the first letter, there are four choices for the second letter. For all 5x4 choices of the first two letters, there are three choices for the third letter. For all 5x4x3=60 choices of the first three letters, there are two choices for the fourth letter. So there are 5x4x3x2=120 words of length four.

Now there is only one letter left, so there are 5x4x3x2x1=120 words of length five.

Therefore the total number of words possible is 5+20+60+120+120=325.

To generalize this, you need to know the factorial function $$f:\{0,1,2,\ldots{}\}\to\mathbb{N}\,\,\,\,f(n)=n\cdot{}(n-1)\cdot{}\ldots{}\cdot{}1$$ which we denote by $n!$. We also define $0!=1$. Notice that the solution to your question was $5!/4!+5!/3!+5!/2+5!/1!+5!/0!=5+20+60+120+120=325$.

If you know sigma notation, we can write this as $\sum_{i=0}^4\frac{5!}{i!}$. For $n$ letters, this becomes $\sum_{i=0}^n\frac{n!}{i!}$. Hope this helps.