login
Number of triangles that can be built from rods with lengths 1,2,...,n by using and concatenating not necessarily all rods.
1

%I #6 Nov 30 2012 14:45:42

%S 0,3,20,70,172,366,709,1274,2166,3537,5573,8494,12588,18227,25846,

%T 35942,49124,66138,87827,115132,149166,191238,242800,305447,381012,

%U 471602,579518,707254,857627,1033812,1239238,1477589,1752963

%N Number of triangles that can be built from rods with lengths 1,2,...,n by using and concatenating not necessarily all rods.

%C a(n) is the number of triples (a,b,c) with b+c > a >= b >=c > 0 such that three disjoint subsets A,B,C of {1,2,...,n} with respective element sums a,b,c exist.

%H H. v. Eitzen, <a href="/A160456/b160456.txt">Table of n, a(n) for n=3..5262 (i.e. a(n) less than 2^64)</a>

%H "AI", <a href="http://groups.google.com/group/sci.math/browse_frm/thread/70c1521d9143d634">(Sci.math thread)</a>

%H H. v. Eitzen, <a href="http://www.von-eitzen.de/math/trianglesticks.pdf">How to Build Triangles from Integers</a>

%F If n<=2, then trivially a(n)=0 because three edges need at least three rods.

%F If n>=8 then a(n) = A001400(n*(n+1)/2 - 3) - 11 - A133872(n+1).

%e For n = 4, there are 10 triangles with perimeter at most 1+2+3+4 = 10: (1,1,1), (2,2,1), (2,2,2), (3,2,2), (3,3,2), (3,3,3), (4,3,2), (4,3,3), (4,4,1) and (4,4,2). We have a(4)=3 because only 3 of these can be built from rods among 1,2,3,4: (4,3,2), (4,3,3)=(4,3,1+2) and (4,4,2)=(4,1+3,2). For example, it is not possible to build (4,4,1) because the 1-rod must be used for one of the 4-edges.

%Y A002623 is a similar problem where one rod per edge is to be used.

%Y A160455 is a similar problem where all rods must be used.

%Y A160438 is related to this if one drops the triangle inequality condition.

%K easy,nonn

%O 3,2

%A _Hagen von Eitzen_, May 14 2009