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

1, 2, 4, 6, 10, 16, 26, 42, 72, 124, 218, 390, 706, 1292, 2388, 4436, 8292, 15578, 29376, 55592, 105532, 200858, 383220, 732756, 1403848, 2694404, 5179938, 9973430, 19229826, 37125562, 71762396, 138871260, 269021848, 521666984, 1012520400, 1966957692, 3824240848

Offset

1,2

Comments

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

Links

Alois P. Heinz, Table of n, a(n) for n = 1..3333

Palmer Melbane, Art of Problem Solving thread. - Joel B. Lewis, Nov 13 2014

Formula

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

a(n) = (n + A051293(n))/2.

a(n) = 2^n - A327471(n). - Gus Wiseman, Sep 14 2019

Example

a(4)=6, since {1}, {2}, {3}, {4}, {1,2,3} and {2,3,4} contain their averages.
From Gus Wiseman, Sep 14 2019: (Start)
The a(1) = 1 through a(6) = 16 subsets:
  {1}  {1}  {1}      {1}      {1}          {1}
       {2}  {2}      {2}      {2}          {2}
            {3}      {3}      {3}          {3}
            {1,2,3}  {4}      {4}          {4}
                     {1,2,3}  {5}          {5}
                     {2,3,4}  {1,2,3}      {6}
                              {1,3,5}      {1,2,3}
                              {2,3,4}      {1,3,5}
                              {3,4,5}      {2,3,4}
                              {1,2,3,4,5}  {2,4,6}
                                           {3,4,5}
                                           {4,5,6}
                                           {1,2,3,6}
                                           {1,4,5,6}
                                           {1,2,3,4,5}
                                           {2,3,4,5,6}
(End)

Mathematica

Table[ Sum[a = Select[Divisors[i], OddQ[ # ] &]; Apply[ Plus, 2^(i/a) * EulerPhi[a]]/i, {i, n}]/2, {n, 34}]
(* second program *)
Table[Length[Select[Subsets[Range[n]], MemberQ[#, Mean[#]]&]], {n, 0, 10}] (* Gus Wiseman, Sep 14 2019 *)

Prog

(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
(Python)
from sympy import totient, divisors
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

Crossrefs

Subsets containing n whose mean is an element are A000016.

The version for integer partitions is A237984.

Subsets not containing their mean are A327471.

Cf. A051293, A063776, A066571, A135342, A324736, A325705, A326083, A326836, A327478, A327481.

Sequence in context: A023613 A306293 A307795 * A293077 A000801 A080105

Adjacent sequences: A065792 A065793 A065794 * A065796 A065797 A065798

Keyword

nonn

Author

John W. Layman, Dec 05 2001

Extensions

Edited and extended by Robert G. Wilson v, Nov 15 2002

Status

approved