A051293 Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.

1, 2, 5, 8, 15, 26, 45, 76, 135, 238, 425, 768, 1399, 2570, 4761, 8856, 16567, 31138, 58733, 111164, 211043, 401694, 766417, 1465488, 2807671, 5388782, 10359849, 19946832, 38459623, 74251094, 143524761, 277742488, 538043663, 1043333934, 2025040765, 3933915348

Offset: 1

Author

John W. Layman, Oct 30 1999

Keywords

• nonn
• nice

Comments

a(n) is asymptotic to 2^(n+1)/n. More precisely, I conjecture for any m > 0, a(n) = 2^(n+1)/n * Sum_{k=0..m} A000670(k)/n^k + o(1/n^(m+1)) (A000670 = preferential arrangements of n labeled elements) which can be written a(n) = 2^n/n * 2 + Sum_{k=1..m} A000629(k)/n^k + o(1/n^(m+1)) (A000629 = necklaces of sets of labeled beads). In fact I conjecture that a(n) = 2^(n+1)/n * (1 + 1/n + 3/n^2 + 13/n^3 + 75/n^4 + 541/n^5 + o(1/n^5)). - Benoit Cloitre, Oct 20 2002

A082550(n) = a(n+1) - a(n). - Reinhard Zumkeller, Feb 19 2006

Examples

			a(4) = 8 because each of the 8 subsets {1}, {2}, {3}, {4}, {1,3}, {2,4}, {1,2,3}, {2,3,4} has an integer average.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..3332 (first 300 terms from T. D. Noe)
• 63rd Annual William Lowell Putnam Mathematical Competition, Problem A3, Mathematics Magazine 76 (2003), 76-80.

Crossrefs

Row sums of A061865 and A327481.

Cf. A000629, A000670, A082550, A114976.

Programs

Maple

with(numtheory):
b:= n-> add(2^(n/d)*phi(d), d=select(x-> x::odd, divisors(n)))/n:
a:= proc(n) option remember; `if`(n<1, 0, b(n)-1+a(n-1)) end:
seq(a(n), n=1..40);  # Alois P. Heinz, Jul 15 2019

Mathematica

Table[ Sum[a = Select[Divisors[i], OddQ[ # ] & ]; Apply[Plus, 2^(i/a)*EulerPhi[a]]/i, {i, n}] - n, {n, 34}]
Table[Count[Subsets[Range[n]],?(IntegerQ[Mean[#]]&)],{n,35}] (* _Harvey P. Dale, Apr 14 2018 *)

PARI

a(n)=sum(k=1,n,sumdiv(k,d,d%2*2^(k/d)*eulerphi(d))/k-1)

Python

from sympy import totient, divisors
def A051293(n): return sum((sum(totient(d)<>(~k&k-1).bit_length(),generator=True))<<1)//k for k in range(1,n+1))-n # Chai Wah Wu, Feb 22 2023

Formula

a(n) = Sum_{i=1..n} (A063776(i) - 1).

Extensions

Extended by Robert G. Wilson v, Oct 16 2002