A066052 -id:A066052 - cp's OEIS frontend

A028418 Sum over all n! permutations of n letters of maximum cycle length.

1, 3, 13, 67, 411, 2911, 23563, 213543, 2149927, 23759791, 286370151, 3734929903, 52455166063, 788704078527, 12648867695311, 215433088624351, 3884791172487903, 73919882720901823, 1480542628345939807, 31128584449987511871, 685635398619169059391

Offset: 1

Joe Keane (jgk(AT)jgk.org)

nonn

Sum the n-permutations having at least 1 cycle of length >= i for all i >= 1. A000142 + A033312 + A066052 + A202364 + ... The summation is precisely that indicated in the title since each permutation whose longest cycle = i is counted i times. - Geoffrey Critzer, Jan 09 2013

S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967, p. 183.
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 142 terms from Thomas Dybdahl Ahle)
Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, p. 22.

Cf. A006128, A028417, A060014, A126074.

Column k=1 of A322384.

b:= proc(n, m) option remember; `if`(n=0, m, add((j-1)!*
      b(n-j, max(m,j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=1..25);  # Alois P. Heinz, May 14 2016

kmax = 19; gf[x_] = Sum[ 1/(1-x) - 1/(E^((x^(1+k)*Hypergeometric2F1[1+k, 1, 2+k, x])/ (1+k))*(1-x)), {k, 0, kmax}];
a[n_] := n!*Coefficient[Series[gf[x], {x, 0, kmax}], x^n]; Array[a, kmax]
(* Jean-François Alcover, Jun 22 2011, after e.g.f. *)
a[ n_] := If[ n < 1, 0, 1 + Total @ Apply[ Max, Map[ Length, First /@ PermutationCycles /@ Drop[ Permutations @ Range @ n, 1], {2}], 1]]; (* Michael Somos, Aug 19 2018 *)

E.g.f.: Sum_{k>=0} (1/(1-x) - exp(Sum_{j=1..k} x^j/j)).
a(n) = f(n, 0, n, n!) where f(L, r, n, m) = m*r if r >= l, otherwise Sum_{k=0..L-1} (f(k, max(L-k,r), n-1, m/n) + (n-L)*f(L, r, n-1, m/n)). - Thomas Dybdahl Ahle, Aug 15 2011
a(n) = Sum_{k=1..n} k * A126074(n,k). - Alois P. Heinz, May 17 2016

More terms from Vladeta Jovovic, Sep 19 2002

More terms from Thomas Dybdahl Ahle, Aug 15 2011

A072148 Number of invertible (-1,0,1) n X n matrices having (Tij = -Tji; i

Original entry on oeis.org

2, 14, 92, 796, 7672, 83944

Offset: 1

Wouter Meeussen, Aug 25 2003

The matrix powers T^k reach identity I for k a divisor of 12. All T^k are invertible (-1,0,1)-matrices with determinant +/-1. The matrix |Tij| is symmetric. The matrices T are "pseudo-anti-symmetric" (that is Tij=-Tji except for the main diagonal, or, equivalently, the sum of an anti-symmetric and a diagonal matrix). Their eigenvalues belong to {-1, -I, I, 1, -(-1)^(1/3), (-1)^(1/3), -(-1)^(2/3), (-1)^(2/3)}.

			{{1,-1,0,0,0},{1,0,0,0,0},{0,0,0,-1,0},{0,0,1,1,0},{0,0,0,0,-1}}
qualifies since its powers are:
{{0,-1,0,0,0},{1,-1,0,0,0},{0,0,-1,-1,0},{0,0,1,0,0},{0,0,0,0,1}},
{{-1,0,0,0,0},{0,-1,0,0,0},{0,0,-1,0,0},{0,0,0,-1,0},{0,0,0,0,-1}},
{{-1,1,0,0,0},{-1,0,0,0,0},{0,0,0,1,0},{0,0,-1,-1,0},{0,0,0,0,1}},
{{0,1,0,0,0},{-1,1,0,0,0},{0,0,1,1,0},{0,0,-1,0,0},{0,0,0,0,-1}},
{{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}}.

Cf. A081959 A002464 A020063 A033169 A090410 A066052.

triamatsig[li_List] := Block[{len=Sqrt[8Length[li]+1]/2-1/2}, If[IntegerQ[len], (Part[li, # ]&/@ Table[If[j>i, j(j-1)/2+i, i(i-1)/2+j], {i, len}, {j, len}])Table[If[j>i, -1, 1], {i, len}, {j, len}], li]]; n=4; it=triamatsig/@(-1+IntegerDigits[Range[0, -1+3^(n(n+1)/2)], 3, n(n+1)/2]); result4=Cases[it, (q_?MatrixQ)/; Det[q]=!=0 && And@@ Table[Union[Flatten[{MatrixPower[q, k], {-1, 0, 1}}]]==={-1, 0, 1}, {k, 25}]]

a(6) from Wouter Meeussen, Nov 15 2005

A202364 Number of n-permutations with at least one cycle of length >=4.

Original entry on oeis.org

0, 0, 0, 0, 6, 54, 444, 3828, 34404, 331812, 3457224, 38902104, 472682088, 6185876904, 86896701072, 1305666612144, 20907918062064, 355572850545648, 6401460197543904, 121637573726005152, 2432837939316094944, 51090380436082401504, 1123995659389121919168

Offset: 0

Geoffrey Critzer, Jan 09 2013

nonn

a(n) = n! - A057693(n). - Vaclav Kotesovec, Oct 09 2013

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 358.

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

Cf. A000142, A033312, A066052, A028418.

b:= proc(n) option remember; `if`(n<4, [6, 54, 444, 3828][n+1],
      ((5*n+3+n^2)*b(n-1) -(n+3)*b(n-2) -(n+3)*(n+2)*b(n-3)
      -(n+3)*(n+2)*(n+1)^2*b(n-4))/n)
    end:
a:= n-> `if`(n<4, 0, b(n-4)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 09 2013

nn=25;Range[0,nn]!CoefficientList[Series[1/(1-x)-Exp[x+x^2/2+x^3/3],{x,0,nn}],x]
(* Second program: *)
b[n_] := b[n] = If[n<4, {6, 54, 444, 3828}[[n+1]], ((5*n+3+n^2)*b[n-1] - (n + 3)*b[n-2] - (n+3)*(n+2)*b[n-3] - (n+3)*(n+2)*(n+1)^2*b[n-4])/n]; a[n_] := If[n<4, 0, b[n-4]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 08 2017, after Alois P. Heinz *)

E.g.f.: 1/(1-x) - exp(x + x^2/2 + x^3/3).

cp's OEIS Frontend

A028418 Sum over all n! permutations of n letters of maximum cycle length.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A072148 Number of invertible (-1,0,1) n X n matrices having (Tij = -Tji; i

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A202364 Number of n-permutations with at least one cycle of length >=4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula