login
A108235
Number of partitions of {1,2,...,3n} into n triples (X,Y,Z) each satisfying X+Y=Z.
10
1, 1, 0, 0, 8, 21, 0, 0, 3040, 20505, 0, 0, 10567748, 103372655, 0, 0, 142664107305, 1836652173363, 0, 0
OFFSET
0,5
COMMENTS
a(0)=1 by convention.
LINKS
Matthias Beck and Thomas Zaslavsky, Six Little Squares and How their Numbers Grow, Journal of Integer Sequences, 13 (2010), #10.6.2.
Christian Hercher and Frank Niedermeyer, Efficient Calculation the Number of Partitions of the Set {1,2,...,3n} into Subsets {x,y,z} Satisfying x+y=z, arXiv:2307.00303 [math.CO], 2023.
R. J. Nowakowski, Generalizations of the Langford-Skolem problem, M.S. Thesis, Dept. Math., Univ. Calgary, May 1975. [Scanned copy, with permission.]
Wikipedia, Dancing Links
FORMULA
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.
EXAMPLE
For m = 1 the unique solution is 1 + 2 = 3.
For m = 4 there are 8 solutions:
1 5 6 | 1 5 6 | 2 5 7 | 1 6 7
2 8 10 | 3 7 10 | 3 6 9 | 4 5 9
4 7 11 | 2 9 11 | 1 10 11 | 3 8 11
3 9 12 | 4 8 12 | 4 8 12 | 2 10 12
--------+---------+---------+--------
2 4 6 | 2 6 8 | 3 4 7 | 3 5 8
1 9 10 | 4 5 9 | 1 8 9 | 2 7 9
3 8 11 | 3 7 10 | 5 6 11 | 4 6 10
5 7 12 | 1 11 12 | 2 10 12 | 1 11 12
.
The 8 solutions for m = 4, one per line:
(1, 5, 6), (2, 8, 10), (3, 9, 12), (4, 7, 11);
(1, 5, 6), (2, 9, 11), (3, 7, 10), (4, 8, 12);
(1, 10, 11), (2, 5, 7), (3, 6, 9), (4, 8, 12);
(1, 6, 7), (2, 10, 12), (3, 8, 11), (4, 5, 9);
(1, 9, 10), (2, 4, 6), (3, 8, 11), (5, 7, 12);
(1, 11, 12), (2, 6, 8), (3, 7, 10), (4, 5, 9);
(1, 8, 9), (2, 10, 12), (3, 4, 7), (5, 6, 11);
(1, 11, 12), (2, 7, 9), (3, 5, 8), (4, 6, 10).
MATHEMATICA
Table[Length[Select[Subsets[Select[Subsets[Range[3 n], {3}], #[[1]] + #[[2]] == #[[3]] &], {n}], Range[3 n] == Sort[Flatten[#]] &]], {n, 0,
5}] (* Suitable only for n<6. See Knuth's Dancing Links algorithm for n>5. *) (* Robert Price, Apr 03 2019 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,more
AUTHOR
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.
EXTENSIONS
a(12) from R. H. Hardin, Feb 11 2010
a(12) confirmed and a(13) computed (using Knuth's dancing links algorithm) by Alois P. Heinz, Feb 11 2010
a(13) confirmed by Tomas Boothby, Oct 11 2013
a(16) from Frank Niedermeyer, Apr 19 2020
a(17)-a(19) from Frank Niedermeyer, May 02 2020
STATUS
approved