5
$\begingroup$

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

  • 0
    @EmmadKareem {1,1} is not acceptable.2012-02-29

6 Answers 6

7

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.

  • 0
    Interesting approach to the problem.Good thought.2012-02-29
4

$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.

  • 0
    the order of items doesnt matter, sorry I should have explained better. (so no re-ordering)2012-02-29
3

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$.

  • 0
    Could you explain this in a form for someone without a mathematics background please.2012-02-29
1

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.

  • 0
    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.2013-07-17
1

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 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); 
  • 0
    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.2015-06-12
0

Oh my goodness it’s not actually that complicated. It’s the same as possibilities to a 6 digit code with known numbers and no repeats. With 1 item there are 6 possibilities with 2 you only have 5 choices after the first if you don’t repeat the same item. So for 6 items the equation is as follows 6*5*4*3*2= 720 possible combinations of 6 items. If you can choose to use less of the items in a sequence that changes things. 1 item used = 6 possibilities . 2 items used is 5 possibilities for each item because there are only 5 left to choose from if you have used 1 already so the answer is 5*6= 30. 3 items used is 4 possibilities for the 3rd choice so 4 times 5 possibilities times 6 =120. 4 items used is 3 possibilities for the 4th item and 4 possibilities for the 3rd item and 5 possibilities for the 2nd item and 6 possibilities for the first item so... 3*4*5*6= 360. For the 5th item we have 2 possibilities so 2*3*4*5*6 =720. And for the 6 we only have one choice left after choosing the other 5 so its the same answer because 2*3*4*5*6*1=720 ... what do we do? We add the possibilities! 720+ 720+ 360+ 120+ 30+ 6= 1956 different combinations for 6 items.