Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
Counting rules determine the number of possible selections; inclusion–exclusion corrects repeated counts among overlapping sets.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
n, k and set cardinalities are nonnegative integer counts; no physical unit
| Symbol | Meaning | Unit |
|---|---|---|
| Number of distinct available elements | count | |
| Number selected, with 0≤k≤n | count | |
| Number of unordered selections without replacement | count | |
| Finite sets whose union is being counted | amount | |
| |A| | Cardinality of finite set A | count |
\binom{n}{k}=\frac{n!}{k!(n-k)!},\quad |A\cup B|=|A|+|B|-|A\cap B|,\quad |\bigcup_i A_i|=\sum_{\emptyset\ne S\subseteq[n]}(-1)^{|S|+1}|\bigcap_{i\in S}A_i|The binomial coefficient counts selections without order and without replacement. Ordered selections multiply by k!; selections with replacement use another rule. For two sets, subtract |A∩B| once to correct double counting. General inclusion–exclusion alternates signs according to the number of intersecting sets and applies to every finite family. The curriculum identifies counting, permutations/combinations and inclusion–exclusion as discrete mathematics; the lecture notes supply the equations.
The binomial coefficient counts selections without order and without replacement. Ordered selections multiply by k!; selections with replacement use another rule. For two sets, subtract |A∩B| once to correct double counting. General inclusion–exclusion alternates signs according to the number of intersecting sets and applies to every finite family. The curriculum identifies counting, permutations/combinations and inclusion–exclusion as discrete mathematics; the lecture notes supply the equations.
Counting rules determine the number of possible selections; inclusion–exclusion corrects repeated counts among overlapping sets.
Number of unordered selections
Applies without replacement; require 0 ≤ k ≤ n.
Use the example for Combinatorial counting rules and inclusion–exclusion to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
Counting rules determine the number of possible selections; inclusion–exclusion corrects repeated counts among overlapping sets.
The relation applies only under its stated assumptions.
How many groups of three can be selected from eight people if order does not matter?
binom(8,3)=8!/(3!·5!)=56.
Order within a group is not counted.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: The binomial coefficient counts selections without order and without replacement. Ordered selections multiply by k!; selections with replacement use another rule. For two sets, subtract |A∩B| once to correct double.
Formula cluster
Counting rules determine the number of possible selections; inclusion–exclusion corrects repeated counts among overlapping sets.
In a group, 12 people know Python, 9 know Java and 5 know both, so 12+9−5=16 know at least one language. There are also binom(8,3)=8·7·6/(3·2·1)=56 ways to select 3 of 8 people without order. Check: the 336 ordered selections represent each group in 3!=6 orders, so 336/6=56.
Count selections, overlapping categories, combinatorial probabilities and finite search spaces.
Here is how to work through a typical Combinatorial counting rules and inclusion–exclusion (C(n,k)=n!/[k!(n−k)!]; |A∪B|=|A|+|B|−|A∩B|) task step by step:
Task
Use the example for Combinatorial counting rules and inclusion–exclusion to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
Counting rules determine the number of possible selections; inclusion–exclusion corrects repeated counts among overlapping sets.
The relation applies only under its stated assumptions.
Task
How many groups of three can be selected from eight people if order does not matter?
Solution path
binom(8,3)=8!/(3!·5!)=56.
Order within a group is not counted.
The binomial coefficient binom(n,k) counts the distinct k-element subsets that can be formed from n distinguishable elements. Selection order does not matter, and each element may be used at most once. That is why n! is divided by k! for the orders within the chosen group and by (n−k)! for the remaining elements. With n=8 and k=3, there are 56 groups. If order among the three selected elements mattered, the count would instead be 336. Assumption: finite sets; distinguish selections with or without order and replacement.
First ask whether swapping the order of chosen elements leaves the outcome unchanged. For a committee of three, {A,B,C} is the same selection as {C,B,A}, so the binomial coefficient applies. In a code or seating order, ABC and CBA differ. Without replacement there are n!/(n−k)! ordered selections; with replacement there are n^k. Choosing the wrong order assumption can change the answer by a factor of k!. Make this decision before multiplying by any other case counts. Assumption: finite sets; distinguish selections with or without order and replacement.
Adding |A| and |B| counts each element in A∩B twice: once as a member of A and once as a member of B. Subtracting the intersection once leaves every element of the union counted exactly once. If A and B are disjoint, the intersection is zero and simple addition is enough. For 12 people who know Python, 9 who know Java and 5 who know both, 12+9−5=16 people know at least one language. Assumption: finite sets; distinguish selections with or without order and replacement.
For three sets, first add the three individual cardinalities, subtract the three pairwise intersections, then add the common three-way intersection again. This makes every element count exactly once, including elements present in two or all three sets. In general, signs alternate with the size of the intersection index: single sets positive, pairwise intersections negative, triple intersections positive. The rule works for any finite family, although it can involve many terms when there are many sets. For four or five sets, a structured table helps track every required intersection. Assumption: finite sets; distinguish selections with or without order and replacement.
The binomial coefficient counts the ways to place exactly k successes among n distinguishable trials. If every sequence with k successes has probability p^k(1−p)^(n−k), multiplying by binom(n,k) gives P(X=k). The binomial model therefore requires independent trials with a constant success probability p. The counting formula alone is not a probability; the probabilistic model supplies the weights. Sampling without replacement is usually modeled by the hypergeometric distribution instead. A small tree diagram can show equally likely sequences, but it does not replace the independence assumption. Assumption: finite sets; distinguish selections with or without order and replacement.
Quanta exam set
Curated exam set for "Combinatorial counting rules and inclusion–exclusion":
Question (front)
Which formula describes Combinatorial counting rules and inclusion–exclusion?
Answer in your set
Question (front)
How do you rearrange Combinatorial counting rules and inclusion–exclusion for Number of unordered selections?
Answer in your set
Question (front)
Which common mistake happens with Combinatorial counting rules and inclusion–exclusion?
Answer in your set
+ 8 more cards: units, variables, derivation, example, exam task
The formula set contains 11 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for C(n,k)=n!/[k!(n−k)!]; |A∪B|=|A|+|B|−|A∩B|: formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential