4 items:
A
B
C
D
6 unique pairs possible:
AB
AC
AD
BC
BD
CD
What if I have 100 starting items? How many unique pairs are there? Is there a formula I can throw this into?
Asked
Active
Viewed 2.4e+01k times
85
Brian Tompsett - 汤莱恩
- 5,753
- 72
- 57
- 129
Kirk Ouimet
- 27,280
- 43
- 127
- 177
-
7I'm voting to close this question as off-topic because it does not appear to be about programming, but rather about math in general. – TylerH May 14 '18 at 14:02
-
2`(n(n-1))/2` where `n` is the number of elements i.e. in your case 4 so `(n(n-1))/2` = 6 – seralouk Jul 15 '19 at 07:53
4 Answers
131
TLDR; The formula is n(n-1)/2 where n is the number of items in the set.
Explanation:
To find the number of unique pairs in a set, where the pairs are subject to the commutative property (AB = BA), you can calculate the summation of 1 + 2 + ... + (n-1) where n is the number of items in the set.
The reasoning is as follows, say you have 4 items:
A
B
C
D
The number of items that can be paired with A is 3, or n-1:
AB
AC
AD
It follows that the number of items that can be paired with B is n-2 (because B has already been paired with A):
BC
BD
and so on...
(n-1) + (n-2) + ... + (n-(n-1))
which is the same as
1 + 2 + ... + (n-1)
or
n(n-1)/2
audiomason
- 2,283
- 1
- 15
- 9
-
-
3This is not the same as (n-1)! Which escalates much quicker. This is similar to a Triangle number though, whose formula is (n+1)n/2 (the series is positionally off by one). (n-1)n/2 for n=1,2,3,... = 0, 1, 3, 6, 10, 15, 21, 28, 36, ... – Marques Johansson Jul 05 '18 at 17:44
-
```(n (n+1) / 2) - n = ((n^2 + n) /2) - n = (n^2 + n - 2n) / 2 = (n^2 - n) / 2 = n(n - 1) / 2``` – Kok How Teh Apr 03 '20 at 09:04
93
What you're looking for is n choose k. Basically:
For every pair of 100 items, you'd have 4,950 combinations - provided order doesn't matter (AB and BA are considered a single combination) and you don't want to repeat (AA is not a valid pair).
Mike Christensen
- 88,082
- 50
- 208
- 326
-
7Help me I'm dumb - can you throw 100 items into that equation to teach me – Kirk Ouimet Sep 17 '13 at 20:41
-
18`n` would be the number of items (100 in your case), and `k` would be the number of elements in each set (2 in your case). – Mike Christensen Sep 17 '13 at 20:45
-
7No problem. I think most modern programming languages have *combination* functions built in. You can also use the function `=COMBIN(100,2)` if you have Excel handy. – Mike Christensen Sep 17 '13 at 20:54
-
4[Here's an online one](http://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html) – Conrad Frix Sep 17 '13 at 20:54
-
library(gtools); combinations(3 * 3, 2) # pairs from 9 in R (e.g. 3 x 3 factorial ANOVA) – Paul Jun 30 '21 at 08:46
-
2
45
This is how you can approach these problems in general on your own:
The first of the pair can be picked in N (=100) ways. You don't want to pick this item again, so the second of the pair can be picked in N-1 (=99) ways. In total you can pick 2 items out of N in N(N-1) (= 100*99=9900) different ways.
But hold on, this way you count also different orderings: AB and BA are both counted. Since every pair is counted twice you have to divide N(N-1) by two (the number of ways that you can order a list of two items). The number of subsets of two that you can make with a set of N is then N(N-1)/2 (= 9900/2 = 4950).
Joni
- 108,737
- 14
- 143
- 193
13
I was solving this algorithm and get stuck with the pairs part.
This explanation help me a lot https://betterexplained.com/articles/techniques-for-adding-the-numbers-1-to-100/
So to calculate the sum of series of numbers:
n(n+1)/2
But you need to calculate this
1 + 2 + ... + (n-1)
So in order to get this you can use
n(n+1)/2 - n
that is equal to
n(n-1)/2
atomsfat
- 2,863
- 6
- 34
- 36