A169888 -id:A169888 - cp's OEIS frontend

A119358 Number of n-element subsets of [2n] having an even sum.

1, 1, 2, 10, 38, 126, 452, 1716, 6470, 24310, 92252, 352716, 1352540, 5200300, 20056584, 77558760, 300546630, 1166803110, 4537543340, 17672631900, 68923356788, 269128937220, 1052049129144, 4116715363800, 16123803193628, 63205303218876, 247959261273752

Offset: 0

Paul Barry, May 16 2006

Old name was: Central coefficients of number triangle A119326.

			a(3) = 10: {1,2,3}, {1,2,5}, {1,3,4}, {1,3,6}, {1,4,5}, {1,5,6}, {2,3,5}, {2,4,6}, {3,4,5}, {3,5,6}. - _Alois P. Heinz_, Feb 04 2017

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A071688, A119326, A119359, A169888, A282011.

Column k=2 of A318557.

a:= proc(n) option remember; `if`(n<3, 1+n*(n-1)/2,
     ((4*n-10)*(5*n^2-10*n+4)*(a(n-1)+4*(n-2)*a(n-3)
      /(n-1))/(5*n^2-20*n+19)-4*(n-1)*a(n-2))/n)
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 26 2018

Table[HypergeometricPFQ[{1/2 - n/2, 1/2 - n/2, -n/2, -n/2}, {1/2, 1/2, 1}, 1], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 04 2016 *)

G.f.: (1/sqrt(1-4x)+1/sqrt(1+4x^2))/2.
a(n) = Sum_{k=0..floor(n/2)} C(n,2k)^2.
a(n) = C(2n,n)/2+sin(Pi*(n+1)/2)*C(n,n/2)/2.
a(n) = A119326(2n,n).
a(n) = A071688(n) + A119359(n) for n>=1.
D-finite with recurrence n*(n-1)*(10*n-29)*a(n) +2*(n-1)*(5*n^2-74*n+164)*a(n-1) +4*(-40*n^3+310*n^2 -744*n+559)*a(n-2) +8*(n-2)*(5*n^2-74*n+164)*a(n-3) -16*(25*n-42)*(n-3)*(2*n-7)*a(n-4)=0. - R. J. Mathar, Nov 05 2012
a(n) = hypergeom([(1-n)/2, (1-n)/2, -n/2, -n/2], [1/2, 1/2, 1], 1). - Vladimir Reshetnikov, Oct 04 2016
a(n) = A282011(2n,n). - Alois P. Heinz, Feb 04 2017

New name from Alois P. Heinz, Feb 04 2017

A304482 Number A(n,k) of n-element subsets of [k*n] whose elements sum to a multiple of n. Square array A(n,k) with n, k >= 0 read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 1, 0, 1, 4, 6, 8, 0, 0, 1, 5, 12, 30, 18, 1, 0, 1, 6, 20, 76, 126, 52, 0, 0, 1, 7, 30, 155, 460, 603, 152, 1, 0, 1, 8, 42, 276, 1220, 3104, 3084, 492, 0, 0, 1, 9, 56, 448, 2670, 10630, 22404, 16614, 1618, 1, 0, 1, 10, 72, 680, 5138, 28506, 98900, 169152, 91998, 5408, 0, 0

Offset: 0

Marko Riedel, Aug 28 2018

When k=1 the only subset of [n] with n elements is [n] which sums to n(n+1)/2 and hence for n>0 and n even A(n,1) is zero and for n odd A(n,1) is one.

			Square array A(n,k) begins:
  1, 1,   1,     1,      1,      1,       1,        1, ...
  0, 1,   2,     3,      4,      5,       6,        7, ...
  0, 0,   2,     6,     12,     20,      30,       42, ...
  0, 1,   8,    30,     76,    155,     276,      448, ...
  0, 0,  18,   126,    460,   1220,    2670,     5138, ...
  0, 1,  52,   603,   3104,  10630,   28506,    64932, ...
  0, 0, 152,  3084,  22404,  98900,  324516,   874104, ...
  0, 1, 492, 16614, 169152, 960650, 3854052, 12271518, ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
Marko Riedel et al., Number of n-element subsets divisible by n

Cf. A000007, A169888, A318431, A318432, A318433, A318557.

Main diagonal gives A318477.

with(numtheory):
A:= (n, k)-> `if`(n=0, 1, add(binomial(k*d, d)*(-1)^(n+d)*
              phi(n/d), d in divisors(n))/n):
seq(seq(A(n, d-n), n=0..d), d=0..11);

A[n_, k_] : = (-1)^n (1/n) Sum[Binomial[k d, d] (-1)^d EulerPhi[n/d], {d, Divisors[n]}]; A[0, 0] = 1; A[, 0] = 0; A[0, ] = 1;
Table[A[n-k, k], {n, 0, 11}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Sep 23 2019 *)

T(n,k)=if(n==0, 1, (-1)^n*sumdiv(n, d, binomial(k*d, d) * (-1)^d * eulerphi(n/d))/n)
for(n=0, 7, for(k=0, 7, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Aug 28 2018

A(n,k) = (-1)^n * (1/n) * Sum_{d|n} C(k*d,d)*(-1)^d*phi(n/d), boundary values A(0,0) = 1, A(n, 0) = 0, A(0, k) = 1.

A061865 Triangle in which the k-th item in the n-th row (both starting from 1) is the number of ways in which we can add k distinct integers from 1 to n, in such a way that the sum is divisible by k.

Original entry on oeis.org

1, 2, 0, 3, 1, 1, 4, 2, 2, 0, 5, 4, 4, 1, 1, 6, 6, 8, 4, 2, 0, 7, 9, 13, 9, 5, 1, 1, 8, 12, 20, 18, 12, 4, 2, 0, 9, 16, 30, 32, 26, 14, 6, 1, 1, 10, 20, 42, 54, 52, 34, 18, 6, 2, 0, 11, 25, 57, 84, 94, 76, 48, 21, 7, 1, 1, 12, 30, 76, 126, 160, 152, 114, 64, 26, 6, 2, 0, 13, 36, 98, 181, 259, 284, 246, 163, 81, 28, 8, 1, 1

Offset: 1

Antti Karttunen, May 11 2001

T(n,k) is the number of k-element subsets of {1,...,n} whose mean is an integer. Row sums and alternating row sums: A051293 and A000027. - Clark Kimberling, May 05 2012 [first link corrected to A051293 by Antti Karttunen, Feb 18 2013]

			The third term of the sixth row is 8 because we have solutions {1+2+3, 1+2+6, 1+3+5, 1+5+6, 2+3+4, 2+4+6, 3+4+5, 4+5+6} which all are divisible by 3.
From _Clark Kimberling_, May 05 2012: (Start)
First six rows:
  1;
  2, 0;
  3, 1, 1;
  4, 2, 2, 0;
  5, 4, 4, 1, 1;
  6, 6, 8, 4, 2, 0;
(End)

Alois P. Heinz, Rows n = 1..150, flattened
Index entries for sequences related to subset sums modulo m

The second diagonal is given by C(((n+(n mod 2))/2), 2)+C(((n-(n mod 2))/2), 2) = A002620, the third diagonal by A061866. Cf. A061857.

T(2n,n) gives A169888.

[seq(DivSumChooseTriangle(j),j=1..120)]; DivSumChooseTriangle := (n) -> nops(DivSumChoose(trinv(n-1),(n-((trinv(n-1)*(trinv(n-1)-1))/2))));
DIVSum_SOLUTIONS_GLOBAL := []; DivSumChoose := proc(n,k) global DIVSum_SOLUTIONS_GLOBAL; DIVSum_SOLUTIONS_GLOBAL := []; DivSumChooseSearch([],n,k); RETURN(DIVSum_SOLUTIONS_GLOBAL); end;
DivSumChooseSearch := proc(s,n,k) global DIVSum_SOLUTIONS_GLOBAL; local i,p; p := nops(s); if(p = k) then if(0 = (convert(s,`+`) mod k)) then DIVSum_SOLUTIONS_GLOBAL := [op(DIVSum_SOLUTIONS_GLOBAL),s]; fi; else for i from lmax(s)+1 to n-(k-p)+1 do DivSumChooseSearch([op(s),i],n,k); od; fi; end;
lmax := proc(a) local e,z; z := 0; for e in a do if whattype(e) = list then e := last_term(e); fi; if e > z then z := e; fi; od; RETURN(z); end;
# second Maple program:
b:= proc(n, s, m, t) option remember; `if`(n=0, `if`(s=0 and t=0, 1, 0),
      `if`(t=0, 0, b(n-1, irem(s+n, m), m, t-1))+b(n-1, s, m, t))
    end:
T:= (n, k)-> b(n, 0, k$2):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 28 2018

t[n_, k_] := Length[ Select[ Subsets[ Range[n], {k}], Mod[Total[#], k] == 0 & ]]; Flatten[ Table[ t[n, k], {n, 1, 13}, {k, 1, n}]] (* Jean-François Alcover, Dec 02 2011 *)

T(n,k) = C(n,k) - Sum[a_1=1..(n-k+1)] Sum[a_2=a_1+1..(n-k+2)] ... Sum[a_k=a_(k-1)+1..n] (ceiling(f(a_1,...a_k)) - floor(f(a_1,...a_k))), where f(a_1,...a_k) = (a_1+...+a_k)/k is the arithmetic mean. - Ctibor O. Zizka, Jun 03 2015

Starting offset corrected from 0 to 1 by Antti Karttunen, Feb 18 2013.

A318431 Number of n-element subsets of [3n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 3, 6, 30, 126, 603, 3084, 16614, 91998, 520779, 3004206, 17594250, 104308092, 624801960, 3775722348, 22991162130, 140928103134, 868886416869, 5384796884934, 33525472069566, 209592226792326, 1315211209647435, 8281053081282900, 52301607644921262

Offset: 0

Marko Riedel, Aug 26 2018

nonn

Marko Riedel et al., Number of n-element subsets divisible by n

Cf. A169888, A318432, A318433.

Column k=3 of A304482.

with(numtheory); a := n -> `if`(n=0, 1, (-1)^n * 1/n * add(binomial(3*d,d)*(-1)^d*phi(n/d), d in divisors(n)));

a(n) = if (n, (-1)^n * (1/n) * sumdiv(n, d, binomial(3*d,d)*(-1)^d*eulerphi(n/d)), 1); \\ Michel Marcus, Aug 27 2018

a(n) = (-1)^n * (1/n) * Sum_{d|n} C(3d,d)*(-1)^d*phi(n/d) for n>0, a(0)=1.

A318432 Number of n-element subsets of [4n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 4, 12, 76, 460, 3104, 22404, 169152, 1315020, 10460416, 84764512, 697212652, 5805722692, 48847196896, 414623627136, 3546272614976, 30532934225100, 264420681260336, 2301782759539392, 20129523771781288, 176765807152990560, 1558058796052048968

Offset: 0

Marko Riedel, Aug 26 2018

nonn

Marko Riedel et al., Number of n-element subsets divisible by n

Cf. A169888, A318431, A318433.

Column k=4 of A304482.

with(numtheory); a := n -> `if`(n=0, 1, (-1)^n * 1/n * add(binomial(4*d,d)*(-1)^d*phi(n/d), d in divisors(n)));

a(n) = if (n, (-1)^n * (1/n) * sumdiv(n, d, binomial(4*d,d)*(-1)^d*eulerphi(n/d)), 1); \\ Michel Marcus, Aug 27 2018

a(n) = (-1)^n * (1/n) * Sum_{d|n} C(4d,d)*(-1)^d*phi(n/d) for n>0, a(0)=1.

A318433 Number of n-element subsets of [5n] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 5, 20, 155, 1220, 10630, 98900, 960650, 9613700, 98462675, 1027222520, 10877596900, 116613287300, 1263159501180, 13803839298920, 152000845788280, 1684888825463940, 18785707522181965, 210536007879090140, 2370423142929112065, 26799168520704093720

Offset: 0

Marko Riedel, Aug 26 2018

nonn

Marko Riedel et al., Number of n-element subsets divisible by n

Cf. A169888, A318431, A318432.

Column k=5 of A304482.

with(numtheory); a := n -> `if`(n=0, 1, (-1)^n * 1/n * add(binomial(5*d,d)*(-1)^d*phi(n/d), d in divisors(n)));

a(n) = if (n, (-1)^n * (1/n) * sumdiv(n, d, binomial(5*d,d)*(-1)^d*eulerphi(n/d)), 1); \\ Michel Marcus, Aug 27 2018

a(n) = (-1)^n * (1/n) * Sum_{d|n} C(5d,d)*(-1)^d*phi(n/d) for n>0, a(0)=1.

A318477 Number of n-member subsets of [n^2] whose elements sum to a multiple of n.

Original entry on oeis.org

1, 1, 2, 30, 460, 10630, 324516, 12271518, 553275192, 28987537806, 1731030733840, 116068178638786, 8634941165110140, 705873715441872276, 62895036883536770108, 6067037854078500844740, 629921975126483973659888, 70043473196734767582082246

Offset: 0

Alois P. Heinz, Aug 26 2018

nonn

			a(0) = 1: {}.
a(1) = 1: {1}.
a(2) = 2: {1,3}, {2,4}.
a(3) = 30: {1,2,3}, {1,2,6}, {1,2,9}, {1,3,5}, {1,3,8}, {1,4,7}, {1,5,6}, {1,5,9}, {1,6,8}, {1,8,9}, {2,3,4}, {2,3,7}, {2,4,6}, {2,4,9}, {2,5,8}, {2,6,7}, {2,7,9}, {3,4,5}, {3,4,8}, {3,5,7}, {3,6,9}, {3,7,8}, {4,5,6}, {4,5,9}, {4,6,8}, {4,8,9}, {5,6,7}, {5,7,9}, {6,7,8}, {7,8,9}.

Alois P. Heinz, Table of n, a(n) for n = 0..338

Main diagonal of A304482 and of A318557.

Cf. A119358, A169888, A308667.

with(numtheory):
a:= proc(n) option remember; `if`(n=0, 1, add(phi(n/d)*
      (-1)^(n+d)*binomial(n*d, d), d=divisors(n))/n)
    end:
seq(a(n), n=0..20);

a[n_] := (-1)^n Sum[(-1)^d Binomial[d n, d] EulerPhi[n/d], {d, Divisors[n]} ]/n; a[0] = 1;
a /@ Range[0, 20] (* Jean-François Alcover, Sep 23 2019 *)

a(n) = n * A308667(n) for n >= 1.

a(n) ~ exp(n - 1/2) * n^(n - 3/2) / sqrt(2*Pi). - Vaclav Kotesovec, Mar 28 2023

cp's OEIS Frontend

A119358 Number of n-element subsets of [2n] having an even sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A304482 Number A(n,k) of n-element subsets of [k*n] whose elements sum to a multiple of n. Square array A(n,k) with n, k >= 0 read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A061865 Triangle in which the k-th item in the n-th row (both starting from 1) is the number of ways in which we can add k distinct integers from 1 to n, in such a way that the sum is divisible by k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A318431 Number of n-element subsets of [3n] whose elements sum to a multiple of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A318432 Number of n-element subsets of [4n] whose elements sum to a multiple of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A318433 Number of n-element subsets of [5n] whose elements sum to a multiple of n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A318477 Number of n-member subsets of [n^2] whose elements sum to a multiple of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica