login
Number of maximal collections of pairwise disjoint subsets {X,Y,Z} of {1, 2, ..., n}, each satisfying X + Y = Z.
(Formerly M0980 N0368)
11

%I M0980 N0368 #87 Oct 29 2023 01:48:05

%S 1,1,1,2,4,6,3,10,25,12,42,8,40,204,21,135,1002,4228,720,5134,29546,

%T 4079,35533,3040,28777,281504,20505,212283,2352469,16907265,1669221,

%U 19424213,167977344,14708525,191825926,10567748,149151774,2102286756,103372655,1534969405

%N Number of maximal collections of pairwise disjoint subsets {X,Y,Z} of {1, 2, ..., n}, each satisfying X + Y = Z.

%D R. K. Guy, "Sedlacek's Conjecture on Disjoint Solutions of x+y= z," in Proc. Conf. Number Theory. Pullman, WA, 1971, pp. 221-223.

%D R. K. Guy, "Packing [1,n] with solutions of ax + by = cz; the unity of combinatorics," in Colloq. Internaz. Teorie Combinatorie. Rome, 1973, Atti Conv. Lincei. Vol. 17, Part II, pp. 173-179, 1976.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Frank Niedermeyer, <a href="/A002849/b002849.txt">Table of n, a(n) for n = 1..44</a> (first 42 terms from Fausto A. C. Cariboni)

%H R. K. Guy, Letter to N. J. A. Sloane, Jun 24 1971: <a href="/A002572/a002572.jpg">front</a>, <a href="/A002572/a002572_1.jpg">back</a> [Annotated scanned copy, with permission]

%H R. K. Guy, <a href="/A002848/a002848.pdf">Sedlacek's Conjecture on Disjoint Solutions of x+y= z</a>, Univ. Calgary, Dept. Mathematics, Research Paper No. 129, 1971. [Annotated scanned copy, with permission]

%H Richard K. Guy, <a href="http://dx.doi.org/10.1007/978-1-4613-3554-2_9">The unity of combinatorics</a>, in Proc. 25th Iran. Math. Conf., Tehran, (1994), Math. Appl. 329 (1994) 129-159, Kluwer Acad. Publ., Dordrecht, 1995.

%H Christian Hercher and Frank Niedermeyer, <a href="https://arxiv.org/abs/2307.00303">Efficient Calculation the Number of Partitions of the Set {1, 2, ..., 3n} into Subsets {x, y, z} Satisfying x + y = z</a>, arXiv:2307.00303 [math.CO], 2023.

%H Nigel Martin, <a href="http://dx.doi.org/10.1016/0012-365X(94)90168-6">Solving a conjecture of Sedlacek: maximal edge sets in the 3-uniform sumset hypergraphs</a>, Discrete Mathematics, Volume 125, 1994, pp. 273-277.

%H Matheplanet <a href="https://matheplanet.de/default3.html?article=1899">Calculating sequence element a(16) of OEIS A108235</a>

%H R. J. Nowakowski, <a href="/A104429/a104429.pdf">Generalizations of the Langford-Skolem problem</a>, M.S. Thesis, Dept. Math., Univ. Calgary, May 1975. [Scanned copy, with permission.]

%e For n = 3, the unique solution is 1 + 2 = 3.

%e For n = 12, there are 8 solutions:

%e 1 5 6 | 1 5 6 | 2 5 7 | 1 6 7

%e 2 8 10 | 3 7 10 | 3 6 9 | 4 5 9

%e 4 7 11 | 2 9 11 | 1 10 11 | 3 8 11

%e 3 9 12 | 4 8 12 | 4 8 12 | 2 10 12

%e --------+---------+---------+--------

%e 2 4 6 | 2 6 8 | 3 4 7 | 3 5 8

%e 1 9 10 | 4 5 9 | 1 8 9 | 2 7 9

%e 3 8 11 | 3 7 10 | 5 6 11 | 4 6 10

%e 5 7 12 | 1 11 12 | 2 10 12 | 1 11 12

%o (PARI) nxyz(v,t)=local(n,r,x2); r=0; if(t==0,return(1)); for(i3=3*t,#v, n=v[i3]; for(i1=1,i3-2, x2=n-v[i1]; if(x2<=v[i1],break); for(i2=i1+1,i3-1, if(v[i2]>=x2, if(v[i2]==x2, r+=nxyz(vector(i3-3,k,v[if(k<i1,k,if(k<i2-1,k+1,k+2))]),t-1)); break)))); r

%o a(n)=nxyz(vector(n,k,k),n\3-(n%12==6 || n%12==9)) \\ _Franklin T. Adams-Watters_

%Y Cf. A002848, A108235, A161826.

%K nonn

%O 1,4

%A _N. J. A. Sloane_

%E Edited by _N. J. A. Sloane_, Feb 10 2010, based on posting to the Sequence Fans Mailing List by _Franklin T. Adams-Watters_, _R. K. Guy_, _R. H. Hardin_, _Alois P. Heinz_, _Andrew Weimholt_, _Max Alekseyev_ and others

%E a(32)-a(39) from _Max Alekseyev_, Feb 23 2012

%E Definition corrected by _Max Alekseyev_, Nov 16 2012, Jul 06 2023

%E a(40)-a(41) from _Fausto A. C. Cariboni_, Feb 04 2017

%E a(42) from _Fausto A. C. Cariboni_, Mar 12 2017