Product Rule for Counting/General Theorem
Jump to navigation
Jump to search
This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code. |
Theorem
Suppose a process can be broken into $m$ successive, ordered, stages, with the $i$th stage having $r_i$ possible outcomes (for $i = 1, \ldots, m$).
Let the number of outcomes at each stage be independent of the choices in previous stages
Let the composite outcomes be all distinct.
Then the total procedure has $\ds \prod_{i \mathop = 1}^m r_i$ different composite outcomes.
Proof
This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
Also known as
Some sources give this as the General Combinatorial Principle.
Also see
Sources
- 1932: Clement V. Durell: Advanced Algebra: Volume $\text { I }$ ... (previous) ... (next): Chapter $\text I$ Permutations and Combinations: The $r$, $s$ Principle: Example $2$.
- 2007: Alan Tucker: Applied Combinatorics (5th ed.): $5.1$ Basic Counting Principles