All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Cool Count (Posted on 2005-08-10)
The binomial coefficients T(n)=n(n+1)/2 are called triangular numbers because T(n) points can be arranged into a triangular array with n points on a side. For example, T(4)=10 points can be arranged in the familiar pattern of bowling pins. Call this triangular array with n points on a side Array(n).

If we count the number of triples of points in Array(n) which are vertices of equilateral triangles with sides parallel to those of the whole array, we get the binomial coefficient (n+1)n(n-1)/6: a nice formula in closed form (i.e., no sum of stuff).

What surprised me when I dared look at it is that if we count the number E(n) of ALL triples of points in Array(n) which are vertices of equilateral triangles, we also get a nice formula.

What is that nice formula for E(n)?

 No Solution Yet Submitted by McWorter Rating: 4.1429 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 closed form solution | Comment 2 of 8 |

If we call P(n) the number of equilateral triangles parallel to the big triangle, and A(n) the number of remaining triangles, then

E(n) = P(n) + A(n).

The triangles can point one of two directions, so all triangles not parallel to the big triangle are parallel to each other.  Given an array of base n [ie. with n(n+1)/2 points], I claim

A(n) = (n-1)(n-2)/2 + (n-3)(n-4)/2 + ...

until the numerator vanishes.  The individual summands refer to distinct sizes of triangles formed [I won't prove this in the interest of brevity].  Simplifying, we get

A(n) = (n^2 + n) p (sum[k=1 .. p] k (2k - 2n - 1)), where

p = n/2 rounded down to an integer.

Letting w = np(n+1) and simplifying further (and omitting several steps) we get

A(n) = w ({sum[k=1 .. p] k (2k - 1)} - 2n sum[k=1 .. p] k)

A(n) = w (p^3 - [{1 + (p-1)^3}/3 + {p (2n+1) (p+1)}/2])

so, altogether

E(n) = n (n+1) { [n-1]/6 + p [ p^3 - ( { 1 + (p-1)^3 }/3 + { p (2n+1) (p+1) }/2 ) ] }

anyone want to check my math ;)?

 Posted by Josh70679 on 2005-08-10 20:35:06

 Search: Search body:
Forums (0)