A061865 -id:A061865 - cp's OEIS frontend

A051293 Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.

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

Offset: 1

John W. Layman, Oct 30 1999

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

A082550(n) = a(n+1) - a(n). - Reinhard Zumkeller, Feb 19 2006

			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.

Alois P. Heinz, Table of n, a(n) for n = 1..3332 (first 300 terms from T. D. Noe)
63rd Annual William Lowell Putnam Mathematical Competition, Problem A3, Mathematics Magazine 76 (2003), 76-80.

Row sums of A061865 and A327481.

Cf. A000629, A000670, A082550, A114976.

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:
seq(a(n), n=1..40);  # Alois P. Heinz, Jul 15 2019

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 *)

a(n)=sum(k=1,n,sumdiv(k,d,d%2*2^(k/d)*eulerphi(d))/k-1)

from sympy import totient, divisors
def A051293(n): return sum((sum(totient(d)<>(~k&k-1).bit_length(),generator=True))<<1)//k for k in range(1,n+1))-n # Chai Wah Wu, Feb 22 2023

a(n) = Sum_{i=1..n} (A063776(i) - 1).

Extended by Robert G. Wilson v, Oct 16 2002

A061857 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 2 distinct integers from 1 to n in such a way that the sum is divisible by k.

Original entry on oeis.org

0, 1, 0, 3, 1, 1, 6, 2, 2, 1, 10, 4, 4, 2, 2, 15, 6, 5, 3, 3, 2, 21, 9, 7, 5, 4, 3, 3, 28, 12, 10, 6, 6, 4, 4, 3, 36, 16, 12, 8, 8, 5, 5, 4, 4, 45, 20, 15, 10, 9, 7, 6, 5, 5, 4, 55, 25, 19, 13, 11, 9, 8, 6, 6, 5, 5, 66, 30, 22, 15, 13, 10, 10, 7, 7, 6, 6, 5, 78, 36, 26, 18, 16, 12, 12, 9, 8, 7, 7

Offset: 1

Antti Karttunen, May 11 2001

Since the sum of two distinct integers from 1 to n can be as much as 2n-1, this triangular table cannot show all the possible cases. For larger triangles showing all solutions, see A220691 and A220693. - Antti Karttunen, Feb 18 2013 [based on Robert Israel's mail, May 07 2012]

			The second term on the sixth row is 6 because we have 6 solutions: {1+3, 1+5, 2+4, 2+6, 3+5, 4+6} and the third term on the same row is 5 because we have solutions {1+2,1+5,2+4,3+6,4+5}.
Triangle begins:
   0;
   1,  0;
   3,  1,  1;
   6,  2,  2,  1;
  10,  4,  4,  2,  2;
  15,  6,  5,  3,  3,  2;
  21,  9,  7,  5,  4,  3,  3;
  28, 12, 10,  6,  6,  4,  4,  3;
  36, 16, 12,  8,  8,  5,  5,  4,  4;
  45, 20, 15, 10,  9,  7,  6,  5,  5,  4;

Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened
Stackexchange, Question 142323
Index entries for sequences related to subset sums modulo m

This is the lower triangular region of square array A220691. See A220693 for all nonzero solutions.

The left edge (first diagonal) of the triangle: A000217, 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 A058212, the fourth by A001971, the central column by A042963? trinv is given at A054425. Cf. A061865.

a061857 n k = length [()| i <- [2..n], j <- [1..i-1], mod (i + j) k == 0]
a061857_row n = map (a061857 n) [1..n]
a061857_tabl = map a061857_row [1..]
-- Reinhard Zumkeller, May 08 2012

[seq(DivSumChoose2Triangle(j),j=1..120)]; DivSumChoose2Triangle := (n) -> nops(DivSumChoose2(trinv(n-1),(n-((trinv(n-1)*(trinv(n-1)-1))/2))));
DivSumChoose2 := proc(n,k) local a,i,j; a := []; for i from 1 to (n-1) do for j from (i+1) to n do if(0 = ((i+j) mod k)) then a := [op(a),[i,j]]; fi; od; od; RETURN(a); end;

a[n_, 1] := n*(n-1)/2; a[n_, k_] := Module[{r}, r = Reduce[1 <= i < j <= n && Mod[i + j, k] == 0, {i, j}, Integers]; Which[Head[r] === Or, Length[r], Head[r] === And, 1, r === False, 0, True, Print[r, " not parsed"]]]; Table[a[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 04 2014 *)

(define (A061857 n) (A220691bi (A002024 n) (A002260 n))) ;; Antti Karttunen, Feb 18 2013. Needs A220691bi from A220691.

From Robert Israel, May 08 2012: (Start)
Let n+1 = b mod k with 0 <= b < k, q = (n+1-b)/k.  Let k = c mod 2, c = 0 or 1.
If b = 0 or 1 then a(n,k) = q^2*k/2 + q*b - 2*q - b + 1 + c*q/2.
If b >= (k+3)/2 then a(n,k) = q^2*k/2 + q*b - 2*q + b - 1 - k/2 + c*(q+1)/2.
Otherwise a(n,k) = q^2*k/2 + q*b - 2*q + c*q/2. (End)

Offset corrected by Reinhard Zumkeller, May 08 2012

A169888 Number of n-member subsets of 1..2n whose elements sum to a multiple of n.

Original entry on oeis.org

1, 2, 2, 8, 18, 52, 152, 492, 1618, 5408, 18452, 64132, 225432, 800048, 2865228, 10341208, 37568338, 137270956, 504171584, 1860277044, 6892335668, 25631327688, 95640829924, 357975249028, 1343650267288, 5056424257552, 19073789328752, 72108867620204

Offset: 0

N. J. A. Sloane, Jul 07 2010, based on a letter from Jean-Claude Babois

nonn

This is twice A145855 (for n>0), which is the main entry for this problem.

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

Cf. A061865, A119358, A145855, A318431, A318432, A318433.

Column k=2 of A304482.

with(combinat): t0:=[]; for n from 1 to 8 do ans:=0; t1:=choose(2*n,n); for i in t1 do s1:=add(i[j],j=1..n); if s1 mod n = 0 then ans:=ans+1; fi; od: t0:=[op(t0),ans]; od:

a[n_] := Sum[(-1)^(n+d)*EulerPhi[n/d]*Binomial[2d, d]/n, {d, Divisors[n]}]; Table[a[n], {n, 1, 26}] (* Jean-François Alcover, Oct 22 2012, after T. D. Noe's program in A145855 *)

a(n) = if(n==0, 1, sumdiv(n, d, (-1)^(n+d)*eulerphi(n/d)*binomial(2*d, d)/n)); \\ Altug Alkan, Aug 27 2018, after T. D. Noe at A145855

a(n) = A061865(2n,n). - Alois P. Heinz, Aug 28 2018

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

a(0)=1 prepended by Alois P. Heinz, Aug 26 2018

A061866 a(n) is the number of solutions to x+y+z = 0 mod 3, where 1 <= x < y < z <= n.

Original entry on oeis.org

0, 0, 0, 1, 2, 4, 8, 13, 20, 30, 42, 57, 76, 98, 124, 155, 190, 230, 276, 327, 384, 448, 518, 595, 680, 772, 872, 981, 1098, 1224, 1360, 1505, 1660, 1826, 2002, 2189, 2388, 2598, 2820, 3055, 3302, 3562, 3836, 4123, 4424, 4740, 5070, 5415, 5776, 6152, 6544, 6953, 7378, 7820

Offset: 0

Antti Karttunen, May 11 2001

(1+x)*(1+x^2)*(1+x^3) / ( (1-x)*(1-x^2)*(1-x^3)*(1-x^4)) is the Poincaré series [or Poincare series] (or Molien series) for H^*(O_4(q); F_2).

A. Adem and R. J. Milgram, Cohomology of Finite Groups, Springer-Verlag, 2nd. ed., 2004; p. 233.

D. Z. Dokovic, B. H. Smith, Quaternionic matrices: Unitary similarity, simultaneous triangularization and some trace identities, Lin. Alg. Applic. 428 (4) (2008) 890-910
Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-3,3,-1).

The third diagonal of A061865.

LinearRecurrence[{3,-3,2,-3,3,-1},{0,0,0,1,2,4},60] (* Harvey P. Dale, Nov 22 2014 *)

G.f.: x^3*(1+x)*(1+x^2)*(1+x^3) / ( (1-x)*(1-x^2)*(1-x^3)*(1-x^4)). - N. J. A. Sloane, Mar 17 2004
a(n) = (binomial(n,3)+2*floor(n/3))/3. - Claude Morin, Mar 06 2012
G.f.: x^3*(1-x+x^2) / ( (1+x+x^2)*(x-1)^4 ). - R. J. Mathar, Dec 18 2014
a(n+5) = A014125(n)-A014125(n+1)+A014125(n+2). - R. J. Mathar, Mar 11 2019

A212138 Triangular array: T(n,k) is the number of k-element subsets S of {1,...,n} whose average is in S.

Original entry on oeis.org

1, 2, 0, 3, 0, 1, 4, 0, 2, 0, 5, 0, 4, 0, 1, 6, 0, 6, 2, 2, 0, 7, 0, 9, 4, 5, 0, 1, 8, 0, 12, 8, 10, 2, 2, 0, 9, 0, 16, 14, 18, 8, 6, 0, 1, 10, 0, 20, 22, 32, 20, 14, 4, 2, 0, 11, 0, 25, 32, 52, 42, 34, 14, 7, 0, 1, 12, 0, 30, 46, 80, 80, 72, 42, 22, 4, 2, 0, 13, 0, 36, 62, 119, 1

Offset: 1

Clark Kimberling, May 06 2012

			First 7 rows:
  1
  2...0
  3...0...1
  4...0...2...0
  5...0...4...0...1
  6...0...6...2...2...0
  7...0...9...4...5...0...1
T(5,3) counts these subsets: {1,2,3}, {1,3,5}, {2,3,4}, {3,4,5}.

Cf. A061865.

t[n_, k_] := Length[Flatten[Map[Apply[Intersection, #] &,
    Select[Map[{#, {Mean[#]}} &, Subsets[Range[n], {k}]], IntegerQ[Last[Last[#]]] &]]]]
Flatten[Table[t[n, k], {n, 1, 12}, {k, 1, n}]]
TableForm[Table[t[n, k], {n, 1, 12}, {k, 1, n}]]
(* Peter J. C. Moses, May 01 2012 *)

A212137 Triangular array: T(n,k) is the number of k-element subsets of {1,...,n} whose average is not an integer.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 0, 4, 2, 1, 0, 6, 6, 4, 0, 0, 9, 12, 11, 4, 1, 0, 12, 22, 26, 16, 6, 0, 0, 16, 36, 52, 44, 24, 6, 1, 0, 20, 54, 94, 100, 70, 30, 8, 0, 0, 25, 78, 156, 200, 176, 102, 39, 8, 1, 0, 30, 108, 246, 368, 386, 282, 144, 48, 10, 0, 0, 36, 144, 369, 632, 772, 678, 431, 194, 60, 10, 1

Offset: 1

Clark Kimberling, May 06 2012

Alternating row sums: -1,-2,-3,-4,-5,-6,...

Let S(n,k) be the number in row n and column k of the array A061865; then S(n,k)+T(n,k)=C(n,k), for 1<=k<=n, n>=1.

			First 7 rows:
0
0...1
0...2....0
0...4....2....1
0...6....6....4....0
0...9....12...11...4....1
0...12...22...26...16...6...0

Alois P. Heinz, Rows n = 1..90, flattened

Cf. A061865.

t[n_, k_] := t[n, k] =
  Count[Map[IntegerQ[Mean[#]] &, Subsets[Range[n], {k}]], False]
Flatten[Table[t[n, k], {n, 1, 12}, {k, 1, n}]]
TableForm[Table[t[n, k], {n, 1, 12}, {k, 1, n}]]
s[n_] := Sum[t[n, k], {k, 1, n}]
(* Peter J. C. Moses, May 01 2012 *)

cp's OEIS Frontend

A051293 Number of nonempty subsets of {1,2,3,...,n} whose elements have an integer average.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A061857 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 2 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

Haskell

Maple

Mathematica

Scheme

Formula

Extensions

A169888 Number of n-member subsets of 1..2n whose elements sum to a multiple of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A061866 a(n) is the number of solutions to x+y+z = 0 mod 3, where 1 <= x < y < z <= n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A212138 Triangular array: T(n,k) is the number of k-element subsets S of {1,...,n} whose average is in S.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A212137 Triangular array: T(n,k) is the number of k-element subsets of {1,...,n} whose average is not an integer.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica