# How many combinations of 6 items are possible?

I have 6 items and want to know how many combinations are possible in sets of any amount. (no duplicates)

e.g. It's possible to have any of the following:
1,2,3,4,5,6
1,3,5,6,2
1
1,3,4

there cannot be duplicate combinations:
1,2,3,4
4,3,2,1

Edit: for some reason I cannot add more comments. @miracle173 is correct. Also {1,1} is not acceptable

-
Be aware of the case when the set of numbers contains the numbers 0,1,2,3,4,5 then 012 will be numerically equal to 12. – NoChance Feb 29 '12 at 9:40
there are no zeros. it is "six items" – Mark W Feb 29 '12 at 10:12
Do you want to know the number of all subsets (except the empty one)? If there are 3 items 1,2,3 wich 'combinations' dou you want? The following 7 ? {1} {2} {3} {1,2} {1,3} {2,3}{1,2,3} – miracle173 Feb 29 '12 at 10:51
To make your question complete, please identify whether the following is acceptable or not {1,1}. – NoChance Feb 29 '12 at 11:27
Comments working again: @miracle173 you are correct. – Mark W Feb 29 '12 at 12:29

Your are asking the number of subsets of a set with n elements.{1,2,3,...,n} Each subset can be represented by a binary string, e.g for the set {1,2,3,4,5,6} the string 001101 means the subset that

does not contain the element 1 of the set, because the 1st left character of the string is 0

does not contain the element 2 of the set, because the 2nd left character of the string is 0

does contain the element 3 of the set, because the 3rd left character of the string is 1

does contain the element 4 of the set, because the 4th left character of the string is 1

does not contain the element 5 of the set, because the 5th left character of the string is 0

does contain the element 6 of the set, because the 6th left character of the string is 1

so 001101 means the subset {3,4,6}. Therefore there asre as many subsets as strings of length n. With n binary digits one can count from 0 to 2^n-1, therefore there are 2^n such strings and 2^n subsets of {1,....,n}. 00...0 means the empty subset. if you dont want count the empty subset then you have only 2^n-1 subsets.

-
marked as answer as it provides the clearest novice friendly explaination – Mark W Feb 29 '12 at 13:54
Interesting approach to the problem.Good thought. – João Feb 29 '12 at 23:29

$2^6$. Think of it like a garden of forking paths where at the first fork you have to decide whether or not to include 1, then 2, then 3... With each choice the number of possibilities doubles.

-
...though remember that this includes the empty subset – Henry Feb 29 '12 at 9:35
Also, it is not clear whether the OP wants to count reordered sequences. The use of sets hints at no, but the second example given is (on purpose?) not increasing. – Ansgar Esztermann Feb 29 '12 at 9:57
the order of items doesnt matter, sorry I should have explained better. (so no re-ordering) – Mark W Feb 29 '12 at 10:14

My thought was:

Each combination of $k$ elements $n$ by $n$ can be express by $^kC_{n}$.As I understood you want to make sets of $1,2,3,4,5$ and $6$ elements from a sample of $6$ elements without reapeting.So there is a line in pascal's triangle where $k=6$ and $n \in \{ 1,2,3,4,5,6\}$, I'll not include the $0$.

Then we'll get:

$^6C_{1}+^6C_{2}+^6C_{3}+^6C_{4}+^6C_{5}+^6C_{6}=2^6-1$

The minus $1$ is because the $^6C_{0}$ is not inclued. I thing is that.

Explain:

Each combination refers to each set. A set of $1$ element, a set of $2$ elements...and so on.The $^6C_{0}$ it's not valid for this particular problem, because the problem don't allow the empty set. For any line of the Pascal's triangle the sum of all elements of this line is given by $2^n$, where $n$ is the number's line.So if the $^6C_{0}$ is not inclued the solution is given by $2^n-1$, where in this case $n=6$.

-
Could you explain this in a form for someone without a mathematics background please. – Mark W Feb 29 '12 at 12:28

You have 6 numbers, so the answer is 2^6, which is 64. If the empty set doesn't count as a combination, then it's 63.

-
This answer does not provide any new insight beyond the ones which already existed, explain anything more, or really do anything useful, just bumps a rather old question to the top... If you want to help, answer an unanswered question, or one where you can add what others may have missed. – tomasz Jul 17 '13 at 2:42

The actual values are:

number of items in set : total combinations
1 : 1
2 : 4
3 : 15
4 : 64
5 : 325
6 : 1956
7 : 13699
8 : 109,600
9 : 986,409
10 :                   9,864,100   million
11 :                 108,505,111
12 :               1,302,061,344   billion
13 :              16,926,797,485
14 :             236,975,164,804
15 :           3,554,627,472,075   trillion
16 :          56,874,039,553,216
17 :         966,858,672,404,689
18 :      17,403,456,103,284,420   quadrillion
19 :     330,665,665,962,404,000
20 :   6,613,313,319,248,079,000   quintillion
21 : 138,879,579,704,209,650,000   sextillion
22 : 3.0553507534926124e+21        zillion


I know this isn't the programming stack, but i figure some smarty-pants might be able to come up with a (real mathematical) formula based on the script and/or derived values?

The validation was derived from a permutation script (javascript below).

UPDATE: After staring at the results I found a relationship:

nr = (pr * ni) + ni

where:
pr = previous result
nr = next result
ni = next item


So I wrote a little baby script to test the "formula". (That's where the mega-big numbers came from, there's no way a home computer could permutate a zillion!)

var combos = 0;
for(var items=1; items<100; items++){
combos = (combos * items) + items;
console.log(items, combos);
}


Javascript permutation script

function combinations (Asource){

var combos = [];
var temp = [];

var picker = function (arr, temp_string, collect) {
if (temp_string.length) {
collect.push(temp_string);
}

for (var i=0; i<arr.length; i++) {
var arrcopy = arr.slice(0, arr.length);
var elem = arrcopy.splice(i, 1);

if (arrcopy.length > 0) {
picker(arrcopy, temp_string.concat(elem), collect);
} else {
collect.push(temp_string.concat(elem));
}
}
}

picker(Asource, temp, combos);

return combos;

}

var combos = ["a", "b", "c", "d"]; // 5 in this set
var findCombos = combinations (Asource);

console.log(combos.length + " : " + findCombos.length);

-
If you have one element total, you can either have an empty set or a set with that element meaning 2 options. The first line is wrong. If you have 3 elements, you can have all the items, none of the items, 3 ways for one item or 3 ways for 2 items which is 8 combinations. The third line is wrong. Your answer is wrong. – user121330 Jun 12 '15 at 21:20