1
$\begingroup$

Disclaimer: I'm new to cryptography.

Background: I'm reading Cryptography Engineering by Ferguson, Schneier, and Kohno, where, in Chapter 2, the authors write this:

enter image description here

Question: What is $k(k-1)/2$ called? It seems related to an arithmetic sequence $a_n = a_1 + (n-1)d$ and some kind of combination (my notes below), but I can't place it.

enter image description here

$\endgroup$
3
  • $\begingroup$ en.wikipedia.org/wiki/Triangular_number ​ ​ $\endgroup$
    – user991
    Feb 25, 2016 at 13:19
  • $\begingroup$ It's the number of pairs. It's your lower right formula if you fix $r=2$. $\endgroup$
    – SEJPM
    Feb 25, 2016 at 13:22
  • $\begingroup$ @SEJPM Just nitpicking: "pairs" is quite ambiguous in this context (it could mean any of the above except the lower left). I would use the term two-element subsets. $\endgroup$
    – yyyyyyy
    Feb 25, 2016 at 13:49

2 Answers 2

2
$\begingroup$

$k(k-1)/2$ is usually called a binomial coefficient and written $k \choose 2$. It corresponds to the number of unordered pairs of distinct elements out of $k$ elements. It does indeed correspond to the sum ${k \choose 2} = \sum_{i=1}^{k-1} i$. This is quite intuitive: fixing one element, you have $k-1$ pairs containing this element. Now remove it, consider a second element: you have $k-2$ pairs with this second element, and so on. At the end, you get $(k-1) + (k-2) + \cdots +2 + 1 = k(k-1)/2$ pairs.

your bottom right formula is the general formula for ${k \choose r}$.

$\endgroup$
0
$\begingroup$

Imagine you have picked $k$ elements $e_1, e_2, .., e_k$ and you want to check if two of them have the same property (the same birthday, for instance).

Then, you can fix $e_1$ and compare it with all the other elements. This give you $k-1$ sets:

$\{e_1, e_2\},\{e_1, e_3\},\{e_1, e_4\},...,\{e_1, e_k\}$

And you can fix $e_2$ and check the property for all the other elements except $e_1$, because you already checked it ($\{e_1, e_2\} = \{e_2, e_1\}$). So you get the following $k-2$ sets:

$\{e_2, e_3\},\{e_2, e_4\},\{e_2, e_5\},...,\{e_2, e_k\}$

In the same way, the element $e_3$ gives you $k - 3$ sets

$\{e_3, e_4\},\{e_3, e_5\},\{e_3, e_6\},...,\{e_3, e_k\}$

the element $e_{k-1}$ gives you only the set $\{e_{k-1}, e_k\}$ and the element $e_k$ gives you nothing.

So, the total number of sets is

$$(k-1) + (k-2) + (k-3) + ... + 2 + 1$$

and this quantity is equal to $\frac{k(k-1)}{2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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