A220693 -id:A220693 - cp's OEIS frontend

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.

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

A220691 Table A(i,j) read by antidiagonals in order A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ..., where A(i,j) is the number of ways in which we can add 2 distinct integers from the range 1..i in such a way that the sum is divisible by j.

Original entry on oeis.org

0, 0, 1, 0, 0, 3, 0, 1, 1, 6, 0, 0, 1, 2, 10, 0, 0, 1, 2, 4, 15, 0, 0, 1, 1, 4, 6, 21, 0, 0, 0, 2, 2, 5, 9, 28, 0, 0, 0, 1, 2, 3, 7, 12, 36, 0, 0, 0, 1, 2, 3, 5, 10, 16, 45, 0, 0, 0, 0, 2, 2, 4, 6, 12, 20, 55, 0, 0, 0, 0, 1, 3, 3, 6, 8, 15, 25, 66, 0, 0, 0, 0

Offset: 1

Antti Karttunen, Feb 18 2013

			The upper left corner of this square array starts as:
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
   1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...
   3, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, ...
   6, 2, 2, 1, 2, 1, 1, 0, 0, 0, 0, ...
  10, 4, 4, 2, 2, 2, 2, 1, 1, 0, 0, ...
  15, 6, 5, 3, 3, 2, 3, 2, 2, 1, 1, ...
Row 1 is all zeros, because it's impossible to choose two distinct integers from range [1]. A(2,1) = 1, as there is only one possibility to choose a pair of distinct numbers from the range [1,2] such that it is divisible by 1, namely 1+2. Also A(2,3) = 1, as 1+2 is divisible by 3.
A(4,1) = 2, as from [1,2,3,4] one can choose two pairs of distinct numbers whose sum is even: {1+3} and {2+4}.

A. Karttunen, The first 150 antidiagonals of the square array, flattened
Stackexchange, Question 142323
Index entries for sequences related to subset sums modulo m

Transpose: A220692. The lower triangular region of this square array is given by A061857, which leaves out about half of the nonzero terms. A220693 is another variant giving 2n-1 terms from the beginning of each row, thus containing all the nonzero terms of this array.

The left column of the table: A000217. The following cases should be checked: the second column: A002620, the third column: A058212 (after the first two terms), the fourth column: A001971.

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+1, k], {n, 1, 13} , {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Mar 04 2014 *)

See Robert Israel's formula at A061857.

A220692 Square array A220691 transposed.

Original entry on oeis.org

0, 1, 0, 3, 0, 0, 6, 1, 1, 0, 10, 2, 1, 0, 0, 15, 4, 2, 1, 0, 0, 21, 6, 4, 1, 1, 0, 0, 28, 9, 5, 2, 2, 0, 0, 0, 36, 12, 7, 3, 2, 1, 0, 0, 0, 45, 16, 10, 5, 3, 2, 1, 0, 0, 0, 55, 20, 12, 6, 4, 2, 2, 0, 0, 0, 0, 66, 25, 15, 8, 6, 3, 3, 1, 0, 0, 0, 0

Offset: 1

Antti Karttunen, Feb 18 2013

Index entries for sequences related to subset sums modulo m

Cf. A220691, A220693, A061857.

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+1, k], {n, 1, 13} , {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 04 2014 *)

(define (A220692 n) (A220691bi (A004736 n) (A002260 n)))

a(n) = A220691bi(A004736(n),A002260(n)). (As a sequence. As an array this is the transpose of the square array given in A220691).

cp's OEIS Frontend

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

A220691 Table A(i,j) read by antidiagonals in order A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ..., where A(i,j) is the number of ways in which we can add 2 distinct integers from the range 1..i in such a way that the sum is divisible by j.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A220692 Square array A220691 transposed.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula