A304011 Number of same-sized pairs of subsets of set of n numbers that might have the same sum.

0, 0, 0, 1, 5, 20, 70, 231, 735, 2289, 7029, 21384, 64636, 194480, 583232, 1744847, 5210687, 15540023, 46299143, 137837666, 410127806, 1219804541, 3626853647, 10781440394, 32045015650, 95236794600, 283027305300, 841096898745, 2499595030581, 7428627412260

Offset: 1

Author

Michael Turniansky, Jul 03 2018

Keywords

• nonn

Comments

Given a set with n different numbers, you only need to check a(n) pairs of subsets of the same cardinality to prove that no pair of same-cardinality subsets have the same total sum. The others can be eliminated by noting the dominance of members of one totally-ordered subset over the corresponding elements of the other totally-ordered subset.

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..2100
• Jean-Luc Baril, Richard Genestier, Sergey Kirgizov, Pattern distributions in Dyck paths with a first return decomposition constrained by height, arXiv:1911.03119 [math.CO], 2019.
• Project Euler, Problem 106: Special subset sums: meta-testing

Crossrefs

Cf. A002054.

Programs

Mathematica

Table[1/2 + Hypergeometric2F1[(1 - n)/2, -n/2, 1, 4]/2 - Hypergeometric2F1[(1 - n)/2, -n/2, 2, 4], {n, 1, 30}] (* Vaclav Kotesovec, Aug 04 2018 *)
Join[{0,0,0,1},RecurrenceTable[{(n-4)*(n+2)*a[n]==(3*n^2-7*n-5)*a[n-1]+ (n-3)*(n-1)*a[n-2]-3*(n-2)*(n-1)*a[n-3],a[2]==0,a[3]==0,a[4]==1},a,{n,5,25}]] (* Georg Fischer, Dec 06 2019 *)

PARI

a(n) = sum(i=1, n\2, binomial(n, 2*i)*binomial(2*i-1, i-2)); \\ Michel Marcus, Jul 04 2018

Formula

a(n) = Sum_{i=1..floor(n/2)} binomial(n, 2*i)*A002054(i-1).

From Vaclav Kotesovec, Aug 04 2018: (Start)

D-finite with recurrence: (n-4)*(n+2)*a(n) = (3*n^2 - 7*n - 5)*a(n-1) + (n-3)*(n-1)*a(n-2) - 3*(n-2)*(n-1)*a(n-3) for n >= 5.

a(n) ~ 3^(n + 1/2) / (4*sqrt(Pi*n)). (End)

Extensions

a(23) corrected by Georg Fischer, Dec 06 2019