A125182 -id:A125182 - cp's OEIS frontend

A065608 Sum of divisors of n minus the number of divisors of n.

0, 1, 2, 4, 4, 8, 6, 11, 10, 14, 10, 22, 12, 20, 20, 26, 16, 33, 18, 36, 28, 32, 22, 52, 28, 38, 36, 50, 28, 64, 30, 57, 44, 50, 44, 82, 36, 56, 52, 82, 40, 88, 42, 78, 72, 68, 46, 114, 54, 87, 68, 92, 52, 112, 68, 112, 76, 86, 58, 156, 60, 92, 98, 120, 80, 136, 66, 120, 92

Offset: 1

Jason Earls, Nov 06 2001

Number of permutations p of {1,2,...,n} such that p(k)-k takes exactly two distinct values. Example: a(4)=4 because we have 4123, 3412, 2143 and 2341. - Max Alekseyev and Emeric Deutsch, Dec 22 2006
Number of solutions to the Diophantine equation xy + yz = n, with x,y,z >= 1.
In other words, number of ways to write n = (a + b) * k for positive integers a, b, k. - Gus Wiseman, Mar 25 2021
Not the same as A184396(n): a(66) = 136 while A184396(66) = 137. - Wesley Ivan Hurt, Dec 26 2013
From Gus Wiseman, Mar 25 2021: (Start)
Also the number of compositions of n into an even number of parts with alternating parts equal. These are finite even-length sequences q of positive integers summing to n such that q(i) = q(i+2) for all possible i. For example, the a(2) = 1 through a(8) = 11 compositions are:
  (1,1)  (1,2)  (1,3)      (1,4)  (1,5)          (1,6)  (1,7)
         (2,1)  (2,2)      (2,3)  (2,4)          (2,5)  (2,6)
                (3,1)      (3,2)  (3,3)          (3,4)  (3,5)
                (1,1,1,1)  (4,1)  (4,2)          (4,3)  (4,4)
                                  (5,1)          (5,2)  (5,3)
                                  (1,2,1,2)      (6,1)  (6,2)
                                  (2,1,2,1)             (7,1)
                                  (1,1,1,1,1,1)         (1,3,1,3)
                                                        (2,2,2,2)
                                                        (3,1,3,1)
                                                        (1,1,1,1,1,1,1,1)
The odd-length version is A062968.
The version with alternating parts weakly decreasing is A114921, or A342528 if odd-length compositions are included.
The version with alternating parts unequal is A342532, or A224958 if odd-length compositions are included (unordered: A339404/A000726).
Allowing odd lengths as well as even gives A342527.
(End)
Inverse Möbius transform of n-1. - Wesley Ivan Hurt, Jun 29 2024

Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
M. Alekseyev, E. Deutsch, and J. H. Steelman, Solution to problem 11281, Amer. Math. Monthly, 116, No. 5, 2009, p. 465.
George E. Andrews, Stacked lattice boxes, Ann. Comb. 3 (1999), 115-130. See L_2(n).
Joerg Arndt, On computing the generalized Lambert series, arXiv:1202.6525v3 [math.CA], (2012).
Masato Kobayashi, New recurrences for divisor sum functions and triangular numbers, arXiv:2207.05831 [math.NT], 2022.

Cf. A000203, A000005, A134857.
Starting (1, 2, 4, 4, 8, 6, ...), = row sums of triangle A077478. - Gary W. Adamson, Nov 12 2007
Starting with "1" = row sums of triangle A176919. - Gary W. Adamson, Apr 29 2010
Column k=2 of A125182.
A175342/A325545 count compositions with constant/distinct differences.
Cf. A001522, A002843, A008965, A010054, A064410, A064428, A325557, A342495.

List([1..100],n->Sigma(n)-Tau(n)); # Muniru A Asiru, Mar 19 2018

with(numtheory): seq(sigma(n)-tau(n),n=1..70); # Emeric Deutsch, Dec 22 2006

Table[DivisorSigma[1,n]-DivisorSigma[0,n], {n,100}] (* Wesley Ivan Hurt, Dec 26 2013 *)

a(n) = sigma(n) - numdiv(n); \\ Harry J. Smith, Oct 23 2009

from math import prod
from sympy import factorint
def A065608(n):
    f = factorint(n).items()
    return prod((p**(e+1)-1)//(p-1) for p, e in f)-prod(e+1 for p,e in f) # Chai Wah Wu, Jul 16 2022

a(n) = sigma(n) - d(n) = A000203(n) - A000005(n).
a(n) = Sum_{d|n} (d-1). - Wesley Ivan Hurt, Dec 26 2013
G.f.: Sum_{k>=1} x^(2*k)/(1-x^k)^2. - Benoit Cloitre, Apr 21 2003
G.f.: Sum_{n>=1} (n-1)*x^n/(1-x^n). - Joerg Arndt, Jan 30 2011
L.g.f.: -log(Product_{k>=1} (1 - x^k)^(1-1/k)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Mar 18 2018
G.f.: Sum_{n >= 1} q^(n^2)*( (n - 1) + q^n - (n - 1)*q^(2*n) )/(1 - q^n)^2 - differentiate equation 1 in Arndt with respect to t, then set x = q and t = q. - Peter Bala, Jan 22 2021
a(n) = A342527(n) - A062968(n). - Gus Wiseman, Mar 25 2021
a(n) = n * A010054(n) - Sum_{k>=1} a(n - k*(k+1)/2), assuming a(n) = 0 for n <= 0 (Kobayashi, 2022). - Amiram Eldar, Jun 23 2023

A099152 Number of n X n permutation matrices in which the sums of the entries of each NorthEast-SouthWest diagonal are 0 or 1.

Original entry on oeis.org

1, 1, 1, 3, 7, 23, 83, 405, 2113, 12657, 82297, 596483, 4698655, 40071743, 367854835, 3622508685, 38027715185, 424060091065, 5006620130753, 62395131973755, 818456924866815, 11271715349614463

Offset: 0

Cecilia Bebeacua and Simone Severini, Nov 16 2004

Numbers of solutions to a modified version of the n-queens problem, in which two queens do not attack each other if they are in the same NorthWest-SouthEast diagonal.
Number of perfect extremal Skolem-type sequences of order n.
From Emeric Deutsch, Nov 28 2008: (Start)
a(n) is also the number of permutations p of {1,2,...,n} for which the numbers p(i)-i (i=1,2,...,n) are distinct. Example: a(4)=7 because we have 4132, 3142, 2413, 4213, 2431, 3241 and 4321.
a(n) is also the number of permutations p of {1,2,...,n} for which the numbers p(i)+i (i=1,2,...,n) are distinct. Example: a(4)=7 because we have 1423, 2413, 3142, 1342, 3124, 2314 and 1234.
a(n) = A125182(n,n). (End)
Also number of transversals in the n X n matrix M defined by M_{ij} = i+j. [Cavenagh-Wanless]

D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.

N. J. Cavenagh and I. M. Wanless, On the number of transversals in Cayley tables of cyclic groups, Disc. Appl. Math. 158 (2010), 136-146.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 672, 732-736.
G. Nordh, Perfect Skolem sequences, arXiv:math/0506155 [math.CO], 2005.
Kevin Pratt, Closed-Form Expressions for the n-Queens Problem and Related Problems, arXiv:1609.09585 [cs.DM], 2016.
W. Schubert, N-Queens page
Eduard C. Taganap and Rainier D. Almuete, n-Rooks and n-queens problem on planar and modular chessboards with hexagonal cells, Notes Num. Theor. Disc. Math. (2023) Vol. 29, No. 4, 774-788. See p. 778.

Cf. A125182. [From Emeric Deutsch, Nov 28 2008]

b[i_, p_, s_] := b[i, p, s] = If[p == {}, x^Length[s], Sum[b[i+1, p ~Complement~ {t}, s ~Union~ {t+i}], {t, p}]];
a[n_] := Coefficient[b[1, Range[n], {}], x, n];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 12}] (* Jean-François Alcover, Aug 07 2018, after Alois P. Heinz *)

More terms from Ivica Kolar, Nov 23 2004
a(14)-a(18) from Ian Wanless, Jul 30 2010, from the Cavenagh-Wanless paper.
a(19),a(20) from W. Schubert, May 27 2011
a(21) from W. Schubert, Feb 26 2012
a(0) = 1 prepended by Joerg Arndt, Sep 16 2018

A306455 Total number of covered falling diagonals in all n X n permutation matrices.

Original entry on oeis.org

0, 1, 3, 14, 73, 454, 3253, 26480, 241505, 2440538, 27075301, 327197452, 4278799105, 60205974230, 907025841317, 14567520651224, 248474458923073, 4485765986251570, 85454391074596165, 1713134893536617348, 36052727133118151201, 794697884305583064302

Offset: 0

Alois P. Heinz, Feb 16 2019

nonn

A covered diagonal in a permutation matrix contains at least one 1.
Alternatively: Total number of covered raising diagonals in all n X n permutation matrices.
Also one half of the total number of all covered diagonals in all n X n permutation matrices.
Sum over all permutations p of [n] of the cardinality of the (signed) displacement set {p(i)-i, i=1..n}.
Alternatively: Sum over all permutations p of [n] of the cardinality of the set {p(i)+i, i=1..n}.

			The 6 permutations p of [3]: 123, 132, 213, 231, 312, 321 have (signed) displacement sets {p(i)-i, i=1..3}: {0}, {-1,0,1}, {-1,0,1}, {-2,1}, {-1,2}, {-2,0,2}, representing the indices of covered falling diagonals in the permutation matrices
  [1    ]  [1    ]  [  1  ]  [  1  ]  [    1]  [    1]
  [  1  ]  [    1]  [1    ]  [    1]  [1    ]  [  1  ]
  [    1]  [  1  ]  [    1]  [1    ]  [  1  ]  [1    ] , respectively, the sum of the set cardinalities gives a(3) = 1 + 3 + 3 + 2 + 2 + 3 = 14.

Alois P. Heinz, Table of n, a(n) for n = 0..450
Wikipedia, Permutation
Wikipedia, Permutation matrix

Cf. A000142, A059841, A125182, A259834, A306234, A306461.

a:= proc(n) option remember; `if`(n<3, n*(n+1)/2,
      ((2*n^2-5*n+1)*a(n-1)-(n-1)*(n^2-4*n+2)*a(n-2)
      -(n-2)*(n-1)^2*a(n-3))/(n-2))
    end:
seq(a(n), n=0..23);

a[n_] := a[n] = If[n<3, n(n+1)/2, ((2n^2-5n+1) a[n-1] -
   (n-1)(n^2-4n+2) a[n-2] - (n-2)(n-1)^2 a[n-3])/(n-2)];
a /@ Range[0, 23] (* Jean-François Alcover, Aug 24 2021, after Alois P. Heinz *)

E.g.f.: (exp(-x)*(x+1)+x-1)/(x-1)^2.
a(n) = ((2*n^2-5*n+1)*a(n-1) - (n-1)*(n^2-4*n+2)*a(n-2) - (n-2)*(n-1)^2*a(n-3)) / (n-2) for n > 2, a(n) = n*(n+1)/2 for n < 3.
a(n) = Sum_{k=1..n} k * A125182(n,k).
a(n) = A259834(n+2) - n!.
a(n) = Sum_{k=1-n..n-1} A306461(n,k).
a(n) = Sum_{k=1-n..n-1} |k|! * A306234(n,k).
a(n) mod 2 = 1 - (n mod 2) = A059841(n) for n >= 2.

A125183 Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that the set {|p(i)-i|, i=1,2,...,n} has exactly k elements (1<=k<=n).

Original entry on oeis.org

1, 2, 0, 1, 5, 0, 3, 11, 6, 4, 1, 28, 55, 32, 4, 3, 69, 210, 330, 108, 0, 1, 102, 846, 2177, 1590, 324, 0, 4, 279, 2694, 11221, 17578, 7624, 888, 32, 1, 328, 7791, 54777, 135993, 123474, 37524, 2896, 96, 3, 961, 24032, 227906, 914364, 1427342, 839904, 182824, 11464, 0

Offset: 1

Emeric Deutsch, Nov 24 2006

Row sums are the factorial numbers (A000142). T(n,n) = A075866(n). In the Maple program define n (<=10) to obtain row n.

			T(4,3) = 6 because we have 1423, 1342, 3124, 4312, 2314 and 3421.
Triangle starts:
  1;
  2,  0;
  1,  5,   0;
  3, 11,   6,   4;
  1, 28,  55,  32,   4;
  3, 69, 210, 330, 108,  0;
  ...

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

Cf. A000142, A075866, A125182.

n:=7: with(combinat): P:=permute(n): for j from 1 to n! do c[j]:=0 od: for j from 1 to n! do if nops({seq(abs(P[j][i]-i),i=1..n)}) = 1 then c[1]:=c[1]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 2 then c[2]:=c[2]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 3 then c[3]:=c[3]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 4 then c[4]:=c[4]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 5 then c[5]:=c[5]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 6 then c[6]:=c[6]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 7 then c[7]:=c[7]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 8 then c[8]:=c[8]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 9 then c[9]:=c[9]+1 elif nops({seq(abs(P[j][i]-i),i=1..n)}) = 10 then c[10]:=c[10]+1 else fi od: seq(c[i],i=1..n); # yields row n for the specified n (n<=10)
# second Maple program:
b:= proc(p, s) option remember; `if`(p={}, x^nops(s),
      add(b(p minus {t}, s union {abs(t-nops(p))}), t=p))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b({$1..n}, {})):
seq(T(n), n=1..9);  # Alois P. Heinz, Feb 21 2019

b[p_, s_] := b[p, s] = If[p == {}, x^Length[s], Sum[b[p ~Complement~ {t}, s ~Union~ {Abs[t - Length[p]]}], {t, p}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, n}]][b[Range[n], {}]];
Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Dec 07 2019, after Alois P. Heinz *)

More terms from Alois P. Heinz, Feb 27 2012

cp's OEIS Frontend

A065608 Sum of divisors of n minus the number of divisors of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Python

Formula

A099152 Number of n X n permutation matrices in which the sums of the entries of each NorthEast-SouthWest diagonal are 0 or 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A306455 Total number of covered falling diagonals in all n X n permutation matrices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A125183 Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} such that the set {|p(i)-i|, i=1,2,...,n} has exactly k elements (1<=k<=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions