|
| |
|
|
A145855
|
|
Number of n-member subsets of 1..2n-1 whose elements sum to a multiple of n.
|
|
3
| |
|
|
1, 1, 4, 9, 26, 76, 246, 809, 2704, 9226, 32066, 112716, 400024, 1432614, 5170604, 18784169, 68635478, 252085792, 930138522, 3446167834, 12815663844, 47820414962, 178987624514, 671825133644, 2528212128776, 9536894664376
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| It is easy to see that 1..2n-1 can be replaced by any 2n-1 consecutive numbers and the results will be the same. Erdos, Ginzburg and Ziv prove that every set of 2n-1 numbers -- not necessarily consecutive -- contains a subset of n elements whose sum is a multiple of n.
|
|
|
REFERENCES
| P. Erdos, A. Ginzburg and A. Ziv: Theorem in the additive number theory, Bull. Res. Council Israel 10 (1961).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=1..200
Max Alekseyev, Proof of Jovovic's conjecture
|
|
|
FORMULA
| Conjecture: a(n) = (1/(2*n))*Sum_{d|n} (-1)^(n+d)*phi(n/d)*binomial(2*d,d). [From Vladeta Jovovic (vladeta(AT)eunet.yu), Oct 22 2008]. The conjecture is true - see the Alekseyev link.
a(2n+1) = A003239(2n+1) and a(2n) = A003239(2n) - A003239(d), where d is the largest odd divisor of n. [From T. D. Noe (noe(AT)sspectra.com), Oct 24 2008]
a(n) = Sum_{d|n} (-1)^(n+d)*d*A131868(d). [From Vladeta Jovovic (vladeta(AT)eunet.yu), Oct 28 2008]
|
|
|
EXAMPLE
| a(3)=4 because, of the 10 3-element subsets of 1..7, only {1,2,3}, {1,3,5}, {2,3,4} and {3,4,5} have sums that are multiples of 3.
|
|
|
MATHEMATICA
| Table[Length[Select[Plus@@@Subsets[Range[2n-1], {n}], Mod[ #, n]==0&]], {n, 10}]
Table[d=Divisors[n]; Sum[(-1)^(n+d[[i]]) EulerPhi[n/d[[i]]] Binomial[2d[[i]], d[[i]]]/2/n, {i, Length[d]}], {n, 30}] [From T. D. Noe (noe(AT)sspectra.com), Oct 24 2008]
|
|
|
CROSSREFS
| Sequence in context: A090117 A020181 A113682 * A099615 A114618 A067758
Adjacent sequences: A145852 A145853 A145854 * A145856 A145857 A145858
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| T. D. Noe (noe(AT)sspectra.com), Oct 21 2008, Oct 22 2008, Oct 24 2008
|
|
|
EXTENSIONS
| Extension T. D. Noe (noe(AT)sspectra.com), Oct 24 2008
|
| |
|
|
