A query about a more complex factorial

[Josephsummer777]

I understand Factorials. One can arrange five things (abcde) in 120 ways. However, that formula requires one to use all five things. What is the formula that expands that set of things to include smaller subsets, so that one could arrange the things like so: a,b,c,d,e; but also a,b,c,e? I'm unclear how to calculate the number of combinations of things one can obtain when the sets of things do not require all the things.

 

[Steven G]

The answer is 2^n where n is the number of items.

You can choose 0 items from n or you can choose 1 item from n or 2 items from n or ... or you can choose n items from n. The sum of all these equals 2^n

 

[Dr.Peterson]

I understand Factorials. One can arrange five things (abcde) in 120 ways. However, that formula requires one to use all five things. What is the formula that expands that set of things to include smaller subsets, so that one could arrange the things like so: a,b,c,d,e; but also a,b,c,e? I'm unclear how to calculate the number of combinations of things one can obtain when the sets of things do not require all the things.

To be clear, are you asking about permutations (arranging), or combinations (choosing)? Jomo's answer is about combinations, where you are just selecting a subset of the five items. If you are also arranging them (partial permutations), it gets more complicated. I think the best formula is simply the sum of the number of permutations of each possible size.

 

[pka]

I understand Factorials. One can arrange five things (abcde) in 120 ways. However, that formula requires one to use all five things. What is the formula that expands that set of things to include smaller subsets, so that one could arrange the things like so: a,b,c,d,e; but also a,b,c,e? I'm unclear how to calculate the number of combinations of things one can obtain when the sets of things do not require all the things.

Here is an example. A club of twenty members has officers, a chairman, vice-chair, treasurer and whip. How many ways can the offices be filled?
That calls for a permutation: \(\mathcal{P}_4^{20}=\dfrac{20}{(20-4)!}=116280\) ways.
The notation \(\mathcal{P}_j^{N}=\dfrac{N!}{(N-j)!}\) SEE HERE.

 

[Josephsummer777]

The answer is 2^n where n is the number of items.

You can choose 0 items from n or you can choose 1 item from n or 2 items from n or ... or you can choose n items from n. The sum of all these equals 2^n

I think that doesn't answer my query, perhaps because I didn't state it clearly. I want to know how many different ways one can order abcde, including the obvious 120 using all five, but then less than all five.

To be clear, are you asking about permutations (arranging), or combinations (choosing)? Jomo's answer is about combinations, where you are just selecting a subset of the five items. If you are also arranging them (partial permutations), it gets more complicated. I think the best formula is simply the sum of the number of permutations of each possible size.

So, would that be 5! + 4! + 3! +2! + 1? Somehow, I am not seeing that as the answer. Yes, all combinations and permutations.

 

[Josephsummer777]

Here is an example. A club of twenty members has officers, a chairman, vice-chair, treasurer and whip. How many ways can the offices be filled?
That calls for a permutation: \(\mathcal{P}_4^{20}=\dfrac{20}{(20-4)!}=116280\) ways.
The notation \(\mathcal{P}_j^{N}=\dfrac{N!}{(N-j)!}\) SEE HERE.

I think I understand your reply, but that's not my question. I'm looking at finding the number of all possible combinations and permutations of a,b,c,d,e. Examples include the ordered set [a,then b, then c, then d, then e;] the ordered set [a, then c, then b, then d, then e;], the ordered set [c. then b, then e;] the ordered set [d;] etcetera. i don't think the answer is 5! + 4! + 3! + 2! + 1; but I can't place my finger on what the formula would be.

 

[Dr.Peterson]

So, would that be 5! + 4! + 3! +2! + 1? Somehow, I am not seeing that as the answer. Yes, all combinations and permutations.

A better way to say it would be, "all permutations of any number of elements in the set". You can't really consider a permutation to be a combination.

I think I understand your reply, but that's not my question. I'm looking at finding the number of all possible combinations and permutations of a,b,c,d,e. Examples include the ordered set [a,then b, then c, then d, then e;] the ordered set [a, then c, then b, then d, then e;], the ordered set [c. then b, then e;] the ordered set [d;] etcetera. i don't think the answer is 5! + 4! + 3! + 2! + 1; but I can't place my finger on what the formula would be.

If you understand pka, then you can insert that into my answer, which does pertain to what you are asking.

You want the sum of 5P0 + 5P1 + ..., where each term nPk is the number of ways to permute some number k of items from the n items in a set. You are using the factorial, which is k! = kPk, that is, the number of ways to permute all k items in a set.

 

[Cubist]

You want the sum of 5P0 + 5P1 + ...,

There's an interesting approximation to this sum: e * n!

It works because 5!/0! + 5!/1! + 5!/2! ... = 5! * (1/0! + 1/1! + 1/2! + ...) ≈ 5! * e

(The reciprocals of the factorials sum to the transcendental number e)

Here's the comparison for the first few n...
n, actual result, approximation to a few dp (rounded down)
2 5 5.4365
3 16 16.3096
4 65 65.2387
5 326 326.1938
6 1957 1957.1629
7 13700 13700.1404
8 109601 109601.1233
9 986410 986410.1099

It looks like the approximation can be made exact by taking floor( e * n! )

 

[Josephsummer777]

I'm afraid that I am phrasing the question poorly. Solving by brute force, I know that there are 64 possible arrangements of the set of [a, b, c, d]. There's abcd, abdc, acbd, adbc, adcb; abc, abd, acb, acd, adb, adc; ab, ac, ad; and a. repeat with b, then c, then d. 16 x 4 = 64. 65 if one includes null. (For the set of ABC, there are 15 possible arrangement, not including the null.) So, I'm still unclear on what the formula would be for the set of [a,b,c,d,e] nor do I know how to extrapolate for further sets.

 

[Dr.Peterson]

I do know what you want, and I came very close to giving you the exact formula, but I guess you missed it: for permutations of all subsets of {a, b, c, d}, we have n=4 and the formula is

[MATH]_4P_0 + _4P_1 + _4P_2 + _4P_3 + _4P_4 = 1 + 4 + (4\times 3) + (4\times 3\times 2) + (4\times 3\times 2\times 1) = 1 + 4 + 12 + 24 + 24 = 65[/MATH]​

where I included the empty set (as mathematicians are prone to do ...). So remove the first term to get what you want, excluding it.

For n=3, and excluding the empty permutation, it's

[MATH]_3P_1 + _3P_2 + _3P_3 = 3 + (3\times 2) + (3\times 2\times 1) = 3 + 6 + 6 = 15[/MATH]​

We could simplify these a little, in the sense of needing fewer multiplications, which gives nice, though not closed, "formula":

For n=4: [MATH]4(1+3(1+2(1+1))) = 4(1+3(1+4)) = 4(1+15) = 64[/MATH]​

Does that fit your need?

For alternative descriptions of this concept (including the empty sequence), see http://oeis.org/A000522. That confirms my expectation that there is no simple integer formula, but also confirms Cubist's formula: for n > 0, a(n) = floor(e*n!)

 

[Josephsummer777]

I do know what you want, and I came very close to giving you the exact formula, but I guess you missed it: for permutations of all subsets of {a, b, c, d}, we have n=4 and the formula is

[MATH]_4P_0 + _4P_1 + _4P_2 + _4P_3 + _4P_4 = 1 + 4 + (4\times 3) + (4\times 3\times 2) + (4\times 3\times 2\times 1) = 1 + 4 + 12 + 24 + 24 = 65[/MATH]​

where I included the empty set (as mathematicians are prone to do ...). So remove the first term to get what you want, excluding it.

For n=3, and excluding the empty permutation, it's

[MATH]_3P_1 + _3P_2 + _3P_3 = 3 + (3\times 2) + (3\times 2\times 1) = 3 + 6 + 6 = 15[/MATH]​

We could simplify these a little, in the sense of needing fewer multiplications, which gives nice, though not closed, "formula":

For n=4: [MATH]4(1+3(1+2(1+1))) = 4(1+3(1+4)) = 4(1+15) = 64[/MATH]​

Does that fit your need?

For alternative descriptions of this concept (including the empty sequence), see http://oeis.org/A000522. That confirms my expectation that there is no simple integer formula, but also confirms Cubist's formula: for n > 0, a(n) = floor(e*n!)

AH! Thank you for spelling that out for me. I ‘m a musician, not a mathematician, so I ‘ve only really needed to count to 12 most of my life. (A little facetious, as I studied Acoustics, and taught musical acoustics, but still, the math is fairly simple, even when figuring out frequencies and pitches.) That is the formula that I wasn’t Comprehending in your prior answer. My apologies for my thickheadedness.