Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Emmad Kareem 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}. –  Emmad Kareem Feb 29 '12 at 11:27
    
Comments working again: @miracle173 you are correct. –  Mark W Feb 29 '12 at 12:29

5 Answers 5

up vote 2 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
1  
...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$.

share|improve this answer
    
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.

share|improve this answer
    
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);
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.