3
$\begingroup$

Can someone please explain what double counting is?

I have no idea what it is, and Google search yields results that are too complicated for me to understand at this point in time.

If there's some simple way and example to understand the principle, and apply it to problems, I'd appreciate it a lot. Thanks.

$\endgroup$
4
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Dec 6, 2021 at 5:18
  • 1
    $\begingroup$ Well, here's a problem I'm working on: "An exercise sheet with 9 tasks was distributed to 7 students. Each student must complete at least 4 assignments. Show by double counting that there is at least one task that has been completed by at least 4 students." Now, I can ask what the solution to this is, and I'd appreciate it. However, I will probably not understand the principles behind it. I would like to know what double counting is: what features it has, how does it work, what it results in, and when and where I can use it (and why). For me, this is like archeology. $\endgroup$ Dec 6, 2021 at 5:20
  • 3
    $\begingroup$ Note by the way that there is also another, unrelated, thing called double counting in combinatorics: en.wikipedia.org/wiki/Double_counting_(fallacy). That one is related to the inclusion/exclusion principle. (I mention this to spare you some confusion in case you googled and found examples of this instead). $\endgroup$
    – Milten
    Dec 6, 2021 at 7:52
  • 1
    $\begingroup$ Milten's last comment shows why you always need to provide context. I get that you wanted a bird's-eye-view of the concept instead of that one specific example, but it is better to provide the motivating example, and then request for a general explanation. $\endgroup$ Dec 6, 2021 at 16:09

1 Answer 1

9
$\begingroup$

"Double counting" or more accurately "counting in two ways" is a combinatorial technique. It is used for showing that two expressions are equal by demonstrating that they are two ways of counting the size of same set, or to derive other conclusions from the equality of two expressions.

It is often used to prove combinatorial identities such as $$\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=2^n$$

LHS counts total number of subsets of an $n$-set according to their size. RHS also counts total number of subsets according to the choice of any element being present or not. Hence the two expressions must be equal.

For another use, let us consider your problem as example.

An exercise sheet with 9 tasks was distributed to 7 students. Each student must complete at least 4 assignments. Show by double counting that there is at least one task that has been completed by at least 4 students.

Here you can count the total number of tasks completed one way, by counting number of tasks done by each of $7$ students. If $i$th student submits $x_i$ tasks then according to given condition, $$28 \le x_1+\ldots+x_7 \le 63$$

Another way to count the same total number is asking how many students solved task number $1$, $2$, etcetera. If $y_j$ is the number of students who solved $j$th task, then total number of tasks completed is $$y_1+y_2+\ldots+y_9 = x_1+\ldots+x_7$$ From this equality, conclude $$28 \le y_1+y_2+\ldots+y_9 \le 63$$

The lower bound can be achieved if and only if atleast one of $y_j$ is greater than or equal to $4$ (since $9\times3 = 27 < 28$). This completes the proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .