A264388 -id:A264388 - cp's OEIS frontend

A161680 a(n) = binomial(n,2): number of size-2 subsets of {0,1,...,n} that contain no consecutive integers.

0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378

Offset: 0

Jaroslav Krizek, Jun 16 2009

Essentially the same as A000217: zero followed by A000217. - Joerg Arndt, Jul 26 2015
Count of entries <= n in A003057.
a(n) is the number of size-2 subsets of [n+1] that contain no consecutive integers, a(n+1) is the n-th triangular number. - Dennis P. Walsh, Mar 30 2011
Construct the n-th row of Pascal's triangle (A007318) from the preceding row, starting with row 0 = 1. a(n) is the sequence consisting of the total number of additions required to compute the triangle in this way up to row n. Copying a term does not count as an addition. - Douglas Latimer, Mar 05 2012
a(n-1) is also the number of ordered partitions (compositions) of n >= 1 into exactly 3 parts. - Juergen Will, Jan 02 2016
a(n+2) is also the number of weak compositions (ordered weak partitions) of n into exactly 3 parts. - Juergen Will, Jan 19 2016
In other words, this is the number of relations between entities, for example between persons: Two persons (n = 2) will have one relation (a(n) = 1), whereas four persons will have six relations to each other, and 20 persons will have 190 relations between them. - Halfdan Skjerning, May 03 2017
This also describes the largest number of intersections between n lines of equal length sequentially connected at (n-1) joints. The joints themselves do not count as intersection points. - Joseph Rozhenko, Oct 05 2021
The lexicographically earliest infinite sequence of nonnegative integers with monotonically increasing differences (that are also nonnegative integers). - Joe B. Stephen, Jul 22 2023

			A003057 starts 2, 3, 3, 4, 4,..., so there are a(0)=0 numbers <= 0, a(1)=0 numbers <= 1, a(2)=1 number <= 2, a(3)=3 numbers <= 3 in A003057.
For n=4, a(4)=6 since there are exactly 6 size-2 subsets of {0,1,2,3,4} that contain no consecutive integers, namely, {0,2}, {0,3}, {0,4}, {1,3}, {1,4}, and {2,4}.

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 4.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Steve Lawford and Yll Mehmeti, Cliques and a new measure of clustering: with application to U.S. domestic airlines, arXiv:1806.05866 [cs.SI], 2018.
P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901.
Dennis Walsh, Notes on size-2 subsets of [n] that contain no consecutive integers
Eric Weisstein's World of Mathematics, Composition
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A000124, A000217, A000290, A004125, A034856, A244049.

a003057:=func< n | Round(Sqrt(2*(n-1)))+1 >; S:=[]; m:=2; count:=0; for n in [2..2000] do if a003057(n) lt m then count+:=1; else Append(~S, count); m+:=1; end if; end for; S; // Klaus Brockhaus, Nov 30 2010

Maple
```
seq(binomial(n,2),n=0..50);
```

Join[{a = 0}, Table[a += n, {n, 0, 100}]] (* Vladimir Joseph Stephan Orlovsky, Jun 12 2011 *)
f[n_] := n(n-1)/2; Array[f, 54, 0] (* Robert G. Wilson v, Jul 26 2015 *)
Binomial[Range[0,60],2] (* or *) LinearRecurrence[{3,-3,1},{0,0,1},60] (* Harvey P. Dale, Apr 14 2017 *)

a(n)=n*(n-1)/2 \\ Charles R Greathouse IV, Jun 17 2017

a(n) = (n^2 - n)/2 = n*(n - 1)/2.
a(n) = A000124(n-1)-1 = A000217(n-1).
a(n) = a(n-1)+n-1 (with a(0)=a(1)=0). - Vincenzo Librandi, Nov 30 2010
Compositions: C(n,3) = binomial(n-1,n-3) = binomial(n-1,2), n>0. - Juergen Will, Jan 02 2015
G.f.: x^2/(1-x)^3. - Dennis P. Walsh, Mar 30 2011
G.f. with offset 1: Compositions: (x+x^2+x^3+...)^3 = (x/(1-x))^3. - Juergen Will, Jan 02 2015
a(n-1) = 6*n*s(1,n), n >= 1, where s(h,k) are the Dedekind sums. For s(1,n) see A264388(n)/A264389(n), also for references. - Wolfdieter Lang, Jan 11 2016
a(n) = A244049(n+1) + A004125(n+1). - Omar E. Pol, Mar 25 2021
a(n) = A000290(n+1) - A034856(n+1). - Omar E. Pol, Mar 30 2021
E.g.f.: exp(x)*x^2/2. - Stefano Spezia, Dec 19 2021

Definition rephrased, offset set to 0 by R. J. Mathar, Aug 03 2010

A264389 Denominator of binomial(n-1, 2)/(6*n), for n >= 1. Denominator of Dedekind sum s(1,n).

Original entry on oeis.org

1, 1, 18, 8, 5, 18, 14, 16, 27, 5, 22, 72, 13, 14, 90, 32, 17, 27, 38, 40, 63, 22, 46, 144, 25, 13, 162, 56, 29, 90, 62, 64, 99, 17, 70, 216, 37, 38, 234, 80, 41, 63, 86, 88, 135, 46, 94, 288, 49, 25, 306, 104, 53, 162, 110, 112, 171, 29, 118, 360, 61, 62, 378

Offset: 1

Wolfdieter Lang, Jan 11 2016

See A264388 for the numerators and details about the Dedekind sum s(1,n), as well as references.

Cf. A264388.

using Nemo
A264389(n) = denominator(dedekind_sum(1, n))
[A264389(n) for n in 1:70] |> println # Peter Luschny, Mar 13 2018

Denominator[Table[Binomial[n-1,2]/(6n),{n,50}]] (* Harvey P. Dale, Aug 30 2016 *)

a(n) = denominator(binomial(n-1, 2)/(6*n)), n >= 1.

a(n) = denominator(s(1,n)), with s(1,n) = Sum_{r=1..(n-1)} (r/n)*(r/n - floor(r/n)- 1/2), n >= 1, where s(h,k) are the Dedekind sums.

A278713 Numerators of (n-1)(n-3)/(6(2n-1)); equivalently, numerators of Dedekind sum s(2,2n-1).

Original entry on oeis.org

0, -1, 0, 1, 4, 5, 4, 7, 8, 21, 40, 33, 4, 143, 28, 65, 112, 17, 48, 323, 60, 133, 44, 161, 88, 575, 104, 45, 364, 261, 140, 899, 32, 341, 544, 385, 204, 259, 228, 481, 760, 533, 56, 1763, 308, 645, 1012, 141, 368, 2303, 400, 833, 260, 901, 468, 2915, 504, 209

Offset: 1

Wolfdieter Lang, Nov 28 2016

For the denominators see A278714.

This gives the numerators of the rational numbers r(n) = s(2,2*n-1), where s(h,k) = Sum_{r=1..k-1} (r/k)*(h*r/k - floor(h*r/k)- 1/2), k >=1, are the Dedekind sums. See the references, Apostol pp. 52, 61-69, 72-73, Ayoub, p. 168, and the Weisstein link. Because gcd(h,k) = 1 is assumed, for h=2 only odd k is of interest.

Apostol, Tom, M., Modular Functions and Dirichlet Series in Number Theory, Second edition, Springer, 1990.
Ayoub, R., An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963, pp. 168, 191.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Dedekind Sum.

Cf. A278714, A264388/A264389 for s(1,n).

[Numerator((n-1)*(n-3)/(6*(2*n-1))): n in [1..60]]; // Vincenzo Librandi, Nov 21 2018

Table[Numerator[(n - 1) (n - 3) / (6 (2 n - 1))], {n, 60}] (* Vincenzo Librandi, Nov 21 2018 *)

a(n)=numerator((n-1)*(n-3)/(12*n-6)) \\ Charles R Greathouse IV, Nov 28 2016

a(n) = numerator((n-1)*(n-3)/(6*(2*n-1))).
a(n) = numerator(r(n)), with r(n) = s(2,2*n-1) where s(2,k) = Sum_{r=1..(k-1)} (r/k)*(2*r/k - floor(2*r/k)- 1/2), for odd k.
(n-1)*(n-3)/30 <= a(n) <= (n-1)*(n-3) for n > 2. - Charles R Greathouse IV, Nov 28 2016

A080779 Triangle read by rows: n-th row gives expansion of the series for HarmonicNumber(n, -r).

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 0, 6, 12, 6, -4, 0, 40, 60, 24, 0, -60, 0, 300, 360, 120, 120, 0, -840, 0, 2520, 2520, 720, 0, 3360, 0, -11760, 0, 23520, 20160, 5040, -12096, 0, 80640, 0, -169344, 0, 241920, 181440, 40320, 0, -544320, 0, 1814400, 0, -2540160, 0, 2721600, 1814400, 362880

Offset: 0

Wouter Meeussen, Mar 11 2003

The harmonic numbers as used here are defined: HarmonicNumber(n, r) = Zeta(r) - HurwitzZeta(r, n + 1). - Peter Luschny, Mar 21 2024

			The triangle t(n, m) begins:
n\m  0    1    2      3    4      5     6    7 ...
0:   1
1:   1    1
2:   1    3    2
3:   0    6   12      6
4:  -4    0   40     60   24
5:   0  -60    0    300  360    120
6: 120    0 -840      0 2520   2520   720
7:   0 3360    0 -11760    0  23520 20160 5040
...
Row n=8: -12096    0 80640      0 -169344 0 241920 181440 40320;
Row n=9: 0 -544320 0 1814400 0 -2540160 0 2721600 1814400 362880;
Row n=10: 3024000 0 -19958400 0 39916800 0 -39916800 0 33264000 19958400 3628800.
... Reformatted and extended. - _Wolfdieter Lang_, Feb 04 2016

J. H. Silverman, A Friendly Introduction to Number Theory, 3rd ed., Pearson Education, Inc, 2006, pp. 370 - 371.

G. C. Greubel, Rows n=0..100 of triangle, flattened
Wikipedia, Faulhaber's formula

Cf. A264388, A264389, A103438.

RowPoly := n -> local j; n!*add(binomial(n + 1, j) * bernoulli(j, 1) * x^(n - j), j = 0..n): seq(lprint(seq(coeff(RowPoly(n), x, k), k = 0..n)), n = 0..8);
# Peter Luschny, Mar 21 2024

Table[(n+1)! CoefficientList[Sum[k^n, {k, 0, m}]/m, m], {n,1,12}] and for n=0: 1.
a = Join[{{1}}, Table[CoefficientList[Expand[n!*(BernoulliB[n + 1, x + 1] - BernoulliB[n + 1])/x], x], {n, 1, 10}]] Flatten[a] (* Roger L. Bagula and N. J. A. Sloane, Feb 18 2008 *)
T[n_, k_] := Coefficient[ 1/x Integrate[ BernoulliB[n, x + 1], x], x, k]; (* Michael Somos, Aug 18 2018 *)

Row sums are (n + 1)!, last element in row n is n!
Alternative description using Bernoulli polynomials: Let p[x,n]=Sum[k^n,{k,1,x}]; 1/x /. NSolve[p[x,n]-Zeta[n]==0,x] where n>=2. Then t(n,m) = CoefficientList[Expand[n!*(BernoulliB[n + 1, x + 1] - BernoulliB[n + 1])/x], x]. - Roger L. Bagula and N. J. A. Sloane, Feb 18 2008
From Wolfdieter Lang, Feb 04 2016: (Start)
The row polynomials R(n, x) = (n+1)!*F(n, x)/x with F(n,x) = (Sum_{k=1..m} k^n)|{m=x} satisfy the recurrence R(n, x) = n!*(((x + 1)^(n+1) - 1)/x - Sum{k=0..n-1} (binomial(n+1, k)*R(k, x)/(k+1)!)), n >= 1, and R(0, x) = 1. See the Silverman reference, pp. 370 - 371, for F(n, x).
t(n, m) = [x^m] ((Bernoulli(n+1, x+1) - Bernoulli(n+1, 1))/x). See a comment above. For these Bernoulli polynomials see A264388 and A264389. (End)
t(n, m) = t(n-1, m-1) * n/(m+1). - Michael Somos, Aug 18 2018
T(n, k) = [x^k] n!*Sum_{j=0..n} binomial(n+1, j)*Bernoulli(j, 1)*x^(n - j). - Peter Luschny, Mar 21 2024

A278715 Table T read by rows. T(k, h) gives the numerators of the Dedekind sums s(h, k) with gcd(h, k) = 1 or 0 otherwise.

Original entry on oeis.org

0, 1, -1, 1, 0, -1, 1, 0, 0, -1, 5, 0, 0, 0, -5, 5, 1, -1, 1, -1, -5, 7, 0, 1, 0, -1, 0, -7, 14, 4, 0, -4, 4, 0, -4, -14, 3, 0, 0, 0, 0, 0, 0, 0, -3, 15, 5, 3, 3, -5, 5, -3, -3, -5, -15, 55, 0, 0, 0, -1, 0, 1, 0, 0, 0, -55, 11, 4, 1, -1, 0, -4, 4, 0, 1, -1, -4, -11, 13, 0, 3, 0, 3, 0, 0, 0, -3, 0, -3, 0, -13, 91, 7, 0, 19, 0, 0, -7, 7, 0, 0, -19, 0, -7, -91

Offset: 2

Wolfdieter Lang, Nov 28 2016

For the denominators see A278716.
The Dedekind sums are s(h,k) = Sum_{r=1..k-1} (r/k)*(h*r/k - floor(h*r/k) - 1/2) = Sum_{r=1..k-1} ((r/k))*((h*r)/k) with the period 1 sawtooth function ((x)) = x - floor(x) - 1/2 if x is not an integer and 0 otherwise. One assumes gcd(h,k) = 1, and for other h, k values the table has 0's. See the references Apostol pp. 52, 61-69, 72-73 and Ayoub pp. 168, 191. See also the Weisstein link.
In order to have a regular triangle T(k, h)  one starts with k >= 2 and h = 1, 2, ..., k-1. s(1,1) = 0.

			The triangle T(k,h) begins (if gcd(k,h) is not 1 we use o instead of 0):
k\h  1  2  3  4  5  6  7   8  9  10  11  12
2:   0
3:   1 -1
4:   1  o -1
5:   1  0  0 -1
6:   5  o  o  o -5
7:   5  1 -1  1 -1 -5
8:   7  o  1  o -1  o -7
9:  14  4  o -4  4  o -4 -14
10:  3  o  0  o  o  o  0   o -3
11: 15  5  3  3 -5  5 -3  -3 -5 -15
12: 55  o  o  o -1  o  1   o  o   o -55
13: 11  4  1 -1  0 -4  4   0  1  -1  -4 -11
...
n = 14: 13 o 3 o 3 o o o -3 o -3 o -13,
n = 15: 91 7 0 19 0 0 -7 7 0 0 -19 0 -7 -91.
...
---------------------------------------------
The rational triangle s(h,k) begins (here o is used if gcd(h,k) is not 1):
k\h  1      2     3    4     5     6     7
2:   0
3:  1/18 -1/18
4:  1/8     o  -1/8
5:  1/5     0    0   -1/5
6:  5/18    o    o     o   -5/18
7:  5/14  1/14 -1/14  1/14 -1/14 -5/14
8:  7/16    o   1/16   o   -1/16   o   -7/16
...
n = 9: 14/27 4/27 o -4/27 4/27 o -4/27 -14/27,
n = 10: 3/5 o 0 o o o 0 o -3/5,
n = 11: 15/22 5/22 3/22 3/22 -5/22 5/22 -3/22 -3/22 -5/22 -15/22,
n = 12:  55/72 o o o -1/72 o 1/72 o o o  -55/72,
n = 13: 11/13 4/13 1/13 -1/13 0 -4/13 4/13 0 1/13 -1/13 -4/13 -11/13,
n = 14: 13/14 o 3/14 o 3/14 o o o -3/14 o -3/14 o -13/14,
n = 15: 1/90 7/18 o 19/90 o o -7/18 7/18 o o -19/90 o -7/18 -91/90.
...
--------------------------------------------

Apostol, Tom, M., Modular Functions and Dirichlet Series in Number Theory, Second edition, Springer, 1990.
Ayoub, R., An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963.

G. C. Greubel, Rows n=2..100 of triangle, flattened
Eric Weisstein's World of Mathematics, Dedekind Sum.

Cf. A278716, A264388/A264389 (h=1), A278713/A278714 (h=2 odd k).

[[GCD(n,k) eq 1 select Numerator((&+[(j/n)*(k*j/n - Floor(k*j/n) - 1/2): j in [1..(n-1)]])) else 0: k in [1..(n-1)]]: n in [2..15]]; // G. C. Greubel, Nov 22 2018

T[n_, k_]:= If[GCD[n, k] == 1, Sum[(j/n)*(k*j/n - Floor[k*j/n] - 1/2), {j, 1, n - 1}], 0]; Numerator[Table[T[n, k], {n,2,15}, {k,1,n-1}]] //Flatten (* G. C. Greubel, Nov 22 2018 *)

{T(n,k) = if(gcd(n,k)==1, sum(j=1,n-1, (j/n)*(k*j/n - floor(k*j/n) - 1/2)), 0)};
for(n=2,15, for(k=1,n-1, print1(numerator(T(n,k)), ", "))) \\ G. C. Greubel, Nov 22 2018

def T(n,k):
    if gcd(n,k)==1:
       return numerator(sum((j/n)*(k*j/n - floor(k*j/n) - 1/2) for j in (1..(n-1))))
    elif gcd(n,k)!=1:
        return 0
    else:
        0
[[T(n,k) for k in (1..n-1)] for n in (2..15)] # G. C. Greubel, Nov 22 2018

T(k ,h) = numerator(s(h,k)) with the Dedekind sums s(h,k) given in a comment above and gcd(h,k) = 1. k >=2, h = 1, 2, ..., k-1. If gcd(h,k) is not 1 then T(k,h) is put to 0 (in the example o is used). Note that T(k,h) can vanish also for gcd(h,k) = 1.

cp's OEIS Frontend

A161680 a(n) = binomial(n,2): number of size-2 subsets of {0,1,...,n} that contain no consecutive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A264389 Denominator of binomial(n-1, 2)/(6*n), for n >= 1. Denominator of Dedekind sum s(1,n).

Views

Author

Keywords

Comments

Crossrefs

Programs

Julia

Mathematica

Formula

A278713 Numerators of (n-1)*(n-3)/(6*(2*n-1)); equivalently, numerators of Dedekind sum s(2,2*n-1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A080779 Triangle read by rows: n-th row gives expansion of the series for HarmonicNumber(n, -r).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A278715 Table T read by rows. T(k, h) gives the numerators of the Dedekind sums s(h, k) with gcd(h, k) = 1 or 0 otherwise.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A278713 Numerators of (n-1)(n-3)/(6(2n-1)); equivalently, numerators of Dedekind sum s(2,2n-1).