A131868 -id:A131868 - cp's OEIS frontend

A145855 Number of n-element subsets of {1,2,...,2n-1} whose elements sum to a multiple of n.

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

Offset: 1

T. D. Noe, Oct 21 2008, Oct 22 2008, Oct 24 2008

nonn

It is easy to see that {1,2,...,2n-1} can be replaced by any 2n-1 consecutive numbers and the results will be the same. Erdos, Ginzburg and Ziv proved that every set of 2n-1 numbers -- not necessarily consecutive -- contains a subset of n elements whose sum is a multiple of n.

			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.
L.g.f.: L(x) = x + x^2/2 + 4*x^3/3 + 9*x^4/4 + 26*x^5/5 + 76*x^6/6 + 246*x^7/7 +...
where exponentiation yields the g.f. of A000571:
exp(L(x)) = 1 + x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 22*x^6 + 59*x^7 + 167*x^8 +...

Seiichi Manyama, Table of n, a(n) for n = 1..1669 (terms 1..200 from T. D. Noe)
Max Alekseyev, Proof of Jovovic's formula, 2008.
Michal Bassan, Serte Donderwinkel, and Brett Kolesnik, Tournament score sequences, Erdős-Ginzburg-Ziv numbers, and the Lévy-Khintchine method, arXiv:2407.01441 [math.CO], 2024. See p. 7.
Shane Chern, An extension of a formula of Jovovic, Integers (2019) Vol. 19, Article A47.
Anders Claesson, Mark Dukes, Atli Fannar Franklín, and Sigurður Örn Stefánsson, Counting tournament score sequences, arXiv:2209.03925 [math.CO], 2022.
P. Erdős, A. Ginzburg and A. Ziv, Theorem in the additive number theory, Bull. Res. Council Israel 10 (1961).
Steven Rayan, Aspects of the topology and combinatorics of Higgs bundle moduli spaces, arXiv:1809.05732 [math.AG], 2018.
Mithat Ünsal, Graded Hilbert spaces, quantum distillation and connecting SQCD to QCD, arXiv:2104.12352 [hep-th], 2021.

Cf. A000571, A227532.

Column k=2 of A309148.

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}] (* T. D. Noe, Oct 24 2008 *)

{a(n)=sumdiv(n, d, (-1)^(n+d)*eulerphi(n/d)*binomial(2*d, d)/(2*n))}

{A227532(n, k)=local(G=1); for(i=1, n, G=1+x*subst(G, x, q*x)*G +x*O(x^n)); n*polcoeff(polcoeff(log(G), n, x), k, q)}
{a(n)=sum(k=0,n\2, A227532(n, n*k))} \\ Paul D. Hanna, Jul 17 2013

a(n) = (1/(2*n))*Sum_{d|n} (-1)^(n+d)*phi(n/d)*binomial(2*d,d). Conjectured by Vladeta Jovovic, Oct 22 2008; proved by Max Alekseyev, Oct 23 2008 (see link).
a(2n+1) = A003239(2n+1) and a(2n) = A003239(2n) - A003239(d), where d is the largest odd divisor of n. - T. D. Noe, Oct 24 2008
a(n) = Sum_{d|n} (-1)^(n+d)*d*A131868(d). - Vladeta Jovovic, Oct 28 2008
a(n) = Sum_{k=0..[n/2]} A227532(n,n*k), where A227532 is the logarithmic derivative, wrt x, of the g.f. G(x,q) = 1 + x*G(q*x,q)*G(x,q) of triangle A227543. - Paul D. Hanna, Jul 17 2013
Logarithmic derivative of A000571, the number of different scores that are possible in an n-team round-robin tournament. - Paul D. Hanna, Jul 17 2013
G.f.: -Sum_{m >= 1} (phi(m)/m) * log((1 + sqrt(1 + 4*(-y)^m))/2). - Petros Hadjicostas, Jul 15 2019
a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 28 2023

Extension T. D. Noe, Oct 24 2008

A178904 This should be related to the Coxeter transformations of the posets of partitions in rectangular boxes of size m times n.

Original entry on oeis.org

1, -1, -1, 0, -1, 0, 0, 1, 1, 0, 0, -1, 1, -1, 0, 0, 1, -1, -1, 1, 0, 0, -1, 2, -3, 2, -1, 0, 0, 1, -3, 4, 4, -3, 1, 0, 0, -1, 3, -6, 8, -6, 3, -1, 0, 0, 1, -3, 9, -13, -13, 9, -3, 1, 0, 0, -1, 4, -11, 19, -23, 19, -11, 4, -1, 0, 0, 1, -5, 13, -27, 39, 39, -27, 13, -5, 1, 0, 0, -1, 5, -17, 38, -61, 71, -61, 38, -17, 5, -1, 0

Offset: 0

F. Chapoton, Jun 22 2010

This table is symmetric: a(m,n)=a(n,m) for all m,n>=0.

			a(0,0) = 1, a(1,0) = a(0,1) = -1.
Triangle begins:
   1;
  -1, -1;
   0, -1,  0;
   0,  1,  1,  0;
   0, -1,  1, -1,  0;
   0,  1, -1, -1,  1,  0;
   0, -1,  2, -3,  2, -1, 0;
   ...

G. C. Greubel, Table of n, a(n) for the first 100 rows, flattened

Cf. A178738, A178749, A022553, A131868, A163210.

b[m_, n_] := (-1)^Max[m, n]*Binomial[m+n, n]; A[m_, n_] := DivisorSum[ n+m+1, b[Floor[m/#], Floor[n/#]]*MoebiusMu[#]&]/(m+n+1); Table[A[m-n, n], {m, 0, 12}, {n, 0, m}] // Flatten (* Jean-François Alcover, Feb 23 2017, adapted from Python *)

def twisted_binomial(m, n):
    return (-1)**max(m, n) * binomial(m + n, n)
def coefficients_A(m, n):
    return sum(twisted_binomial(m // d, n // d) * moebius(d)
           for d in divisors(m + n + 1)) / (m + n + 1)
matrix(ZZ, 8, 8, coefficients_A)

Terms a(82) onward added by G. C. Greubel, Dec 10 2017

A254593 a(n) = (3/n^3) * Sum_{d|n} (-1)^(n+d)moebius(n/d)binomial(2*d,d).

Original entry on oeis.org

6, 3, 2, 3, 6, 13, 30, 75, 200, 555, 1590, 4693, 14202, 43863, 137882, 440235, 1424958, 4668304, 15459366, 51692379, 174362770, 592815459, 2030105382, 6998177293, 24270836436, 84646997613, 296744311172, 1045283877639, 3698462401026, 13140509079977, 46869358523238, 167781751129899

Offset: 1

Max Alekseyev, Feb 01 2015

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1650
R. R. Aidagulov, M. A. Alekseyev. On p-adic approximation of sums of binomial coefficients. Journal of Mathematical Sciences 233:5 (2018), 626-634. doi:10.1007/s10958-018-3948-0 arXiv:1602.02632
M. Kontsevich, R. Stanley, O. Gorodetsky, et al. A congruence involving binomial coefficients, Mathoverflow, 2015.

a[n_] := 3/n^3 DivisorSum[n, (-1)^(n+#) MoebiusMu[n/#] Binomial[2#, #]&]; Array[a, 40] (* Jean-François Alcover, Dec 18 2015 *)

{ a(n) = sumdiv(n,d,(-1)^(n+d)*moebius(n/d)*binomial(2*d,d))*3/n^3 }

a(n) = 6*A131868(n)/n.

For n == 0, 1, or 3 (mod 4), a(n) = A268592(n)/2; for n == 2 (mod 4), a(n) = A268592(n)/2 + A268592(n/2)/8.

A178738 Moebius inversion of a sequence related to powers of 2.

Original entry on oeis.org

1, -1, -1, 1, 2, -3, -5, 9, 15, -27, -49, 89, 164, -304, -565, 1057, 1987, -3745, -7085, 13445, 25575, -48771, -93210, 178481, 342392, -657935, -1266205, 2440323, 4709403, -9099507, -17602325, 34087058, 66076421, -128207979, -248983641

Offset: 1

F. Chapoton, Jun 08 2010

Only odd indices make sense. The given sequence is a(1), a(3), a(5), etc.
This should be related to the Coxeter transformations for the posets of diagonally symmetric paths in an n*n grid. - F. Chapoton, Jun 11 2010
Start from 1, 1, -2, -2, -4, -4, 8, 8, 16, 16, -32, -32, -64, -64, 128, ... which is A016116(n-1) with negative signs in blocks of 4, assuming offset 1. The Mobius transform of that sequence is b(n) = 1, 0, -3, -3, -5, -2, 7, 10, 18, 20, -33, -25, -65, -72, 135, 120, ... for n >= 1, and the current sequence is a(n) = b(2n-1)/(2n-1). - R. J. Mathar, Oct 29 2011

			b(1)=1*1; b(3)=-1*3; ...; b(9)=2*9.

Similar to A022553 and A131868

Also related to A178749. - F. Chapoton, Jun 11 2010

A := proc(n)
        (-1)^binomial(floor((n+1)/2),2) * 2^floor((n-1)/2) ;
end proc:
L := [seq(A(n),n=1..40)] ;
b := MOBIUS(L) ;
for i from 1 to nops(b) by 2 do
        printf("%d,", op(i,b)/i) ;
end do: # R. J. Mathar, Oct 29 2011

b[n_] := Sum[(-1)^Binomial[(d+1)/2, 2]*2^((d-1)/2)*MoebiusMu[n/d], {d, Divisors[n]}]/n;
a[n_] := b[2n - 1];
a /@ Range[35] (* Jean-François Alcover, Mar 16 2020 *)

def suite(n):
    return sum((-1)**binomial(((d+1)//2), 2) * 2**((d-1)//2) * moebius(n//d) for d in divisors(n)) // n
[suite(n) for n in range(1,22,2)]

I would like a more precise definition. - N. J. A. Sloane, Jun 08 2010

A178749 n*a(n) provides the Moebius transform of signed central binomial coefficients.

Original entry on oeis.org

1, -1, -1, 1, 1, -1, -3, 4, 8, -13, -23, 39, 71, -121, -229, 400, 757, -1354, -2559, 4625, 8799, -16021, -30671, 56316, 108166, -200047, -385210, 716429, 1383331, -2585173, -5003791, 9391680, 18214565, -34318117, -66674463, 126044208, 245273927, -465067981

Offset: 1

F. Chapoton, Jun 09 2010

sign

This should be related to the Coxeter transformation for the Tamari lattices.

The source sequence is 1, -1, -2, 3, 6, -10, -20, 35, 70, -126, ... (A001405). Its Mobius transform is 1, -2, -3, 4, 5, -6, -21, 32, 72, -130, -253, 468, 923, ... and division of each term through n generates a(n). - R. J. Mathar, Jul 23 2012

			G.f. = x - x^2 - x^3 + x^4 + x^5 - x^6 - 3*x^7 + 4*x^8 + 8*x^9 - 13*x^10 + ...

Alois P. Heinz, Table of n, a(n) for n = 1..1000
F. Chapoton, Le module dendriforme sur le groupe cyclique, Ann. Inst. Fourier (Grenoble) 58 (2008), no. 7, 2333-2350. In French.

Similar to A022553, A131868 and A178738.

Also related to A163210.

with(numtheory):
a:= n-> add(mobius(n/d)*[1$2, -1$2][1+irem(d, 4)]*
        binomial(d-1, iquo(d-1, 2)), d=divisors(n))/n:
seq(a(n), n=1..50);  # Alois P. Heinz, Apr 05 2013

a[ n_] := If[ n < 1, 0, DivisorSum[ n, MoebiusMu[ n/#] (-1)^Quotient[ #, 2] Binomial[ # - 1, Quotient[ # - 1, 2]] &] / n]; (* Michael Somos, Sep 14 2015 *)

{a(n) = if( n<1, 0, sumdiv( n, d, moebius(n/d) * (-1)^(d\2) * binomial(d-1, (d-1)\2)) / n)}; /* Michael Somos, Dec 23 2014 */

def lam(n):
    return (-1)**binomial(n, 2) * binomial(n - 1, (n - 1) // 2)
def a(n):
    return sum(moebius(n // d) * lam(d) for d in divisors(n)) // n
[a(n) for n in range(1, 20)]

cp's OEIS Frontend

A145855 Number of n-element subsets of {1,2,...,2n-1} whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A178904 This should be related to the Coxeter transformations of the posets of partitions in rectangular boxes of size m times n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Extensions

A254593 a(n) = (3/n^3) * Sum_{d|n} (-1)^(n+d)*moebius(n/d)*binomial(2*d,d).

Views

Author

Keywords

Links

Programs

Mathematica

PARI

Formula

A178738 Moebius inversion of a sequence related to powers of 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Sage

Extensions

A178749 n*a(n) provides the Moebius transform of signed central binomial coefficients.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

A254593 a(n) = (3/n^3) * Sum_{d|n} (-1)^(n+d)moebius(n/d)binomial(2*d,d).