A290889 Number of partitions of the set of odd numbers {1, 3, ..., 2*n-1} into two subsets such that the absolute difference of the sums of the two subsets is minimized.

1, 1, 1, 1, 2, 1, 5, 4, 13, 10, 38, 34, 118, 103, 380, 346, 1262, 1153, 4277, 3965, 14745, 13746, 51541, 48396, 182182, 171835, 650095, 615966, 2338706, 2223755, 8472697, 8082457, 30884150, 29543309, 113189168, 108545916, 416839177, 400623807, 1541726967

Offset: 1

Author

Hugo Pfoertner, Aug 13 2017

Keywords

• nonn

Comments

Partitioning in equal sums is only possible for n = 4*k-1, k > 1, and the number of such partitions is given by A156700. For the set {1,3} and the other values of n, i.e., for the sets {1,3,5}, {1,3,5,7,9}, {1,3,5,7,9,11,13}, one can use the criterion to split the sets "as well as possible" by choosing those partitions for which the absolute value of the difference of the respective sums of the subset members achieves its minimum.

Examples

			a(1) = 1: {}U{1} with difference 1.
a(2) = 1: {1}U{3} with difference 2.
a(3) = 1: {1,3}U{5} with difference 1.
a(4) = 1 = A156700(2): {1,7}U{3,5} with difference 0.
a(5) = 2: {1,3,9}U{5,7} and {1,5,7}U{3,9} with |difference|=1.
a(6) = 1 = A156700(3): {1,3,5,9}U{7,11} with difference 0.
a(7) = 5: {1,3,5,7,9}U{11,13}, {1,3,9,11}U{5,7,13}, {1,5,7,11}U{3,9,13},
          {1,11,13}U{3,5,7,9}, {1,3,7,13}U{5,9,11} with |difference|=1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A005408, A058377, A069918, A156700.

Programs

Maple

b:= proc(n, i) option remember; `if`(n>i^2, 0,
      `if`(n=i^2, 1, b(abs(n-2*i+1), i-1)+b(n+2*i-1, i-1)))
    end:
a:= n-> `if`(n<5, 1, (t-> b(t, n)/(2-t))(irem(n, 2))):
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 14 2017

Mathematica

b[n_, i_] := b[n, i] = If[n > i^2, 0, If[n == i^2, 1, b[Abs[n - 2i + 1], i - 1] + b[n + 2i - 1, i - 1]]];
a[n_] := If[n < 5, 1, b[#, n]/(2-#)&[Mod[n, 2]]];
Array[a, 50] (* Jean-François Alcover, Nov 14 2020, after Alois P. Heinz *)

Formula

a(n) ~ (3 - (-1)^n) * sqrt(3) * 2^(n - 5/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 18 2017