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
KEYWORD
nonn
AUTHOR
Michael Turniansky, Jul 03 2018
EXTENSIONS
a(23) corrected by Georg Fischer, Dec 06 2019
STATUS
approved