|
| |
|
|
A051293
|
|
Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.
|
|
106
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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
|
|
|
LINKS
|
63rd Annual William Lowell Putnam Mathematical Competition, Problem A3, Mathematics Magazine 76 (2003), 76-80.
|
|
|
FORMULA
|
a(n) = Sum_{i=1..n} (A063776(i) - 1).
|
|
|
EXAMPLE
|
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.
|
|
|
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:
|
|
|
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 *)
|
|
|
PROG
|
(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//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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
