A108235 Number of partitions of {1,2,...,3n} into n triples (X,Y,Z) each satisfying X+Y=Z.

1, 1, 0, 0, 8, 21, 0, 0, 3040, 20505, 0, 0, 10567748, 103372655, 0, 0, 142664107305, 1836652173363, 0, 0

Offset: 0

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

Keywords

• nonn
• more

Comments

a(0)=1 by convention.

Examples

			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).
		

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.
• Matroids Matheplanet, Calculating sequence element a(16) of OEIS A108235
• 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

Crossrefs

Cf. A002848, A002849, A161826, A202951, A202952.

Programs

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 *)

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

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.

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