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

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.

Links

H. v. Eitzen, Table of n, a(n) for n=3..5262 (i.e. a(n) less than 2^64)

"AI", (Sci.math thread)

H. v. Eitzen, How to Build Triangles from Integers

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

Adjacent sequences: A160453 A160454 A160455 * A160457 A160458 A160459

Keyword

easy,nonn

Author

Hagen von Eitzen, May 14 2009

Status

approved