Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
If you are given these options for dinner:
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?
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.
Preliminary
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)...
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$$
Here you can input your options and get all possible combinations: mathisfun.com
Assumptions and Question: 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?
Final Answer(s):
All four possible scenarios are below with their formulas. Since one requirement was that we "can't have more than one of the same item", then the two scenarios (of four possible below) where "items cannot repeat" is a valid answer. You do not have a requirement for having order matter.
So the final answer is either 15 or 64. Both are correct. Some people's stomachs don't agree with ice cream in the wrong order, and might cause acid reflux. :)
Key:
A = Pie
B = Cake
C = Muffin
D = Ice Cream
Unique combinations (order does not matter; items cannot repeat):
unique combinations with 1 item
4
unique combinations with 2 items
6
unique combinations with 3 items
4
unique combinations with 4 items
1
Formula:
Reference: https://en.wikipedia.org/wiki/Permutation
n! / ((n-k)!k!)
4! / ((4-1)!1!)
4! / (3!1!)
24 / 6
4
4! / ((4-2)!2!)
4! / (2!2!)
24 / 4
6
4! / ((4-3)!3!)
4! / (1!3!)
24 / 6
4
4! / ((4-4)!4!)
4! / (0!4!)
4! / 4!
1
Here is the enumeration:
1 item in list = 4
A, B, C, D
(1A, 1B, 1C, 1D)
2 items in list = 6
AB, AC, AD, BC, BD, CD
(3A, 2B, 1C, 0D)
3 items in list = 4
(3A, 1B)
ABC, ABD, ACD, BCD
4 items in list = 1
(4A, 0B, 0C, 0D)
ABCD
ANSWER:
15 unique combinations (order does not matter; items cannot repeat)
Unique combinations (order does matter; items cannot repeat):
unique combinations with 1 item
4
unique combinations with 2 items
4 * 3 = 12
unique combinations with 3 items
4 * 3 * 2 = 24
unique combinations with 4 items
4 * 3 * 2 * 1 = 24
Formula:
n! / (n-k)!
4! / (4-1)!
4! / 3!
24 / 6
4
4! / (4-2)!
4! / 2!
24 / 2
12
4! / (4-3)!
4! / 1!
24 / 1
24
4! / (4-4)!
4! / 0!
24
Here is the enumeration:
1 item in list = 4
A, B, C, D
1A, 1B, 1C, 1D
2 items in list = 12
AB, BA, AC, CA, AD, DA, BC, CB, BD, DB, CD, DC
3A, 3B, 3C, 3D
3 items in list = 24
DAB, DBA, DAC, DCA, CAD, CDA, ABC, ACB, ABD, ADB, ACD, ADC, BAD, CBA, BCA, BDA, CAB, BCD, BAC, BDC, CBD, CDB, DBA, DBC
6A, 6B, 6C, 6D
4 items in list = 24
CDAB, CDBA, BDAC, BDCA, BCAD, BCDA, DABC, DACB, CABD, CADB, BACD, BADC, CBAD, DCBA, DBCA, CBDA, DCAB, ABCD, DBAC, ABDC, ACBD, ACDB, CDBA, ADBC
6A, 6B, 6C, 6D
ANSWER:
64 unique combinations (order does matter; items cannot repeat)
Unique combinations (order does matter; items repeat)
combinations with 1 item
4
combinations with 2 items
4^2 = 4*4 = 16
combinations with 3 items
4^3 = 4*4*4 = 64
combinations with 4 items
4^4 = 4*4*4*4 = 256
ANSWER:
340 unique combinations (order does matter; items repeat)
Unique combinations (order does not matter; items repeat):
combinations with 1 item
4
combinations with 2 items
10
combinations with 3 items
20
combinations with 4 items
35
Formula:
(k + n - 1)! / k!(n - 1)!
(1 + 4 - 1)! / 1!(4 - 1)!
4! / 1!(3!)
24 / 6
4
(2 + 4 - 1)! / 2!(4 - 1)!
5! / 2!3!
120 / 12
10
(3 + 4 - 1)! / 3!(4 - 1)!
6! / 3!3!
6! / 36
20
(4 + 4 - 1)! / 4!(4 - 1)!
7! / 4!3!
5040 / 24*6
35
Enumerations:
1 item in list = 4
A, B, C, D
2 items in list = 10
AA, AB, AC, AD, BB, BC, BD, CC, CD, DD
3 items in list = 20
AAA, AAB, AAC, AAD, ABB, ABC, ABD, ACC, ACD, ADD, BBB, BBC, BBD, BCC, BCD, BDD, CCC, CCD, CDD, DDD
4 items in list = 35
AAAA, AAAB, AAAC, AAAD, AABB, AABC, AABD, AACC, AACD, AADD, ABBB, ABBC, ABBD, ABCC, ABCD, ABDD, ACCC, ACCD, ACDD, ADDD, BBBB, BBBC, BBBD, BBCC, BBCD, BBDD, BCCC, BCCD, BCDD, BDDD, CCCC, CCCD, CCDD, CDDD, DDDD
ANSWER:
> 69 unique combinations (order does not matter; items repeat)
