One more combinatorics question

  • Context: High School 
  • Thread starter Thread starter sk381
  • Start date Start date
  • Tags Tags
    Combinatorics
Click For Summary

Discussion Overview

The discussion centers around the combinatorial problem of determining the number of ways to choose toppings for a pizza from a set of 9 different toppings. Participants explore the concept of subsets and combinations, addressing whether the total number of combinations is correctly calculated as 2^9 or if other considerations apply.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • One participant states that with 9 different toppings, the number of ways to choose toppings is 2^9, representing the number of possible subsets.
  • Another participant provides an example with 3 toppings, confirming that the number of subsets is indeed 2^3 = 8, suggesting this reasoning applies to the original question.
  • In contrast, a different participant argues that the total number of combinations should be 45, explaining that order does not matter and providing a detailed breakdown of combinations involving both same and different toppings.
  • Another participant references the concept of Power sets, asserting that the reasoning about subsets is correct and aligns with the initial claim of 2^n.
  • A later reply acknowledges a misunderstanding of the question, indicating a shift in perspective.

Areas of Agreement / Disagreement

Participants express differing views on the correct calculation of combinations, with some supporting the 2^9 argument and others contesting it with alternative calculations. The discussion remains unresolved regarding the correct interpretation of the problem.

Contextual Notes

There are unresolved assumptions regarding the definitions of combinations and subsets, particularly in how participants interpret the inclusion of identical toppings and the role of order in selection.

sk381
Messages
19
Reaction score
0
My friend says that : If there are 9 different toppings then the number of ways to choose toppings for one pizza is 2^9, the number of the possible subsets of the set of 9 toppings.

How can this be? Could someone explain with an example?

Sorry if this seems very trivial...
 
Physics news on Phys.org
For example: for 3 toppings, ABC the possible subsets would be:

A,B,C,AB,AC,BC,ABC..and the final one is no topping at all.. making it 2^3=8 choices.

Is that correct?
 
No, the number of possible toppings is 45. 9^2 takes order into account. However for this problem, order does not count; AB is the same as BA. Since there are 9 cases for which the two toppings are the same, we are left with 9^2 - 9 = 72 cases in which the two toppings aren't. However since there are 2! = 2 ways to rearrange the order of selection of two different toppings, we divide 72 by 2, which gives 36. Hence we have 36 total combinations for which the toppings are different and 9 for which they are the same, giving 45 different combinations.
 
The class of subsets of the set [tex]\{A\}[/tex] is called [tex]Power(A)[/tex] and has [tex]n(Power(A)) = 2^{n(A)}[/tex]. This is because the elements, in this case the toppings, are either there or not there, so 2 to the power of the number of toppings there. Hence, your second post is correct.
 
Sorry, I had misunderstood the question.
 

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 0 ·
Replies
0
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 19 ·
Replies
19
Views
4K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 2 ·
Replies
2
Views
1K
  • · Replies 22 ·
Replies
22
Views
3K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 29 ·
Replies
29
Views
6K
  • · Replies 6 ·
Replies
6
Views
2K