On this page
Combinatorics is full of problems asking you to form a group under specific constraints. One standard case involves counting subsets when you are forced to include or exclude a specific element.
What is the number of subsets containing a particular element?
For a finite set with n elements, the number of subsets that contain a particular element is 2ⁿ⁻¹ according to the mathematical symmetry of the power set. Because each element is either in or out, exactly half of the total 2ⁿ subsets will include any given element, while the other half will not.
For example, consider the set {A, B, C}, which has n = 3 elements. The total number of subsets is 2³ = 8. If we list them, we get the empty set ∅, {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, and {A, B, C}.
The subsets containing the element A are {A}, {A, B}, {A, C}, and {A, B, C}. As expected, that is 2³⁻¹ = 2² = 4 subsets. Exactly half of the power set contains A.
Why does fixing an element give 2ⁿ⁻¹?
To understand the logic, imagine building a subset from scratch.
When you construct a subset from a set of size n, you must make a "yes or no" choice for each element. The multiplicative principle of counting states that multiplying these independent choices together gives the total number of possibilities.
If you are required to include a particular element, you no longer have two choices for it. You must say "yes", leaving you with exactly 1 choice for that element. For the remaining n-1 elements, you still have 2 choices each (to include them or exclude them).
Therefore, the total count becomes 1 × 2 × 2 × ... for n-1 times, yielding 2ⁿ⁻¹. This is a helpful reasoning skill for many counting problems, much like finding Aⁿ for a matrix by spotting the pattern.
This logic also applies if you are forced to exclude an element. Saying "no" gives you 1 choice. The remaining n-1 elements still have 2 choices, making the count 2ⁿ⁻¹.
How many subsets contain element a but not element b?
A common exam variation adds a second constraint: you must include element a, but you must exclude element b.
The number of subsets containing element a but not element b is 2ⁿ⁻².
Here is the step-by-step logic using the same multiplicative principle of choices:
Element a: You must include it (1 choice).
Element b: You must exclude it (1 choice).
The rest: For the remaining n-2 elements, you have 2 choices each (include or exclude).
Multiplying these choices yields 1 × 1 × 2ⁿ⁻² = 2ⁿ⁻².
If you're preparing for entrance exams, you will also see strict logical constraints on algebraic functions, like knowing when ax² + bx + c is positive for all x.
How many subsets contain at least one of two elements?
Another common question asks for the number of subsets containing at least one of two specific elements, say A or B.
You can find this using the principle of inclusion-exclusion, or you can use the total minus the unwanted subsets. It is often faster to find the subsets you do not want and subtract them from the total.
The total number of subsets is 2ⁿ. The subsets that do not contain A and do not contain B have fixed both A and B to "no". The number of subsets without A and without B is 2ⁿ⁻².
Therefore, the number of subsets containing at least one of them is the total minus the ones containing neither: 2ⁿ − 2ⁿ⁻².
For example, if n = 4, the total subsets are 2⁴ = 16. Subsets without A and B use only the remaining 2 elements, giving 2² = 4 subsets. Thus, 16 - 4 = 12 subsets contain at least one of A or B.
How Fermi's AI tutor helps with combinatorics
Combinatorics problems can be confusing because the numbers are small but the reasoning is abstract. If you find yourself guessing whether to use combinations, permutations, or powers of 2, the Fermi Concept Library maps every concept in physics, chemistry, biology, mathematics and computing, each with its own lesson to explain the foundational logic behind choices and selections.
When you are stuck on a specific question, Fermi's AI tutor doesn't just print the final answer. It holds a line of reasoning across a whole session, notices where a student is stuck, and decides whether to explain, ask, or show. It works out what they already know and builds a plan for the session, so you sit down to a clear next step instead of a blank page.
