[C] Question 2: combinatorics

Can you explain what this means?

I think that means :

$nCk = C(n, k) = {n \choose k} = \frac {n\,!}{(n - k)\,!k\,!};$

• if we take a square $n \times n$ , we have:

• $C(n^2, 3)$ total number of combinations of $3$ points on $n^2$ of the main square $n \times n\;$ ;

• $2 \times n\times C(n, 3)$ combinations to be subctracted from $C(n^2, 3)$ because triads of points belonging to lines parallel to the sides of the main square;

• $2 \times C(n, 3)$ combinations to be subtracted because triads of points belonging to the 2 diagonals of the main square;

• $2 \times 2\times C(n - 1, 3)$ combinations to be subtracted because triads of points belonging to the $4$ distinct diagonals of $2$ of the $4$ squares $(n -1) \times (n - 1)$ with a vertex coinciding with one of the main square;

• $...................................................$

• $2 \times 2\times C(4, 3)$ combinations to be subtracted because triads of points belonging to the $4$ distinct diagonals of $2$ of the $4$ squares $4 \times 4$ with a vertex coinciding with one of the main square;

• $2 \times 2\times C(3, 3)$ combinations to be subtracted because triads of points belonging to the $4$ distinct diagonals of $2$ of the $4$ squares $3 \times 3$ with a vertex coinciding with one of the main square;

• So, the number of triangles whose vertex are points of the square $n \times n$ , is (general formula):

$Nt(n \times n) = C(n^2, 3) - 2(n + 1)C(n, 3) - 4\sum\limits_{k\,=\,n-1}^3C(k, 3);$

$Nt(n \times n) = {n^2 \choose 3} - 2(n + 1){n \choose 3} - 4\sum\limits_{k\,=\,n-1}^3{k \choose 3};$

• for $n = 4,\, n \times n = 4^2 = 16,\,$ , it can be obtain:

$Nt(4 \times 4) = C(16, 3) - 2(4 + 1)C(4, 3) - 4C(3, 3);$

$Nt(4 \times 4) = {16 \choose 3} - 10{4 \choose 3} - 4 = 516$

i can not understand this answer :D