1
$\begingroup$

I understand the purpose for division. Multiplication is simply repeated addition and division is simply repeated subtraction. So lets say we have 4 total items. Plugging 4 into the equation we get 4(4-1)/2 = 12/2 = 6. So there are 6 possible combinations with 4 items. Applying the intuitive understanding of division as repeated subtraction, we can plot 12 on a numberline, and then since we are dividing by 2, we count backwards by 2 until we reach 0. We can do this 6 times.

That makes sense to me. My issue is with the numerator. Why must a number of items be multiplied by one number less than itself? I understand the basic reason for multiplying the number of items by itself: pairs include two items, so the 4 takes care of the possible numbers on the first item, but why does the second item only receive 3 possible combinations? My hypothesis is that it prevents overlap, but I am having difficulty interpreting the logic of this. How exactly does it overlap? Can this be visualized on a matrix? Why does 4*4/2 = 8 not give the correct number of unique pairs?

$\endgroup$
4
$\begingroup$

The formula $n(n-1)/2$ for the number of pairs you can form from an $n$ element set has many derivations, even many on this site.

One is to imagine a room with $n$ people, each of whom shakes hands with everyone else. If you focus on just one person you see that she participates in $n-1$ handshakes. Since there are $n$ people, that would lead to $n(n-1)$ handshakes.

Note here that we are thinking about the multiplication $xy$ as the total for $x$ groups of $y$ things, not as repeated addition. Computationally they are the same, but psychologically they are different.

To finish the problem, we should realize that the total of $n(n-1)$ counts every handshake twice, once for each of the two people involved. So the number of handshakes is $n(n-1)/2$.

Note (continued). We are thinking about $x/y$ as the number of groups of size $y$ it takes to get to a total of $x$, not as repeated subtraction. Computationally they are the same, but psychologically they are different.

Among the other ways to think about this problem (and one which kids find first). Imagine the people entering the room one at a time and introducing themselves. The first person has nothing to do. The second person shakes one hand. The third person shakes with the two already there, and so on. The last person has $n-1$ hands to shake. So the total number of handshakes is $$ 0 + 1 + \cdots + (n-1) . $$ There are many tricks for evaluating that sum to discover that it's $n(n-1)/2$.

$\endgroup$
1
$\begingroup$

You are almost correct that $4*4/2$ would give us the amount of pairs if we simply chose two numbers from our set of n numbers, and let order matter.

Let $[a,b,c,d]$ be our set of four objects. According to your plan, we pick two of the objects from this set with replacement, meaning that if we choose $a$, then we can choose $a$ again as our second object. This would give us the following pairs. $$ aa,ab,ac,ad\\ ba,bb,bc,bd\\ ca,cb,cc,cd\\ da,db,dc,dd $$ As you can see, we do count each of the numbers that are not in the main diagonal twice, but the numbers on the diagonal are counted only once. Our square here is $4$ by $4$, so there are $4$ numbers on the diagonal and $16-4=12$ numbers that are not. So we divide the second number by two and add it to the first to get the total amount of distinct pairs without order mattering, would in fact be $10$, and for a general $n$ by $n$ square of possibilities, you can see that this number becomes $n(n-1)/2+n$.

However, I think the problem that you are being asked here is how many ways are there to choose two numbers from the set with replacement. Thus we would simply subtract the diagonal from our previous answer to get $n(n-1)/2$.

Hope this helps!

$\endgroup$
  • $\begingroup$ What $\binom{n}{2}$ counts is the number of ways of selecting two elements from a set without replacement. $\endgroup$ – N. F. Taussig Oct 11 '18 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.