|
%I #43 Jan 12 2024 16:47:24
%S 1,2,5,8,15,26,45,76,135,238,425,768,1399,2570,4761,8856,16567,31138,
%T 58733,111164,211043,401694,766417,1465488,2807671,5388782,10359849,
%U 19946832,38459623,74251094,143524761,277742488,538043663,1043333934,2025040765,3933915348
%N Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.
%C 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
%C A082550(n) = a(n+1) - a(n). - _Reinhard Zumkeller_, Feb 19 2006
%H Alois P. Heinz, <a href="/A051293/b051293.txt">Table of n, a(n) for n = 1..3332</a> (first 300 terms from T. D. Noe)
%H 63rd Annual William Lowell Putnam Mathematical Competition, <a href="http://www.jstor.org/stable/3219137">Problem A3</a>, Mathematics Magazine 76 (2003), 76-80.
%F a(n) = Sum_{i=1..n} (A063776(i) - 1).
%e 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.
%p with(numtheory):
%p b:= n-> add(2^(n/d)*phi(d), d=select(x-> x::odd, divisors(n)))/n:
%p a:= proc(n) option remember; `if`(n<1, 0, b(n)-1+a(n-1)) end:
%p seq(a(n), n=1..40); # _Alois P. Heinz_, Jul 15 2019
%t Table[ Sum[a = Select[Divisors[i], OddQ[ # ] & ]; Apply[Plus, 2^(i/a)*EulerPhi[a]]/i, {i, n}] - n, {n, 34}]
%t Table[Count[Subsets[Range[n]],_?(IntegerQ[Mean[#]]&)],{n,35}] (* _Harvey P. Dale_, Apr 14 2018 *)
%o (PARI) a(n)=sum(k=1,n,sumdiv(k,d,d%2*2^(k/d)*eulerphi(d))/k-1)
%o (Python)
%o from sympy import totient, divisors
%o def A051293(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))-n # _Chai Wah Wu_, Feb 22 2023
%Y Row sums of A061865 and A327481.
%Y Cf. A000629, A000670, A082550, A114976.
%K nonn,nice
%O 1,2
%A _John W. Layman_, Oct 30 1999
%E Extended by _Robert G. Wilson v_, Oct 16 2002
|
