Counting determines the number of possible outcomes without listing them individually. In computing, it helps estimate configuration spaces, password possibilities, and software testing workloads.
Method
When to use it
Count
Sum rule
Mutually exclusive alternatives
m+n
Product rule
Successive choices with fixed option counts
n1n2⋯nk
🧠 Key Concepts
Sum Rule
Product Rule
Mutually Exclusive Alternatives
Factorial
Permutations
Combinations
Ordered Selections
Repetition
Overlapping Outcomes
🧠 Quick Check
See what you remember from the summary.
1 / 3
A developer selects one project topic from either a networking list or a database list. The lists have no shared topics. What counting method applies directly?
🧠 Flashcards Preview
Tap a card to reveal the definition.
1 / 3
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Counting: Sum and Product Rules, Permutations and Combinations
📘 Overview
Counting determines how many outcomes a situation has without listing them one by one. The sum rule and product rule combine counts for alternatives and for successive choices, while permutations and combinations count ordered and unordered selections from a set of distinct objects.
🧠 Key Idea
Most elementary counting problems come down to two questions: are the choices alternatives (add) or successive steps (multiply), and does the order of the chosen objects matter (permutation) or not (combination)?
⚔️ Core Details:
- Sum rule: if a task can be done in one of m ways or in one of n ways, and no way appears in both lists, it can be done in m+n
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Challenge Quiz
Answer all questions first, then see feedback at the end — the way real exams work.
Adaptive Practice
Focuses each session on what you got wrong, not what you already know.
Board Exam ModePro
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.
Public pages are read-only. Open your own note in the app workspace to edit, review, or manage it.
Permutations
Ordered selections without repetition
P(n,r)=(n−r)!n!
Combinations
Unordered selections without repetition
C(n,r)=r!(n−r)!n!
For overlapping alternatives, subtract the shared outcomes once to avoid double counting. The product rule applies directly when each step's number of available choices does not depend on earlier selections.
The factorial n!=n(n−1)⋯2⋅1 counts arrangements of distinct objects, with 0!=1. Each selection of r distinct objects has r! arrangements, so C(n,r)=P(n,r)/r!. Combinations also satisfy C(n,r)=C(n,n−r).
When each of r ordered positions can independently contain any of n symbols, repetition is allowed and the count is nr. This model applies to PINs and passwords under the stated assumptions. Distinguishing ordered test sequences from unordered groups of modules prevents incorrect workload estimates.
Common Misconceptions: Alternatives cannot simply be added when they overlap. Successive choices do not require the same number of options at every step. Permutations and combinations differ because order matters only for permutations; their stated formulas assume no repetition.
ways. Example: a project topic chosen from 3 networking topics or 5 database topics gives
3+5=8
choices. If the lists overlap, the shared ways must be subtracted once so they are not counted twice.
- Product rule: if a task is done in
k
successive steps with
n1,n2,…,nk
ways, and the number of ways at each step does not depend on which way was chosen earlier, it can be done in
n1n2⋯nk
ways. Example: 3 main dishes and 4 drinks give
3⋅4=12
meals.
- Factorial:
n!=n(n−1)⋯2⋅1
, with
0!=1
. It counts the ways to arrange
n
distinct objects in a row.
- Permutations count ordered selections of
r
distinct objects from
n
distinct objects, with no object used twice:
P(n,r)=(n−r)!n!
. Example: ordered 3-letter codes from the 5 distinct letters A to E number
P(5,3)=60
.
- Combinations count unordered selections of
r
objects from
n
distinct objects:
C(n,r)=r!(n−r)!n!
. Each unordered selection can be arranged in
r!
ways, so
C(n,r)=r!P(n,r)
. Example: choosing 3 of the 5 letters without regard to order gives
C(5,3)=3!60=10
.
- Repetition: when each of
r
ordered positions may use any of
n
symbols, with repetition allowed, there are
nr
sequences. Without repetition, the count of ordered selections is
P(n,r)
.
- Choosing the tool: mutually exclusive alternatives suggest the sum rule; successive steps suggest the product rule; if order matters and nothing repeats, use
P(n,r)
; if order does not matter and nothing repeats, use
C(n,r)
.
🎯 Why It Matters:
- A 4-digit PIN allows 104=10,000 possibilities, and an 8-character password drawn from 62 symbols allows 628 (about 2.18×1014), which shows how length drives the cost of guessing.
- A system with 5 on/off settings, each chosen freely, has 25=32 configurations, so the number of configurations doubles with each added setting.
- Choosing 3 of 10 modules to test together can be done in C(10,3)=120 ways, but testing every ordered selection of 3 of the 10 modules would be P(10,3)=720 cases, so deciding whether order matters changes the workload.
- Counting shows when exhaustive checking of every case is feasible and when it is not.
🧠 Quick Recall:
- Sum rule - m+n ways for mutually exclusive alternatives; subtract any overlap.
- Product rule - n1n2⋯nk ways for successive steps whose option counts do not depend on earlier choices.
- Factorial - n! counts arrangements of n distinct objects; 0!=1.
- Permutation - P(n,r)=(n−r)!n!, order matters, no repetition.
- Combination - C(n,r)=r!(n−r)!n!, order ignored, no repetition; C(n,r)=C(n,n−r).
- Sequences with repetition - nr ordered selections of length r from n symbols.
Memorization
Learn once, then get reminded to review again after 1, 3, 7, 14, and 30 days — so it actually sticks.
