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,5

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

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)

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

Prog

(APL- NARS200 dialect) +/{((2×⍵)!n)×(⍵-2)!1+2×⍵-1}¨1..n÷2
(PARI) a(n) = sum(i=1, n\2, binomial(n, 2*i)*binomial(2*i-1, i-2)); \\ Michel Marcus, Jul 04 2018

Crossrefs

Cf. A002054.

Sequence in context: A169792 A000343 A005324 * A243869 A154638 A054889

Adjacent sequences: A304008 A304009 A304010 * A304012 A304013 A304014

Keyword

nonn

Author

Michael Turniansky, Jul 03 2018

Extensions

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

Status

approved