(no subject)
This question, from a friend's homework, interested me, so I thought I'd work it out and post my result here.
Query: how many ordered triplets (a,b,c) are there such that 1≤a≤b≤c≤N? Answer: fix the low end, a, and the high end, c, and there are c-a+1 triplets in this family. This is also the length of the line between c and a on the number line, plus one.
To find all such families, break them up into classes: all families zero units apart, then one unit apart, two units apart, etc. The families that are zero apart (where a=c) only have one triplet (a=b=c). There are N of these families. The families that are one unit apart have two possible triplets (b=a or b=c). There are N-1 of these families. Then the families that are two units apart have three possibilities, and there are N-2 of these families, and so on.
If you picture the N zero-unit families as growing rightwards from each space on the numberline, all N fit, initially. Then, when they grow by one unit, the family at the right edge grows too large to fit and falls off. One family is lost each time they grow by one unit.
The number of triplets therefore is the sum of all these possibilities. Notice that the number of possibilites is always greater than the width. For convenience, the number of possibilities shall be referred to as k. For a given level k, there are N - k + 1 families and thus k (N - k + 1) triplets.
For example, for a line of length 5, 5 zero-width families can fit between 1 and 5, each with one possibility for c (5 - 1 + 1), for a total of 5 possibilities. 4 one-width families fit, each with two possibilities (2 (5 - 2 + 1)).
Now I will transform the sum into a combinatorial expression (N+2 choose 3). I also derive an expression for the sum of the first N squares, because I have never done it before. Every sum(x) is taken to be from k=1 to k=N.
sum(k(N-k+1))
sum(kN-kk+k)
sum(kN)-sum(kk)+sum(k)
Nsum(k)-sum(kk)+sum(k)
(N+1)sum(k)-sum(kk)
N (N+1) ^ 2 / 2 - sum(kk)
sum(kk)=sum((1+2(k-1))*(N-k+1))
sum(kk)=sum((2k-1)*(N-k+1))
sum(kk)=sum(2kN-N-2kk+k+2k-1)
sum(kk)=sum(-2kk+2kN+3k-N-1)
sum(kk)=-2sum(kk)+2Nsum(k)+3sum(k)-NN-N
sum(kk)=(sum(k)(2N+3)-NN-N)/3
sum(kk)=(N(N+1)(2N+3)/2-NN-N)/3
sum(kk)=((NN+N)(2N+3)/2-NN-N)/3
sum(kk)=(2NNN+5NN+3N-2NN-2N)/6
sum(kk)=(2NNN+3NN+N)/6
sum(kk)=N(2NN+3N+1)/6
sum(kk)=N(N+1)(2N+1)/6
N (N+1) ^ 2 / 2 - N(N+1)(2N+1)/6
(3NNN+6NN+3N - 2NNN-3NN-N)/6
(NNN+3NN+2N)/6
N(NN+3N+2)/6
N(N+1)(N+2)/6
I realize my expression for sum(kk)=sum((2k-1)*(N-k+1)) is a little enigmatic. Imagine a sucession of squares lined up along a wall, each bigger than the last. The first, in front, is a simple cube, then a two-by-two block of cubes, then a three-by-three, etc. They are all lined up along the same corner so that each successive square is one cube taller and one cube wider (to the right, say) than the preceeding block. Or you could stack them up (aligning on a corner, not centering them) and they'd look the corner of a ziggurat.
We need to count all the cubes, so stick a line through them. Along the corner, the longest measurement through the stack and the only one skewering the lone cube, there should be k cubes, the longest possible line. The next longest lines are the three cubes from the two-by-two block that we haven't already skewered; they each measure N - 1 cubes deep. There are five cubes left in the three-by-three block to skewer, each measuring N - 2 cubes. The sum is therefore a sum of the products of successive odd numbers and decreasing Ns.