cp's OEIS Frontend

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

%I A108235 #76 Jul 09 2025 04:25:18
%S A108235 1,1,0,0,8,21,0,0,3040,20505,0,0,10567748,103372655,0,0,142664107305,
%T A108235 1836652173363,0,0
%N A108235 Number of partitions of {1,2,...,3n} into n triples (X,Y,Z) each satisfying X+Y=Z.
%C A108235 a(0)=1 by convention.
%H A108235 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 A108235 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 A108235 Matroids Matheplanet, <a href="https://matheplanet.de/default3.html?article=1899">Calculating sequence element a(16) of OEIS A108235</a>
%H A108235 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 A108235 Wikipedia, <a href="https://en.wikipedia.org/wiki/Dancing_Links">Dancing Links</a>
%F A108235 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 A108235 For m = 1 the unique solution is 1 + 2 = 3.
%e A108235 For m = 4 there are 8 solutions:
%e A108235   1  5  6 | 1  5  6 | 2  5  7 | 1  6  7
%e A108235   2  8 10 | 3  7 10 | 3  6  9 | 4  5  9
%e A108235   4  7 11 | 2  9 11 | 1 10 11 | 3  8 11
%e A108235   3  9 12 | 4  8 12 | 4  8 12 | 2 10 12
%e A108235   --------+---------+---------+--------
%e A108235   2  4  6 | 2  6  8 | 3  4  7 | 3  5  8
%e A108235   1  9 10 | 4  5  9 | 1  8  9 | 2  7  9
%e A108235   3  8 11 | 3  7 10 | 5  6 11 | 4  6 10
%e A108235   5  7 12 | 1 11 12 | 2 10 12 | 1 11 12
%e A108235 .
%e A108235 The 8 solutions for m = 4, one per line:
%e A108235   (1,  5,  6), (2,  8, 10), (3,  9, 12), (4,  7, 11);
%e A108235   (1,  5,  6), (2,  9, 11), (3,  7, 10), (4,  8, 12);
%e A108235   (1, 10, 11), (2,  5,  7), (3,  6,  9), (4,  8, 12);
%e A108235   (1,  6,  7), (2, 10, 12), (3,  8, 11), (4,  5,  9);
%e A108235   (1,  9, 10), (2,  4,  6), (3,  8, 11), (5,  7, 12);
%e A108235   (1, 11, 12), (2,  6,  8), (3,  7, 10), (4,  5,  9);
%e A108235   (1,  8,  9), (2, 10, 12), (3,  4,  7), (5,  6, 11);
%e A108235   (1, 11, 12), (2,  7,  9), (3,  5,  8), (4,  6, 10).
%t A108235 Table[Length[Select[Subsets[Select[Subsets[Range[3 n], {3}], #[[1]] + #[[2]] == #[[3]] &], {n}], Range[3 n] == Sort[Flatten[#]] &]], {n, 0,
%t A108235 5}]  (* Suitable only for n<6. See Knuth's Dancing Links algorithm for n>5. *) (* _Robert Price_, Apr 03 2019 *)
%o A108235 (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 A108235 Cf. A002848, A002849, A161826, A202951, A202952.
%K A108235 nonn,more
%O A108235 0,5
%A A108235 _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 A108235 a(12) from _R. H. Hardin_, Feb 11 2010
%E A108235 a(12) confirmed and a(13) computed (using Knuth's dancing links algorithm) by _Alois P. Heinz_, Feb 11 2010
%E A108235 a(13) confirmed by _Tomas Boothby_, Oct 11 2013
%E A108235 a(16) from _Frank Niedermeyer_, Apr 19 2020
%E A108235 a(17)-a(19) from _Frank Niedermeyer_, May 02 2020