Worksheets — Set 16
Graph theory & combinatorics · Counting and combinatorics
Print and write your answers. Use diagrams to show thinking.
Warm-up
1. How many subsets does a set with 20 elements have? ___ 2. Prove or disprove: if n is even, n² is even. 3. P(at least one head in 19 fair tosses) = ___
_See printable PDF for diagram._
Written practice
1. How many subsets does a set with 19 elements have? ___ 2. Prove or disprove: if n is even, n² is even. 3. P(at least one head in 18 fair tosses) = ___ 4. Write the recurrence aₙ = 18aₙ₋₁ with a₀ = 1 ___ 5. Graph with 20 vertices — minimum edges for connectivity? ___ 6. Convert 58₁₀ to base 19. = ___ 7. How many subsets does a set with 22 elements have? ___ 8. P(at least one head in 21 fair tosses) = ___
___________________________ ___________________________ ___________________________ ___________________________
More written practice
1. Write the recurrence aₙ = 21aₙ₋₁ with a₀ = 1 ___ 2. Graph with 23 vertices — minimum edges for connectivity? ___ 3. Convert 61₁₀ to base 22. = ___ 4. How many subsets does a set with 25 elements have? ___ 5. P(at least one head in 24 fair tosses) = ___ 6. Write the recurrence aₙ = 24aₙ₋₁ with a₀ = 1 ___
___________________________ ___________________________ ___________________________ ___________________________ ___________________________
Patterns and rules
1. How many subsets does a set with 36 elements have? ___ 2. Prove or disprove: if n is even, n² is even. 3. P(at least one head in 35 fair tosses) = ___
_See printable PDF for diagram._
___________________________ ___________________________ ___________________________ ___________________________
Stretch
1. How many subsets does a set with 44 elements have? ___ 2. Prove or disprove: if n is even, n² is even.
___________________________ ___________________________ ___________________________ ___________________________
Parent tip: Use trees or tables for counting