login
A160456
Number of triangles that can be built from rods with lengths 1,2,...,n by using and concatenating not necessarily all rods.
1
0, 3, 20, 70, 172, 366, 709, 1274, 2166, 3537, 5573, 8494, 12588, 18227, 25846, 35942, 49124, 66138, 87827, 115132, 149166, 191238, 242800, 305447, 381012, 471602, 579518, 707254, 857627, 1033812, 1239238, 1477589, 1752963
OFFSET
3,2
COMMENTS
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.
FORMULA
If n<=2, then trivially a(n)=0 because three edges need at least three rods.
If n>=8 then a(n) = A001400(n*(n+1)/2 - 3) - 11 - A133872(n+1).
EXAMPLE
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.
CROSSREFS
A002623 is a similar problem where one rod per edge is to be used.
A160455 is a similar problem where all rods must be used.
A160438 is related to this if one drops the triangle inequality condition.
Sequence in context: A183377 A067600 A348208 * A289643 A196741 A196899
KEYWORD
easy,nonn
AUTHOR
Hagen von Eitzen, May 14 2009
STATUS
approved