|
%I #74 Jul 04 2023 09:30:14
%S 1,1,0,0,8,21,0,0,3040,20505,0,0,10567748,103372655,0,0,142664107305,
%T 1836652173363,0,0
%N Number of partitions of {1,2,...,3n} into n triples (X,Y,Z) each satisfying X+Y=Z.
%C a(0)=1 by convention.
%H Matthias Beck and Thomas Zaslavsky, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Zaslavsky/sls.html">Six Little Squares and How their Numbers Grow</a>, Journal of Integer Sequences, 13 (2010), #10.6.2.
%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 Matroids 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.]
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Dancing_Links">Dancing Links</a>
%F a(n) = 0 unless n == 0 or 1 (mod 4). For n == 0 or 1 (mod 4), a(n) = A002849(3n). See A002849 for references and further information.
%e For m = 1 the unique solution is 1 + 2 = 3.
%e For m = 4 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
%e .
%e The 8 solutions for m = 4, one per line:
%e (1, 5, 6), (2, 8, 10), (3, 9, 12), (4, 7, 11);
%e (1, 5, 6), (2, 9, 11), (3, 7, 10), (4, 8, 12);
%e (1, 10, 11), (2, 5, 7), (3, 6, 9), (4, 8, 12);
%e (1, 6, 7), (2, 10, 12), (3, 8, 11), (4, 5, 9);
%e (1, 9, 10), (2, 4, 6), (3, 8, 11), (5, 7, 12);
%e (1, 11, 12), (2, 6, 8), (3, 7, 10), (4, 5, 9);
%e (1, 8, 9), (2, 10, 12), (3, 4, 7), (5, 6, 11);
%e (1, 11, 12), (2, 7, 9), (3, 5, 8), (4, 6, 10).
%t Table[Length[Select[Subsets[Select[Subsets[Range[3 n], {3}], #[[1]] + #[[2]] == #[[3]] &], {n}], Range[3 n] == Sort[Flatten[#]] &]], {n, 0,
%t 5}] (* Suitable only for n<6. See Knuth's Dancing Links algorithm for n>5. *) (* _Robert Price_, Apr 03 2019 *)
%o (Sage) A = lambda n:sum(1 for t in DLXCPP([(a-1,b-1,a+b-1) for a in (1..3*n) for b in (1..min(3*n-a,a-1))])) # _Tomas Boothby_, Oct 11 2013
%Y Cf. A002848, A002849, A161826, A202951, A202952.
%K nonn,more
%O 0,5
%A _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_ and others.
%E a(12) from _R. H. Hardin_, Feb 11 2010
%E a(12) confirmed and a(13) computed (using Knuth's dancing links algorithm) by _Alois P. Heinz_, Feb 11 2010
%E a(13) confirmed by _Tomas Boothby_, Oct 11 2013
%E a(16) from _Frank Niedermeyer_, Apr 19 2020
%E a(17)-a(19) from _Frank Niedermeyer_, May 02 2020
|
