cp's OEIS Frontend

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

%I A304011 #114 Sep 15 2020 06:51:42
%S A304011 0,0,0,1,5,20,70,231,735,2289,7029,21384,64636,194480,583232,1744847,
%T A304011 5210687,15540023,46299143,137837666,410127806,1219804541,3626853647,
%U A304011 10781440394,32045015650,95236794600,283027305300,841096898745,2499595030581,7428627412260
%N A304011 Number of same-sized pairs of subsets of set of n numbers that might have the same sum.
%C A304011 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.
%H A304011 Michael De Vlieger, <a href="/A304011/b304011.txt">Table of n, a(n) for n = 1..2100</a>
%H A304011 Jean-Luc Baril, Richard Genestier, Sergey Kirgizov, <a href="https://arxiv.org/abs/1911.03119">Pattern distributions in Dyck paths with a first return decomposition constrained by height</a>, arXiv:1911.03119 [math.CO], 2019.
%H A304011 Project Euler, <a href="https://projecteuler.net/problem=106">Problem 106: Special subset sums: meta-testing</a>
%F A304011 a(n) = Sum_{i=1..floor(n/2)} binomial(n, 2*i)*A002054(i-1).
%F A304011 From _Vaclav Kotesovec_, Aug 04 2018: (Start)
%F A304011 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.
%F A304011 a(n) ~ 3^(n + 1/2) / (4*sqrt(Pi*n)). (End)
%t A304011 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 *)
%t A304011 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 *)
%o A304011 (APL- NARS200 dialect) +/{((2×⍵)!n)×(⍵-2)!1+2×⍵-1}¨1..n÷2
%o A304011 (PARI) a(n) = sum(i=1, n\2, binomial(n, 2*i)*binomial(2*i-1, i-2)); \\ _Michel Marcus_, Jul 04 2018
%Y A304011 Cf. A002054.
%K A304011 nonn
%O A304011 1,5
%A A304011 _Michael Turniansky_, Jul 03 2018
%E A304011 a(23) corrected by _Georg Fischer_, Dec 06 2019