Number of Triangles from given set of rods
AI
could one assemble, allowing concatenation (but where order of sticks
in a concatenation does not matter).
This question is inspired from http://mathworld.wolfram.com/TriangleCounting.html
Please note the difference between my question and question posed in
the given link
James Waldby
As noted in your link, "values for n=1, 2, ... are 0, 0, 0, 1, 3, 7,
13, 22, ... (Sloane's A002623)". Call this sequence B(n), and call
yours C(n). So B(4)=1, C(4)=3, from {(2,3,4), (2,1+3,4), (1+2,3,4)}.
Do you wish to equate forms like (4,5,6) == (1+3,5,6) == (4,2+3,6),
or count those as three distinct triangles?
--
jiw
AI
> On Mon, 04 May 2009 05:08:25 -0700, AI wrote:
> > we have set of n "sticks" of lengths {1,2,...n}, how many triangles
> > could one assemble, allowing concatenation (but where order of sticks in
> > a concatenation does not matter).
>
> > This question is inspired from
> > difference between my question and question posed in the given link
>
> As noted in your link, "values for n=1, 2, ... are 0, 0, 0, 1, 3, 7,
> 13, 22, ... (Sloane's A002623)". Call this sequence B(n), and call
> yours C(n). So B(4)=1, C(4)=3, from {(2,3,4), (2,1+3,4), (1+2,3,4)}.
>
> Do you wish to equate forms like (4,5,6) == (1+3,5,6) == (4,2+3,6),
> or count those as three distinct triangles?
>
> --
> jiw
Yes you are right (4,5,6) == (1+3,5,6) == (4,2+3,6) so it will get
counted only once.
hagman
> On May 4, 10:58 pm, James Waldby <n...@no.no> wrote:
>
>
>
> > On Mon, 04 May 2009 05:08:25 -0700, AI wrote:
> > > we have set of n "sticks" of lengths {1,2,...n}, how many triangles
> > > could one assemble, allowing concatenation (but where order of sticks in
> > > a concatenation does not matter).
>
> > > This question is inspired from
> > > difference between my question and question posed in the given link
>
> > As noted in your link, "values for n=1, 2, ... are 0, 0, 0, 1, 3, 7,
> > 13, 22, ... (Sloane's A002623)". Call this sequence B(n), and call
> > yours C(n). So B(4)=1, C(4)=3, from {(2,3,4), (2,1+3,4), (1+2,3,4)}.
>
> > Do you wish to equate forms like (4,5,6) == (1+3,5,6) == (4,2+3,6),
> > or count those as three distinct triangles?
>
> > --
> > jiw
>
> Yes you are right (4,5,6) == (1+3,5,6) == (4,2+3,6) so it will get
> counted only once.
Lt n be big enough.
It is possible to select a subset of {1,2,...,n} with *any* sum
between
n*(n+1)/6 and n*(n+1)/2 for the ongest side:
Just start by taking n, n-1, n-2, ... until taking the next would
be too much and then take the missing number.
What remains is a set {1,2,3,...,m}\{k}.
If the k were not missing, the same argument would show that one can
obtain *any* sum between m*(m+1)/4 and m*(m+1)/2 for the second
longest side.
If one ignores this defect, one can obtain *all* triangles (a,b,c)
with a+b+c = n*(n+1)/2.
And indeed circumventing the defect is (mostly) easy:
a) Assume we wish to select k before the last number, i.e. we wish to
select {s, r, r+1, ...,m} with s<r<=k in oder to obtain sum
S = s+r+...+m. Then repeat the algorithm to obtain sum S+k, this also
involves aking k, and drop k.
b) Assume we wish to select k as last number, i.e. we wish to select
{k,r,r+1,...m} with k<r in order to arrive at sum S = k+r+...+m.
If k<r-2, we can select {k+1,r-1,r+1,...m}.
If k>2, we can select {1,k-1,r,r+1,...m}.
The remaining cases k<=2, r<=k+2 correspond to triangles withsmall
smallest sides c and in fact pose a problem only if c=k.
This can usuakky be avoided be modifying the choice made for the
longest side, in fact I think it can be avoided for all cases
but side lengths b=c=1, b=c=2
rmil...@pacbell.net
> > > On Mon, 04 May 2009 05:08:25 -0700, AI wrote:
> > > > we have set of n "sticks" of lengths {1,2,...n}, how many triangles
> > > > could one assemble, allowing concatenation (but where order of sticks in
> > > > a concatenation does not matter).
> > > Do you wish to equate forms like (4,5,6) == (1+3,5,6) == (4,2+3,6),
> > > or count those as three distinct triangles?
>
> > > --
> > > jiw
>
> > Yes you are right (4,5,6) == (1+3,5,6) == (4,2+3,6) so it will get
> > counted only once.
>
> Lt n be big enough.
> It is possible to select a subset of {1,2,...,n} with *any* sum
> between
> n*(n+1)/6 and n*(n+1)/2 for the longest side...
For a given n, I believe we can form all triangles (a,b,c) with
a<=b<=c, a+b>c, and a+b+c<=n(n+1)/2 with the exception of
112, 122, 222, 133, 223, 233, 333, 144, 344, 444. This was done
with a hand search, I might have missed some. I then wrote a
brute force program to find the number of triangles for a given
n. Starting with n=4 (there are none below this), I find
3, 24, 74, 175, 368, 710, 1275, 2168, 3539, 5574, 8495, 12590,
which is neither polynomial or in Sloane (even if you add back
in the missing triangles)
hagman
Ah, yes I tried to count those triangles using *all* given sticks.
And I ignored the triangle inequality along theway, i.e.
as I showed at most triangles b=c=1 or b=c=2 are ruled out
and these matter only if 1+2+...+n = a+b+c < 2(b+c) <= 8, i.e. n<=3.
Thus the sequence I investigated starts
1 0
2 0 (should be 1, but (1,1,1) is not allowed)
3 0 (should be 1, but (2,2,2) is no allwoed)
4 2
5 7
6 12
7 16
8 27
9 48
10 70
11 91
12 127
13 184
14 243
15 300
16 385
17 507
18 631
19 752
20 919
This sequence (with or without correction) is not in OEIS, either.
hagman
AI
>
> - Show quoted text -
Well so at least I was right for first three 3, 24, 74 beyond which I
think I messed up somewhere:)
Can you share your program?
rmil...@pacbell.net
Here it is. It seems more natural to count the triangles with
perimeter < n, instead of perimeter < n(n+1)/2. If you count
with < n, the mods are pretty obvious and it is found in Sloane
at A001400. Note that in my previous post of triangles to delete
I missed 111.
def prog(n,plev):
#calculates number of triangles formed from rods of size
(1,2,3,...n)
#rods can be added, so we just need (a,b,c) with a<=b<=c,
#a+b+c<=n(n+1)/2, a+b>c, and not 111, 112, 122, 222, 133, 223,
333, 144, 344, 444
#this program does not subtract the ones above
rodtot=n*(n+1)/2
clim=(rodtot-1)/2
if plev>4: print 'n, clim',n,clim
allcount=0
for c in range(1,clim+1):
count=0
for a in range(1,c+1):
bmin=max(a,c-a+1)
bmax=min(c,rodtot-a-c)
if bmax>=bmin: count+=bmax-bmin+1
if plev>4: print 'c,a,bmax,bmin,count',c,a,bmax,bmin,count
allcount+=count
if plev>4: print 'c,new total grand total',c,count,allcount
return allcount
AI
>
> - Show quoted text -
Thanks a lot, I will submit this to OEIS whenever I get time.
Thanks again :)
hagman
I've looked into this once more and found that a few more cases are
unsolveable.
Given k and integers a,b,c (not necessarily making a triangle), can me
find disjoint
subsets A,B,C of {1,2,...,k} such that a=sum A, b=sum B, c=sum C?
Well, we note that D := {1,2...,k}\(A U B U C) is also a set and we
can let d=sum D.
So the problem really is:
For which tuples (k; a,b,c,d) with a+b+c+d = k(+1)/2 does there exist
a partition
of {1,2,...,k} into four sets A,B,C,D such that a=sum A etc.?
THEOREM: Problem (k; a, b, c, d) is solveable unless it is
(up to permutation of a, b, c, d) one of
(5; 6, 6, 2, 1),
(6; 8, 8, 3, 2), (6; 8, 7, 3, 3),
(7; 10, 10, 4, 4), (7; 10, 8, 8, 2) or (7; 14, 8, 3, 3)
or matches (up to permutation of a, b, c, d) one of the patterns
(* ; 1, 1, *, *), (* ; 2, 2, *, *), (* ; 3, 3, 1, *), (* ; 3, 3, 2,
*),
(* ; 3, 3, 3, *), (* ; 4, 4, 1, *), (* ; 4, 4, 3, *) or (* ; 4, 4, 4,
*).
The proof is more technical than ingenious
(readable here: http://www.von-eitzen.de/math/trianglesticks.pdf ).
But it shows that triangle a=6, b=c=4 cannot be built if k=5 (although
6+4+4 < 5*6/2),
nor can a=b=10, c=4 be built if k=7.
Thus there *are* a few more than the small obvious exceptions ...
hagman
Taking my extended exception list into account it seems that the
number of triangles grows as follows (of course these figures are just
slightly smaller than rmill's):
1 0
2 0
3 0
4 3
5 20
6 70
7 172
8 366
9 709
10 1274
11 2166
12 3537
13 5573
14 8494
15 12588
16 18227
17 25846
18 35942
19 49124
20 66138
21 87827
22 115132
23 149166
24 191238
25 242800
26 305447
27 381012
28 471602
29 579518
This was calculated using
#include <stdio.h>
int N[15];
void UP(int x) {
if (x<15) ++N[x];
}
void DN(int x) {
if (x<15) --N[x];
}
int main() {
for (int i=0; i<15; ++i) N[i]=0;
for (int k=1; k<30; ++k) {
int ct = 0;
int abcd = (k*(k+1))/2;
for (int a=1; a+a < abcd; ++a) {
UP(a);
for (int b=a; b+b>=a; --b) {
UP(b);
for (int c=a-b+1; c<=b; ++c) {
int d = abcd-a-b-c;
if (d<0) break;
UP(c);
UP(d);
for (int test=0; test<1; +
+test) {
if (N[1]>=2) break;
if (N[2]>=2) break;
if (N[3]>=3) break;
if (N[3]>=2 && N[1]+N
[2]) break;
if (N[4]>=3) break;
if (N[4]>=2 && N[1]+N
[3]) break;
if (N[6]==2 && N[1] &&
N[2]) break;
if (N[8]==2 && N[3] &&
N[2]) break;
if (N[3]==2 && N[7] &&
N[8]) break;
if (N[4]==2 && N[10]
==2) break;
if (N[8]==2 && N[10]
&& N[4]) break;
if (N[3]==2 && N[8] &&
N[14]) break;
++ct;
}
DN(d);
DN(c);
}
DN(b);
}
DN(a);
}
printf ("%d %d\n", k, ct);
}
}
A slight modification of the above program counts all triangles that
can be produced by making use of all rods (i.e. with d=0, the way I
originally interpreted the problem -- ):
1 0
2 0
3 0
4 2
5 7
6 12
7 16
8 27
9 48
10 70
11 91
12 127
13 184
14 243
15 300
16 385
17 507
18 631
19 752
20 919
21 1141
22 1365
23 1587
24 1875
25 2241
26 2611
27 2977
28 3434
29 3997
I had thought I had overlooked something when I first posted this
sequence, but it seems I did already count all exceptions then ...
After all, the triangle condition may appear somewhat artificial, so I
counted all solutions (up to permutation) and obtained
1 1
2 2
3 5
4 13
5 35
6 93
7 214
8 437
9 815
10 1436
11 2413
12 3886
13 6041
14 9125
15 13436
16 19323
17 27221
18 37670
19 51293
20 68797
21 91025
22 118982
23 153797
24 196721
25 249206
26 312935
27 389761
28 481709
29 591080
It appears that none of the sequences is "known".
hagman
> On 11 Mai, 23:24,hagman<goo...@von-eitzen.de> wrote:
>
>
>
> > On 7 Mai, 14:37, AI <vcpan...@gmail.com> wrote:
>
> > > On May 7, 1:17 am, rmill...@pacbell.net wrote:
>
> > > > On May 5, 6:35 pm, AI <vcpan...@gmail.com> wrote:
>
> > > > > On May 5, 10:47 pm, rmill...@pacbell.net wrote:
>
> > find disjoint
> > subsets A,B,C of {1,2,...,k} such that a=sum A, b=sum B, c=sum C?
> > Well, we note that D := {1,2...,k}\(A U B U C) is also a set and we
> > can let d=sum D.
> > So the problem really is:
> > For which tuples (k; a,b,c,d) with a+b+c+d = k(+1)/2 does there exist
> > a partition
> > of {1,2,...,k} into four sets A,B,C,D such that a=sum A etc.?
>
> > THEOREM: Problem (k; a, b, c, d) is solveable unless it is
> > (up to permutation of a, b, c, d) one of
> > (5; 6, 6, 2, 1),
> > (6; 8, 8, 3, 2), (6; 8, 7, 3, 3),
> > (7; 10, 10, 4, 4), (7; 10, 8, 8, 2) or (7; 14, 8, 3, 3)
> > or matches (up to permutation of a, b, c, d) one of the patterns
> > (* ; 1, 1, *, *), (* ; 2, 2, *, *), (* ; 3, 3, 1, *), (* ; 3, 3, 2,
> > *),
> > (* ; 3, 3, 3, *), (* ; 4, 4, 1, *), (* ; 4, 4, 3, *) or (* ; 4, 4, 4,
> > *).
>
> > The proof is more technical than ingenious
> > (readable here:http://www.von-eitzen.de/math/trianglesticks.pdf).
Meanwhile, I've added these sequences to OEIS as
http://www.research.att.com/~njas/sequences/A160438
http://www.research.att.com/~njas/sequences/A160455
http://www.research.att.com/~njas/sequences/A160456
The attribution should probably be changed,
but I lacked adequate information; other contributions
are of course welcome at OEIS as well.
hagman
AI
>
> The attribution should probably be changed,
> but I lacked adequate information; other contributions
> are of course welcome at OEIS as well.
>
>
> - Show quoted text -
Sorry I was out of town for few days so I could not reply, Thanks a
lot for your effort in submitting it to OEIS.
Vikram Pandya ("AI")