Discrete structures: count only assignments that can coexist
Multiplying each task’s number of choices counts collisions as if they were valid assignments. Represent eligibility as a relation, test whether a full matching exists, then count the assignments that satisfy every constraint.
Course topic: Discrete Mathematics
Study route and exercise: University Reading List editorial project. How we curate · Sources checked:
On this page
Scope and responsibility
An introductory discrete-mathematics route through sets, logic, counting and bipartite matching. Levin means fourth edition; Epp fifth edition; Lovász–Pelikán–Vesztergombi the 2003 first edition. The invented allocation cases have distinct tasks and slots, unit capacity and explicit allowed pairs. They are not scheduling guarantees for a real organization.
Choose your starting point
I want a free inquiry route
Choose Levin for investigations, examples and selected feedback, beginning with the fourth edition’s logic and proofs.
I need explicit proof-writing instruction
Choose Epp when quantified statements, relations and argument structure need careful practice.
I want deeper problem-led reasoning
Choose Lovász and colleagues for counting and graph puzzles after you can follow short proofs.
Compare the three books
Discrete Mathematics: An Open Introduction
Oscar Levin · Edition: 4 · 2025
Free logic-to-graphs introduction
- Choose it when
- You want to investigate a small case before formalizing it.
- Use another route when
- You require complete solutions to every exercise or assume older editions use the same order.
- Selected reading
- Fourth edition: logic and proofs, graph theory, counting, then sequences; use the matching material for the case.
- Limits and trade-offs
- Hints and interactive feedback support inquiry; writing a proof remains your responsibility.
Try before choosing
List the assignments for A,B:{1,2}, C:{2,3}, checking that slots are not reused.
Check your work: Exactly two survive. Explain why eight products of local choices are not eight legal assignments.
Discrete Mathematics with Applications
Susanna S. Epp · Edition: 5 · 2020
Systematic logic and relations spine
- Choose it when
- You need to express eligibility and distinctness before counting.
- Use another route when
- You want only graph puzzles without a sustained logic/proof component.
- Selected reading
- Chapters 1–5 for language and proof, 8 for relations, 9 for counting, 10 for graphs and trees.
- Limits and trade-offs
- Broader formal coverage takes time before graph applications; WebAssign is a separate product.
Try before choosing
Write the assignment as an injective function f from tasks to slots with (t,f(t)) allowed.
Check your work: State both eligibility and injectivity. A function alone permits two tasks to share a slot.
Discrete Mathematics: Elementary and Beyond
László Lovász; József Pelikán; Katalin Vesztergombi · 2003
Problem-led counting and matchings
- Choose it when
- You can turn examples into short arguments and want a structural explanation.
- Use another route when
- You need a complete syllabus in formal logic, relations and algorithm notation.
- Selected reading
- Counting, graph/tree and matching topics; locate them by title in the selected first edition.
- Limits and trade-offs
- Compact questions reward persistence and may need a systematic companion for omitted syllabus topics.
Try before choosing
Find a subset of tasks with too few eligible slots in the follow-up.
Check your work: The witness {A,B,D} has three tasks but only two neighbors; total slot count cannot fix it.
Check your preparation
Can I distinguish a function from an injection?
A function assigns each task one slot. Injectivity additionally forbids two distinct tasks receiving the same slot.
Can I count without double counting?
For three tasks, enumerate the six slot permutations and test eligibility, rather than multiplying independent choices.
What does Hall’s condition say?
Every subset S of tasks must have at least |S| eligible neighboring slots. It is a condition on all subsets, not just individual tasks.
A six-step study plan
Steps completed: 0 / 6
These are your own study marks, not an assessment. They are not sent to this site.
-
Draw the relation
Selected reading: Levin graph material; Epp relations.
What to do: Make the bipartite graph and an allowed-pair table for the three-task case.
Check your work: There are no task-to-task edges or hidden slot capacity.
-
Formalize validity
Selected reading: Epp mathematical language and functions.
What to do: Write a quantified condition for a valid full assignment.
Check your work: Each task is assigned, every pair is allowed, and distinct tasks use distinct slots.
-
Count constructively
Selected reading: Levin counting; Lovász counting.
What to do: List every legal assignment and explain the forced choice for C.
Check your work: C must use 3; A and B then exchange 1 and 2.
-
Check a structural criterion
Selected reading: Matching topics.
What to do: Tabulate neighbor-set sizes for all seven nonempty subsets of {A,B,C}.
Check your work: No subset has fewer neighbors than tasks; counting is consistent with existence.
-
Break and repair the model
Selected reading: Matching topics and the follow-up.
What to do: Add D and slot 4, identify an obstruction, then add the stipulated edge D→4 and recount.
Check your work: A single edge restores feasibility; adding a slot without access did not.
-
Separate algorithm from certificate
Selected reading: Your two solved models.
What to do: Write an existence certificate, an impossibility certificate and a counting argument.
Check your work: A found matching proves existence; a Hall witness proves impossibility; neither alone proves a claimed count.
Worked exercise
Three tasks, eight local choices, two legal assignments
Distinct tasks A,B,C must occupy distinct slots 1,2,3. Allowed slots are A:{1,2}, B:{1,2}, C:{2,3}. Determine all full assignments and verify feasibility using Hall’s condition.
Assumptions
Each task uses exactly one slot; each slot has capacity one. Only the listed pairs are allowed. All tasks and slots are labeled; no probability model is assumed.
- A and B must occupy 1 and 2 in some order. Since slots cannot be reused, C must occupy 3. The two assignments are (A,B,C)=(1,2,3) and (2,1,3).
- For singleton task sets the neighbor counts are 2. For {A,B} it is 2; for {A,C} and {B,C} it is 3; for all three tasks it is 3. Thus every subset meets Hall’s condition.
- The product 2·2·2=8 counts choices with collisions. It is not a count of injections; checking the six slot permutations gives the same two legal assignments.
Answer and interpretation
Exactly two full assignments exist: (1,2,3) and (2,1,3) in task order A,B,C.
Test the result
Verify all listed pairs and distinct slots for each assignment. Exhaustion follows because A and B force C to 3, leaving exactly two permutations of 1 and 2.
Change an assumption
Extra capacity without access does not restore feasibility
Keep the original allowed pairs, add task D with allowed slots {1,2}, and add slot 4. Determine feasibility. Then change the eligibility relation by adding the single edge D→4; count the repaired full assignments and explain why one added edge is a minimal repair.
- Before repair, S={A,B,D} has neighbor set {1,2}. Three tasks cannot inject into two slots, so no full assignment exists even though there are four slots in total.
- After adding D→4, A and B still occupy 1 and 2. D must therefore use 4, and C uses 3. A and B can exchange their slots.
- The repaired assignments in order A,B,C,D are (1,2,3,4) and (2,1,3,4). Zero added edges cannot work by the obstruction; this one edge works, so one is the minimum number, though the repair need not be unique.
Answer and interpretation
Before the added eligibility edge: zero full assignments. With D→4: exactly two. The minimum repair size is one edge.
Test the result
The capacity of slot 4 matters only once a task can reach it. Do not conclude that D→4 is the only possible one-edge repair; the problem asks for the stipulated repair, not uniqueness.
Common mistakes
Treating choices as independent
The multiplication rule needs a valid sequential count; capacities couple the choices.
Checking only totals
Enough slots overall does not exclude a bottleneck for a subset of tasks.
Confusing existence and counting
One matching or Hall’s theorem answers feasibility; a separate exhaustive argument establishes the number.
Before moving on
- Represent an allocation as an injective allowed-pair function.
- Give a small Hall witness and explain why total capacity misses it.
- Prove both a matching count and the minimal size of a repair.
Sources and edition checks
Sources checked:
- Author: fourth edition and reorganization
The author confirms the fourth edition’s revised order, full free reading and CC BY-NC-SA 4.0 scope.
- Cengage: exact fifth edition and contents
Cengage verifies the fifth-edition logic, relations, counting and graph units, with platform products separate.
- Springer: selected first-edition softcover
Springer identifies the exact 2003 softcover and the problem-led counting/graph/matching scope.
These are proposed study activities, not official course assignments or a claim that every book has been read cover to cover.