cp's OEIS Frontend

A065795 Number of subsets of {1,2,...,n} that contain the average of their elements.

%I A065795 #44 May 01 2025 01:35:59
%S A065795 1,2,4,6,10,16,26,42,72,124,218,390,706,1292,2388,4436,8292,15578,
%T A065795 29376,55592,105532,200858,383220,732756,1403848,2694404,5179938,
%U A065795 9973430,19229826,37125562,71762396,138871260,269021848,521666984,1012520400,1966957692,3824240848
%N A065795 Number of subsets of {1,2,...,n} that contain the average of their elements.
%C A065795 Also the number of subsets of {1,2,...,n} with sum of entries divisible by the largest element (compare A000016). See the Palmer Melbane link for a bijection. - _Joel B. Lewis_, Nov 13 2014
%H A065795 Alois P. Heinz, <a href="/A065795/b065795.txt">Table of n, a(n) for n = 1..3333</a>
%H A065795 Palmer Melbane, <a href="https://artofproblemsolving.com/community/c6h610573p3631416">Combinations under constraint</a>, Art of Problem Solving thread. - _Joel B. Lewis_, Nov 13 2014
%F A065795 a(n) = (1/2)*Sum_{i=1..n} (f(i) - 1) where f(i) = (1/i) * Sum_{d | i and d is odd} 2^(i/d) * phi(d).
%F A065795 a(n) = (n + A051293(n))/2.
%F A065795 a(n) = 2^n - A327471(n). - _Gus Wiseman_, Sep 14 2019
%e A065795 a(4)=6, since {1}, {2}, {3}, {4}, {1,2,3} and {2,3,4} contain their averages.
%e A065795 From _Gus Wiseman_, Sep 14 2019: (Start)
%e A065795 The a(1) = 1 through a(6) = 16 subsets:
%e A065795   {1}  {1}  {1}      {1}      {1}          {1}
%e A065795        {2}  {2}      {2}      {2}          {2}
%e A065795             {3}      {3}      {3}          {3}
%e A065795             {1,2,3}  {4}      {4}          {4}
%e A065795                      {1,2,3}  {5}          {5}
%e A065795                      {2,3,4}  {1,2,3}      {6}
%e A065795                               {1,3,5}      {1,2,3}
%e A065795                               {2,3,4}      {1,3,5}
%e A065795                               {3,4,5}      {2,3,4}
%e A065795                               {1,2,3,4,5}  {2,4,6}
%e A065795                                            {3,4,5}
%e A065795                                            {4,5,6}
%e A065795                                            {1,2,3,6}
%e A065795                                            {1,4,5,6}
%e A065795                                            {1,2,3,4,5}
%e A065795                                            {2,3,4,5,6}
%e A065795 (End)
%t A065795 Table[ Sum[a = Select[Divisors[i], OddQ[ # ] &]; Apply[ Plus, 2^(i/a) * EulerPhi[a]]/i, {i, n}]/2, {n, 34}]
%t A065795 (* second program *)
%t A065795 Table[Length[Select[Subsets[Range[n]],MemberQ[#,Mean[#]]&]],{n,0,10}] (* _Gus Wiseman_, Sep 14 2019 *)
%o A065795 (PARI) a(n) = (1/2)*sum(i=1, n, (1/i)*sumdiv(i, d, if (d%2, 2^(i/d)*eulerphi(d)))); \\ _Michel Marcus_, Dec 20 2020
%o A065795 (Python)
%o A065795 from sympy import totient, divisors
%o A065795 def A065795(n): return sum((sum(totient(d)<<k//d-1 for d in divisors(k>>(~k&k-1).bit_length(),generator=True))<<1)//k for k in range(1,n+1))>>1 # _Chai Wah Wu_, Feb 22 2023
%Y A065795 Subsets containing n whose mean is an element are A000016.
%Y A065795 The version for integer partitions is A237984.
%Y A065795 Subsets not containing their mean are A327471.
%Y A065795 Cf. A051293, A063776, A066571, A135342, A324736, A325705, A326083, A326836, A327478, A327481.
%K A065795 nonn
%O A065795 1,2
%A A065795 _John W. Layman_, Dec 05 2001
%E A065795 Edited and extended by _Robert G. Wilson v_, Nov 15 2002