Common pitfalls (miscounting, double counting, invalid assumptions) - Discrete Math

A student counts the number of ways to distribute 12 distinct books to 4 distinct students such that each student gets exactly 3 books. They calculate $\frac{12!}{3! \times 3! \times 3! \times 3!} = 369,600$ . What is the issue with this approach?
Answer: The calculation treats students as indistinguishable when they are distinct, leading to undercounting of valid distributions. The formula $\frac{12!}{3! \times 3! \times 3! \times 3!}$ counts the number of ways to partition 12 distinct books into 4 groups of 3, treating the groups as indistinguishable. However, since the students are distinct, we need to assign these groups to specific students. The correct answer should be $\frac{12!}{3! \times 3! \times 3! \times 3!} \times 4! = 369,600 \times 24 = 8,870,400$ . Alternatively, we can use multinomial coefficients: $\binom{12}{3,3,3,3} \times 4! = 369,600 \times 24$ . Choice A is wrong because the formula does account for distinct books. Choice C is wrong because the constraint is properly handled. Choice D is incorrect because there is an error.
A database administrator counts the number of ways to distribute 15 identical backup tasks among 3 servers such that Server A gets at least 3 tasks, Server B gets at least 2 tasks, and Server C gets at least 1 task. She first allocates the minimum required tasks, leaving 9 tasks to distribute freely, then applies stars and bars: $\binom{9+3-1}{3-1} = \binom{11}{2} = 55$ . A colleague claims this approach has a subtle error. What could be the issue?
Answer: The calculation is actually correct, but assumes tasks are truly identical when they might have different processing requirements The mathematical calculation is correct: allocate minimum tasks (3+2+1=6), leaving 9 tasks to distribute freely among 3 servers using $\binom{9+3-1}{3-1} = \binom{11}{2} = 55$ . However, the method assumes all backup tasks are truly identical. If tasks have different processing requirements, memory usage, or priorities, then distributions that look the same numerically might be functionally different. Choice A introduces an unstated constraint about capacity. Choice B is mathematically incorrect - the formula is properly applied. Choice D is wrong because 3+2+1=6 < 15, so the constraint is satisfiable.
A survey researcher wants to count the number of ways respondents can answer a questionnaire with 5 yes/no questions where at least 3 answers must be 'yes'. She calculates this as: $\binom{5}{3} + \binom{5}{4} + \binom{5}{5} = 10 + 5 + 1 = 16$ . Her supervisor suggests there might be an error in her reasoning. What could be problematic about this approach?
Answer: She assumed that all questions are independent when some questions might have conditional dependencies on previous answers When you encounter counting problems in discrete math, always examine whether the mathematical model matches the real-world scenario being described. Here, the researcher's calculation assumes a purely mathematical framework where questions exist independently. The correct answer is D because the researcher's combinatorial approach treats each question as mathematically independent, but real survey questions often have logical dependencies. For example, if Question 2 asks "Do you own a car?" and Question 4 asks "Do you drive to work daily?", a "no" answer to Question 2 would make a "yes" answer to Question 4 impossible or contradictory. These conditional dependencies mean that not all $\binom{5}{k}$ combinations are actually feasible responses, making her count of 16 potentially too high. Option A is incorrect because combinations are appropriate here—the order in which someone answers "yes" to 3 out of 5 questions doesn't matter, so $\binom{5}{3}$ is the right tool, not permutations. Option B misunderstands the problem; sequential completion doesn't affect the total count of possible response patterns. Option C suggests double-counting, but the researcher correctly uses mutually exclusive scenarios (exactly 3, exactly 4, or exactly 5 "yes" answers) with no overlap between these cases. Remember: When applying counting techniques to real-world problems, always ask whether the mathematical assumptions match reality. Pure combinatorial calculations assume all outcomes are equally possible, but practical constraints often eliminate certain combinations.
A quality control manager wants to select 3 defective items from a batch containing 5 defective smartphones, 4 defective tablets, and 6 defective laptops for detailed analysis. She calculates the number of ways to ensure at least one item from each category as: $\binom{5}{1} \times \binom{4}{1} \times \binom{6}{1} = 120$ . What is the primary issue with this calculation?
Answer: Her calculation is actually correct - with exactly 3 items needed and 3 categories requiring at least 1 each, she must select exactly 1 from each category The manager's calculation is actually correct. Since she needs exactly 3 items total and requires at least 1 from each of the 3 categories, she must select exactly 1 item from each category. The calculation $\binom{5}{1} \times \binom{4}{1} \times \binom{6}{1} = 5 \times 4 \times 6 = 120$ correctly counts these selections. Choice B is incorrect because combinations don't consider order. Choice C describes a non-existent problem. Choice D addresses correlation but not a counting error.
A network security analyst counts the number of ways to select 6 monitoring points from 15 available locations such that no two selected points are adjacent on the network topology. She models this as placing 6 non-attacking rooks on a $15 \times 1$ board and calculates $\binom{15-6+1}{6} = \binom{10}{6} = 210$ . What makes this modeling approach potentially incorrect?
Answer: She assumed the network topology is linear when it might have a more complex graph structure with varied adjacency relationships When you encounter problems about selecting non-adjacent items, the key insight is understanding what "adjacent" actually means in the given context. The analyst's formula $\binom{15-6+1}{6} = \binom{10}{6}$ is actually correct for selecting 6 non-adjacent items from 15 positions arranged in a single line, but this reveals the critical flaw in her approach. The formula works perfectly when items are arranged linearly (like positions 1, 2, 3, ..., 15 in a row), where "adjacent" simply means consecutive positions. However, network topologies are rarely linear arrangements. Real networks form complex graphs where a single node might connect to multiple others, creating intricate adjacency patterns that don't follow a simple sequential structure. Choice A is incorrect because $\binom{15-6+1}{6}$ is actually the standard correct formula for non-adjacent selections on a linear arrangement. Choice B misidentifies the technique—this isn't stars and bars but rather a valid combinatorial approach for linear non-adjacency problems. Choice C focuses on directionality, but adjacency in graphs is typically treated as symmetric (if A connects to B, then B connects to A), regardless of connection direction. Choice D correctly identifies the fundamental modeling error: assuming a linear topology when networks typically have complex, non-linear structures where adjacency relationships don't follow simple consecutive patterns. Study tip: When solving combinatorial problems involving real-world networks, always question whether the mathematical model matches the actual structure. Linear formulas work for linear arrangements, but networks require graph-theoretic approaches that account for their true connectivity patterns.
A tournament organizer is scheduling matches in a round-robin tournament with 8 teams where each team plays every other team exactly once. He calculates that since each team plays 7 matches, and there are 8 teams, the total number of matches is $8 \times 7 = 56$ . Later, he realizes there are only 28 time slots available. What correction should he make to his reasoning?
Answer: He should recognize that each match involves two teams, so he counted each match twice in his original calculation The organizer's calculation counts each match from both teams' perspectives. When Team A plays Team B, this match appears once in Team A's count of 7 matches and once in Team B's count. The correct number of matches is $\frac{8 \times 7}{2} = 28$ , which perfectly matches the available time slots. This is equivalent to $\binom{8}{2} = 28$ ways to choose 2 teams from 8. Choice A incorrectly focuses on simultaneous play rather than the counting error. Choice C is wrong because round-robin tournaments have no bye rounds when all teams play each other. Choice D contradicts the problem statement that each pair plays exactly once.
In analyzing social media connections, Alex counts friendship pairs in a group of 10 people where each person has exactly 4 friends within the group. He calculates the number of friendships as $10 \times 4 = 40$ . What is the fundamental error in this counting method?
Answer: He counted each friendship pair twice since each friendship involves exactly two people who both count it Alex's calculation counts each friendship from both perspectives. When person A is friends with person B, this friendship is counted once when considering A's 4 friends and again when considering B's friends. The correct count is $\frac{10 \times 4}{2} = 20$ friendship pairs. Choice A is incorrect because the problem states "friends," implying symmetric relationships. Choice C is wrong because mutual friends don't affect the basic counting principle here. Choice D is incorrect because the problem explicitly states each person has exactly 4 friends.
A network administrator wants to count the number of ways to assign 12 identical servers to 4 different data centers such that each center gets at least 2 servers. She calculates this as $\binom{12+4-1}{4-1} = \binom{15}{3}$ after ensuring the minimum constraint. Which step in her reasoning contains the critical flaw?
Answer: She applied the stars and bars formula before satisfying the minimum allocation constraint of 2 servers per center The administrator applied stars and bars directly to the original problem without first handling the constraint. The correct approach is: first allocate 2 servers to each of the 4 centers (using 8 servers), then distribute the remaining 4 servers freely among 4 centers, giving $\binom{4+4-1}{4-1} = \binom{7}{3} = 35$ . Her calculation $\binom{15}{3} = 455$ counts distributions where some centers get fewer than 2 servers. Choice B is incorrect because she didn't show the adjustment step. Choice C is wrong because her formula application was technically correct for unrestricted distribution. Choice D addresses a different potential issue not related to the mathematical error.
A student wants to count 5-digit numbers where all digits are different. They calculate $10 \times 9 \times 8 \times 7 \times 6 = 30,240$ . What assumption makes this calculation incorrect?
Answer: The calculation assumes 5-digit numbers can start with 0, but valid 5-digit numbers must start with 1-9. When counting arrangements with restrictions, you must carefully consider what values are actually allowed in each position. The student's calculation treats this as a straightforward permutation problem, but there's a hidden constraint. The calculation $10 \times 9 \times 8 \times 7 \times 6$ assumes all 10 digits (0-9) are available for the first position, then 9 remaining digits for the second position, and so on. However, 5-digit numbers cannot begin with 0 — a number like 01234 is actually just the 4-digit number 1234. Valid 5-digit numbers must start with digits 1-9. The correct calculation should be: $9 \times 9 \times 8 \times 7 \times 6 = 27,216$ . The first position has only 9 choices (1-9), the second position has 9 remaining choices (0 plus the 8 digits not used in the first position), then 8, 7, and 6 for the remaining positions. Looking at the wrong answers: A) incorrectly suggests some digits are generally restricted, but all digits 0-9 are available — just not 0 in the first position. B) mischaracterizes the calculation as assuming ascending order, which isn't relevant here. C) incorrectly claims combinations should be used instead of permutations, but order absolutely matters in numbers (12345 ≠ 54321). Remember this key principle: when counting multi-digit numbers, always check whether leading zeros create valid numbers. The first digit often has different constraints than the others.
A committee of 5 people is to be formed from a group of 8 men and 6 women. How many committees can be formed if there must be at least 2 women and at most 3 men on the committee?
Answer: $C(8,3) \cdot C(6,2) + C(8,2) \cdot C(6,3) + C(8,1) \cdot C(6,4) + C(8,0) \cdot C(6,5)$ We need at least 2 women and at most 3 men. Since the committee has 5 people total, the valid compositions are: (0 men, 5 women), (1 man, 4 women), (2 men, 3 women), and (3 men, 2 women). Choice A correctly accounts for all four cases. Choice B misses two valid cases (0 men with 5 women, and 1 man with 4 women). Choice C attempts a complement approach but incorrectly excludes valid cases. Choice D misses the case with 0 men and 5 women.
In a coding competition, teams earn points for solving problems in categories Math (M), Logic (L), and Programming (P). A student wants to count 4-member teams where at least one member specializes in each category. With 6 Math specialists, 5 Logic specialists, and 7 Programming specialists available, she calculates: $\binom{6}{1} \times \binom{5}{1} \times \binom{7}{2} = 6 \times 5 \times 21 = 630$ . What assumption makes this calculation invalid?
Answer: She assumed specialists cannot have expertise in multiple categories, when they might be cross-trained in several areas The calculation assumes that the 18 people (6+5+7) are distinct individuals, each specializing in exactly one category. However, if some people have expertise in multiple categories, they would be counted multiple times in the totals, making the groups non-disjoint. This would invalidate the multiplication principle. For example, if a person specializes in both Math and Logic, they appear in both the 6 Math specialists and 5 Logic specialists. Choice B is incorrect because 1+1+2=4 members as required. Choice C is wrong because she did account for this by choosing 2 from Programming. Choice D is incorrect because if the groups are disjoint, the multiplication principle applies correctly.
A cryptography student counts the number of 6-character passwords using letters A-Z where no letter appears more than twice. She reasons: "There are $26^6$ total passwords, and I need to subtract those where at least one letter appears 3 or more times." She then calculates the complement as $26^6 - 26 \times \binom{6}{3} \times 25^3$ . What makes this approach fundamentally flawed?
Answer: She only subtracted cases where exactly one letter appears exactly 3 times, ignoring letters appearing 4, 5, or 6 times The student's subtraction $26 \times \binom{6}{3} \times 25^3$ only accounts for passwords where exactly one specific letter appears exactly 3 times (choosing the letter, choosing 3 positions for it, and filling remaining 3 positions with other letters). This misses cases where a letter appears 4, 5, or 6 times. A complete solution requires subtracting all cases where any letter appears 3+ times, which involves much more complex inclusion-exclusion. Choice B, while relevant to complete counting, isn't the primary flaw in her specific calculation. Choice C is incorrect because $\binom{6}{3}$ correctly counts position choices. Choice D is wrong because her calculation doesn't assume consecutive positions.
A student claims that the number of ways to arrange the letters in STATISTICS is $\frac{10!}{3! \cdot 3! \cdot 2!}$ . What error, if any, has the student made?
Answer: The student double-counted some arrangements; the denominator should be $2! \cdot 3! \cdot 2!$ since there are 2 S's, 3 T's, and 2 I's. STATISTICS has 10 letters: S(2), T(3), A(1), T(counted in 3), I(2), S(counted in 2), T(counted in 3), I(counted in 2), C(1), S(counted in 2). So we have 2 S's, 3 T's, 2 I's, 1 A, and 1 C. The correct formula is $\frac{10!}{2! \cdot 3! \cdot 2!}$ . The student wrote $\frac{10!}{3! \cdot 3! \cdot 2!}$ , incorrectly using $3!$ twice instead of $2!$ for the S's. Choice A is wrong because there is an error. Choice B is wrong because I's are already accounted for. Choice C incorrectly suggests there should be four factors in the denominator.
A geneticist studies inheritance patterns by counting the number of ways to select 4 individuals from 3 families where Family A has 5 members, Family B has 4 members, and Family C has 3 members, ensuring at least one individual from each family is selected. She calculates this as: $\binom{12}{4} - \binom{9}{4} - \binom{8}{4} - \binom{7}{4} + \binom{5}{4} + \binom{4}{4} + \binom{3}{4} - 0$ . What error appears in her inclusion-exclusion calculation?
Answer: She attempted to compute $\binom{3}{4}$ which is undefined since you cannot choose 4 individuals from a 3-member family The term $\binom{3}{4} = 0$ because you cannot choose 4 people from a 3-person family, but including it in the calculation suggests a conceptual error. The inclusion-exclusion should be: Total - (missing A) - (missing B) - (missing C) + (missing A and B) + (missing A and C) + (missing B and C) - (missing all three). The terms are: $\binom{12}{4} - \binom{9}{4} - \binom{8}{4} - \binom{7}{4} + \binom{5}{4} + \binom{4}{4} + 0 - 0$ . While $\binom{3}{4} = 0$ mathematically, its inclusion suggests confusion about what each term represents. Choice A is incorrect because the signs follow proper inclusion-exclusion. Choice B is wrong because she correctly identified the exclusions. Choice C is not the primary issue since the undefined binomial coefficient is more fundamental.
An event planner arranges seating for 12 people at 3 round tables, with 4 people per table. She calculates the number of arrangements as: $\frac{12!}{4! \times 4! \times 4!} \times \frac{1}{3!} \times (3!)^3$ , where the first term distributes people to tables, the second accounts for identical tables, and the third handles circular arrangements at each table. What is the most significant error in this approach?
Answer: She applied the division by $3!$ for identical tables but then multiplied by $(3!)^3$ for circular arrangements, creating inconsistent counting The error is in the logical flow: she first divides by $3!$ treating tables as indistinguishable, but then multiplies by $(3!)^3$ for seating arrangements at each table. However, if tables are indistinguishable, then different circular arrangements at 'Table 1' vs 'Table 2' shouldn't be counted as distinct. The correct approach should either: (1) treat tables as distinguishable and use $\frac{12!}{4! \times 4! \times 4!} \times (3!)^3$ , or (2) treat them as indistinguishable and use $\frac{12!}{4! \times 4! \times 4! \times 3!} \times (3!)^3$ . Choice A misses the main logical inconsistency. Choice B introduces an unnecessary reflection consideration. Choice D is incorrect because $3! = (4-1)!$ for circular arrangements.
In counting lattice paths from $(0,0)$ to $(5,3)$ using only right (R) and up (U) moves, a student reasons: 'We need 5 R's and 3 U's in some order, so the answer is $\frac{8!}{5! \times 3!}$ .' Later, they want to count paths that pass through $(2,1)$ . They calculate: 'Paths from $(0,0)$ to $(2,1)$ times paths from $(2,1)$ to $(5,3)$ : $\frac{3!}{2! \times 1!} \times \frac{5!}{3! \times 2!} = 3 \times 10 = 30$ .' If the total number of paths from $(0,0)$ to $(5,3)$ is 56, what can we conclude?
Answer: Both calculations are correct; exactly 30 out of 56 total paths pass through point $(2,1)$ on the lattice grid. When you encounter lattice path problems, you're working with combinations where order matters for placement but you're counting distinct arrangements. The key insight is that moving from one point to another requires a specific number of right (R) and up (U) moves, and you're arranging these moves in different sequences. Let's verify both calculations. For paths from $(0,0)$ to $(5,3)$ , you need exactly 5 R's and 3 U's, giving you 8 total moves. The number of ways to arrange these is $\binom{8}{3} = \frac{8!}{5! \times 3!} = 56$ . This confirms the given total. For paths through $(2,1)$ , you break the journey into two segments: $(0,0)$ to $(2,1)$ requires 2 R's and 1 U from 3 total moves, so $\binom{3}{1} = 3$ paths. From $(2,1)$ to $(5,3)$ requires 3 more R's and 2 more U's from 5 total moves, so $\binom{5}{2} = 10$ paths. Since you must complete both segments, you multiply: $3 \times 10 = 30$ . Option A is wrong because $5^3 = 125$ represents something entirely different—not lattice path counting. Option B misunderstands the multiplication principle; you multiply because each path in the first segment can be paired with each path in the second segment. Option D incorrectly applies inclusion-exclusion, which isn't needed here since we want paths that specifically go through $(2,1)$ . Remember: lattice path problems through intermediate points use the multiplication principle—break the path into segments and multiply the combinations for each segment.
In how many ways can 10 identical books be distributed among 4 distinct shelves such that each shelf gets at least one book?
Answer: $C(6+4-1, 4-1) = C(9,3) = 84$ Since each shelf must get at least one book, we first place one book on each shelf, using 4 books. Then we distribute the remaining 6 identical books among 4 shelves with no restrictions, which is a stars and bars problem: $C(6+4-1, 4-1) = C(9,3) = 84$ . Choice A uses 9 books instead of the remaining 6. Choice B uses all 10 books without accounting for the restriction. Choice D applies inclusion-exclusion as if books were distinct, which is incorrect for identical books.
In a round-robin tournament with 8 players, each player plays every other player exactly once. A student calculates the total number of games as $8 \times 7 = 56$ . What counting error has occurred?
Answer: The student double-counted each game; the correct count is $\frac{8 \times 7}{2} = 28$ games total. In a round-robin tournament, each game involves exactly 2 players, and we need to count unordered pairs. The student calculated $8 \times 7 = 56$ by considering each player playing 7 others, but this counts each game twice (once for each participant). The correct count is $C(8,2) = \frac{8 \times 7}{2} = 28$ games. Choice A incorrectly suggests using permutations. Choice C incorrectly adds bye rounds that don't exist. Choice D makes an additional error by having each player play themselves.
A committee of 5 people is to be selected from 8 men and 7 women, with the requirement that at least 2 women must be on the committee. Sarah calculates this as $\binom{15}{5} - \binom{8}{5}$ . What is the primary error in Sarah's approach?
Answer: She failed to account for committees with exactly 1 woman, which should also be subtracted Sarah's calculation $\binom{15}{5} - \binom{8}{5}$ finds the total committees minus committees with 0 women (all men). However, the constraint is "at least 2 women," which means committees with exactly 1 woman should also be excluded. The correct calculation should be $\binom{15}{5} - \binom{8}{5} - \binom{8}{4}\binom{7}{1}$ . Choice B is incorrect because $\binom{8}{5}$ correctly represents all-male committees. Choice C is wrong because there's no double-counting occurring. Choice D is incorrect because 15 is the correct total.
In a programming contest, participants can earn points in three categories: Algorithm (A), Data Structures (D), and Implementation (I). A student counts the number of ways to earn exactly 10 points where each category contributes at least 1 point, by solving $x + y + z = 10$ where $x, y, z \geq 1$ . The student transforms this to $u + v + w = 7$ where $u, v, w \geq 0$ and concludes there are $\binom{9}{2} = 36$ ways. What assumption makes this approach potentially invalid?
Answer: The assumption that points are indistinguishable within categories when they might have different difficulty levels The stars and bars method assumes that points within each category are indistinguishable - that earning 3 points in Algorithm category can only happen in one way. However, if there are multiple problems of different difficulties within each category, then 3 points in Algorithm could be earned in multiple ways (e.g., one 3-point problem vs. three 1-point problems). Choice A is incorrect because the method properly handles integer constraints. Choice C is wrong because the transformation is mathematically correct. Choice D is incorrect because the problem states points can be earned in all three categories simultaneously.

Start this quiz