I'm reading Sedgewick's "Algorithms" and completely stuck at one exercise. It is formulated like that:
Develop an appropriate mathematical model describing the number of triples of N random int values that sum to 0, where the values are uniformly distributed between –M and M, where M is not small
I wrote a program to calculate such triplets. It iterates through all possible distinct triplets in array A of N numbers. A may have repeating numbers, but these numbers are form uniform random generator.
Example:
A = [7, -3, -4, 0] gives 4 distinct triplets: {7, -3, -4}, {7, -3, 0}, {7, -4, 0}, {-3, -4, 0}. We have only one triplet (first) that sums to 0.
I already calculated the number of 3-samples, it's sampling without replacement and without order: N! / 3! (N - 3)!, but I have no idea how to formulate quantity of triplets that sum to zero.
I want a model and mathematical basis, to calculate average quantity of such triplets among all 3-samples from N.
We are counting the number of pairs $(A, t)$ where $A = (A_1, \dots, A_N)$ is a sequence of $N$ numbers in the range $[-M, M]$ and $t$ is a subset of $\{1, \dots, N\}$ of size $3$ such that $\sum_{i\in t} A_i = 0$.
We first pick a triple (this can be done in ${N \choose 3}$ ways), then pick three values from $[-M, M]$ that sum to $0$ (this can be done in $3M^2 +3M+1$). Finally we pick the values of the remaining $N-3$ positions (can be done in $(2M+1)^{N-3}$ ways).
The total is thus ${N \choose 3}(3M^2+3M+1)(2M+1)^{N-3}$, and the average number of $t$'s per $A$ is therefore
$\frac{{N \choose 3}(3M^2+3M+1)(2M+1)^{N-3}}{(2M+1)^N} = \frac{{N\choose 3}(3M^2+3M+1)}{(2M+1)^3} \sim \frac{1}{16} \frac{N^3}{M}$.
EDIT: I fixed the count of triples from $[-M,M]$ with sum $0$, and calculated the average number of $t$'s, which is what the OP asked about (rather than the probability that a random triple of a random int vector will have sum zero).