15
$\begingroup$

If you are given these options for dinner:

  • Pie
  • Cake
  • Muffin
  • Ice Cream

And you can have any of these options as you like and you can't have more than one of the same item. Then what are all the possible combinations?

For example you can have:

Pie
Pie, Cake
Pie, Cake, Muffin
Pie, Cake, Muffin, Ice Cream
Pie, Ice Cream
Cake, Muffin

etc...

Is there a way to find all possible combinations?

$\endgroup$
  • $\begingroup$ Do you want to list all of the combinations, or do you simply want to know how many there are? $\endgroup$ – Brian M. Scott May 5 '12 at 9:11
  • $\begingroup$ @Brian M. Scott I would like to know the list of all possible combinations not just the number. $\endgroup$ – Sam May 5 '12 at 9:13
  • $\begingroup$ Yes, it is even possible to write a computer program that does it, not the most efficient though ... $\endgroup$ – rtybase Jun 11 '19 at 17:27
  • $\begingroup$ The answers below are good but I always fall back on binary, say XXXX then replacing the X's with {0,1} both enumerates and counts. Then label the positions. $\endgroup$ – rrogers Oct 1 '19 at 21:59
15
$\begingroup$

A set of $4$ elements has $2^4$ subsets. These include the empty set, in which case you eat nothing. So the answer is $16$ if eating nothing is an option, or $15$ if eating nothing is not an option. The wording of the problem does not make it clear whether you can choose the empty set of foods.

The numbers are small enough that you could actually enumerate all the possibilities. You were well under way. To be sure of not missing any, you might proceed systematically. For brevity call the foods A, B, C, D.

We can have

i) nothing;

ii) A or B or C or D;

iii) AB or AC or AD or BC or BD or CD;

iv) BCD or ACD or ABD or ABC;

v) ABCD.

Count: we get $16$.

To see the "formula" $2^4$, imagine you are in a cafeteria line and the A's, B's, C's, and D's are lined up in that order. You look at the A's and say yes or no. Then you do the same with the B's, the C's, the D's. The number of possible choices is the number of strings of length $4$ made up of the letters Y (for Yes) and/or N (for No). There are $2^4$ such strings. The option NNNN corresponds to going hungry.

$\endgroup$
  • $\begingroup$ Eating nothing is not an option. Could you please provide a list of the 15 possible combinations? $\endgroup$ – Sam May 5 '12 at 9:15
  • $\begingroup$ I had already edited to provide a list. If the number of options is say $10$ instead of $4$, then counting would still be easy ($2^{10}$, or $2^{10}-1$ if you do not allow the empty cafeteria tray). But making a complete list would be unpleasant, since $2^{10}=1024$. $\endgroup$ – André Nicolas May 5 '12 at 9:23
2
$\begingroup$

Here you can input your options and get all possible combinations: mathisfun.com

$\endgroup$
  • $\begingroup$ This applet lists the $k$-element subsets of a set. So, in order to get all subsets, one would need to run the program for $k=1,2,\ldots,n$. $\endgroup$ – Douglas S. Stones Oct 15 '12 at 12:24
2
$\begingroup$

Preliminary

  • The subsets of a set $A=A$'s power set $=\mathcal{P}\left(A\right)$.
  • The size of a set $A=A$'s cardinality $=card\left(A\right)$.
  • Let your options be represented by the set $X = \left\{P,C,M,I\right\}$.

This table describes what to do for any basic combinatorics/permutations q...

$$ \begin{array}{l} \begin{array}{c|c} \hskip36.5pt & \hskip42.5pt\style{font-family:inherit}{\text{Ordering}} \end{array} \\[-7pt]\hline\hskip-5.5pt \begin{array}{c|c|c} \style{font-family:inherit}{\text{Repetition}} & \style{font-family:inherit}{\text{w/}} & \style{font-family:inherit}{\text{w/o}} \\\hline \style{font-family:inherit}{\text{w/}} & P_r^n=n^r & C_r^n=\left(\!\left(\begin{smallmatrix} n \\ r \end{smallmatrix}\right)\!\right)=\left(\begin{smallmatrix} n+r-1 \\ r \end{smallmatrix}\right) \\[0pt]\hline \style{font-family:inherit}{\text{w/o}} & nPr=\frac{n!}{(n-r)!} & nCr=\left(\begin{smallmatrix} n \\ r \end{smallmatrix}\right)=\frac{n!}{r!(n-r)!} \end{array}\hskip-5.5pt \end{array} $$

Remark

I will provide my own answer; but first, I will assign some notation to the already accepted answer (which correctly stated that the q could be thought of as the # sequences "(a,b,c,d)" s.t. a,b,c,d $=$ Y/N, i.e., w/ repetition & w/ ordering, subtracted by 1)...

  • $\mathcal{P}\left(X\right) = \left\{\left\{\right\},\left\{P\right\},\left\{C\right\},\left\{M\right\},\left\{I\right\},\left\{P,C\right\},\left\{P,M\right\},\left\{P,I\right\},\left\{C,M\right\},\left\{C,I\right\},\left\{I,M\right\}\left\{P,C,M\right\},\left\{P,C,I\right\},\left\{P,M,I\right\},\left\{C,M,I\right\},\left\{P,C,M,I\right\}\right\}\hskip-2pt\style{font-family:inherit}{\text{.}}$
  • # Combinations w/ empty set $= card\left(\mathcal{P}\left(X\right)\right) = 16$.
  • # Combinations w/o empty set = $card\left(\mathcal{P}\left(X\right)\right) - 1 = 15$.

Answer

Let's consider the q in its intuitive (some would say "raw") form, i.e., 1 about finding the # combinations of options from $X$ w/o repetition or ordering. The table says to use the Binomial Coefficient ($nCr$) but we will have to use it 4 times & + up the results to account for your 4 differently sized subsets...

$$\style{font-family:inherit}{\text{# Combinations}} = 4C1 + 4C2 + 4C3 + 4C4 = \left(\begin{smallmatrix} 4 \\ 1 \end{smallmatrix}\right) + \left(\begin{smallmatrix} 4 \\ 2 \end{smallmatrix}\right) + \left(\begin{smallmatrix} 4 \\ 3 \end{smallmatrix}\right) + \left(\begin{smallmatrix} 4 \\ 4 \end{smallmatrix}\right) = 15$$

$\endgroup$

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