A290932 -id:A290932 - cp's OEIS frontend

A222029 Triangle of number of functions in a size n set for which the sequence of composition powers ends in a length k cycle.

1, 1, 3, 1, 16, 9, 2, 125, 93, 32, 6, 1296, 1155, 480, 150, 24, 20, 16807, 17025, 7880, 3240, 864, 840, 262144, 292383, 145320, 71610, 24192, 26250, 720, 0, 0, 504, 0, 420, 4782969, 5752131, 3009888, 1692180, 653184, 773920, 46080, 5040, 0, 32256, 0, 26880, 0, 0, 2688

Offset: 0

Chad Brewbaker, May 14 2013

If you take the powers of a finite function you generate a lollipop graph. This table organizes the lollipops by cycle size. The table organized by total lollipop size with the tail included is A225725.

Warning: For T(n,k) after the sixth row there are zero entries and k can be greater than n: T(7,k) = |{1=>262144, 2=>292383, 3=>145320, 4=>71610, 5=>24192, 6=>26250, 7=>720, 8=>0, 9=>0, 10=>504, 11=>0, 12=>420}|.

			T(1,1) = |{[0]}|, T(2,1) = |{[0,0],[0,1],[1,1]}|, T(2,2) = |{[0,1]}|.
Triangle starts:
       1;
       1;
       3,      1;
      16,      9,      2;
     125,     93,     32,     6;
    1296,   1155,    480,   150,    24,    20;
   16807,  17025,   7880,  3240,   864,   840;
  262144, 292383, 145320, 71610, 24192, 26250, 720, 0, 0, 504, 0, 420;
  ...

Alois P. Heinz, Rows n = 0..30, flattened
Chad Brewbaker, Ruby program for A222029

Columns k=1-10 give A000272, A163951, A163952, A291110, A291111, A291112, A291113, A291114, A291115, A291116.
Rows sums give A000312.
Row lengths are A000793.
Number of nonzero elements of rows give A009490.
Last elements of rows give A162682.
Main diagonal gives A290961.
Cf. A057731 (the same for permutations), A290932.

b:= proc(n, m) option remember; `if`(n=0, x^m, add((j-1)!*
      b(n-j, ilcm(m, j))*binomial(n-1, j-1), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(add(
         b(j, 1)*n^(n-j)*binomial(n-1, j-1), j=0..n)):
seq(T(n), n=0..10);  # Alois P. Heinz, Aug 14 2017

b[n_, m_]:=b[n, m]=If[n==0, x^m, Sum[(j - 1)!*b[n - j, LCM[m, j]] Binomial[n - 1, j - 1], {j, n}]]; T[n_]:=If[n==0, {1}, Drop[CoefficientList[Sum[b[j, 1]n^(n - j)*Binomial[n - 1, j - 1], {j, 0, n}], x], 1]]; Table[T[n], {n, 0, 10}]//Flatten (* Indranil Ghosh, Aug 17 2017 *)

from sympy.core.cache import cacheit
from sympy import binomial, Symbol, lcm, factorial as f, Poly, flatten
x=Symbol('x')
@cacheit
def b(n, m): return x**m if n==0 else sum([f(j - 1)*b(n - j, lcm(m, j))*binomial(n - 1, j - 1) for j in range(1, n + 1)])
def T(n): return Poly(sum([b(j, 1)*n**(n - j)*binomial(n - 1, j - 1) for j in range(n + 1)]),x).all_coeffs()[::-1][1:]
print([T(n) for n in range(11)]) # Indranil Ghosh, Aug 17 2017

Sum_{k=1..A000793(n)} k * T(n,k) = A290932. - Alois P. Heinz, Aug 14 2017

T(0,1)=1 prepended by Alois P. Heinz, Aug 14 2017

A060014 Sum of orders of all permutations of n letters.

Original entry on oeis.org

1, 1, 3, 13, 67, 471, 3271, 31333, 299223, 3291487, 39020911, 543960561, 7466726983, 118551513523, 1917378505407, 32405299019941, 608246253790591, 12219834139189263, 253767339725277823, 5591088918313739017, 126036990829657056711, 2956563745611392385211

Offset: 0

N. J. A. Sloane, Mar 17 2001

Conjecture: This sequence eventually becomes cyclic mod n for all n. - Isaac Saffold, Dec 01 2019

			For n = 4 there is 1 permutation of order 1, 9 permutations of order 2, 8 of order 3 and 6 of order 4, for a total of 67.

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIII.2, p. 460.

Alois P. Heinz, Table of n, a(n) for n = 0..170
FindStat - Combinatorial Statistic Finder, The order of a permutation
Joshua Harrington, Lenny Jones, and Alicia Lamarche, Characterizing Finite Groups Using the Sum of the Orders of the Elements, International Journal of Combinatorics, Volume 2014, Article ID 835125, 8 pages.

Cf. A000793, A028418, A060015, A057731, A074859, A290932, A346066.

b:= proc(n, g) option remember; `if`(n=0, g, add((j-1)!
      *b(n-j, ilcm(g, j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 11 2017

CoefficientList[Series[Sum[n Fold[#1+MoebiusMu[n/#2] Apply[Times, Exp[x^#/#]&/@Divisors[#2] ]&,0,Divisors[n]],{n,Max[Apply[LCM,Partitions[19],1]]}],{x,0,19}],x] Range[0,19]! (* Wouter Meeussen, Jun 16 2012 *)
a[ n_] := If[ n < 1, Boole[n == 0], 1 + Total @ Apply[LCM, Map[Length, First /@ PermutationCycles /@ Drop[Permutations @ Range @ n, 1], {2}], 1]]; (* Michael Somos, Aug 19 2018 *)

\\ Naive method -- sum over cycles directly
cycleDecomposition(v:vec)={
    my(cyc=List(), flag=#v+1, n);
    while((n=vecmin(v))<#v,
        my(cur=List(), i, tmp);
        while(v[i++]!=n,);
        while(v[i] != flag,
            listput(cur, tmp=v[i]);
            v[i]=flag;
            i=tmp
        );
        if(#cur>1, listput(cyc, Vec(cur)))    \\ Omit length-1 cycles
    );
    Vec(cyc)
};
permutationOrder(v:vec)={
    lcm(apply(length, cycleDecomposition(v)))
};
a(n)=sum(i=0,n!-1,permutationOrder(numtoperm(n,i)))
\\ Charles R Greathouse IV, Nov 06 2014

A060014(n) =
{
  my(factn = n!, part, nb, i, j, res = 0);
  forpart(part = n,
    nb = 1; j = 1;
    for(i = 1, #part,
      if (i == #part || part[i + 1] != part[i],
        nb *= (i + 1 - j)! * part[i]^(i + 1 - j);
        j = i + 1));
    res += (factn / nb) * lcm(Vec(part)));
  res;
} \\ Jerome Raulin, Jul 11 2017 (much faster, O(A000041(n)) vs O(n!))

E.g.f.: Sum_{n>0} (n*Sum_{i|n} (moebius(n/i)*Product_{j|i} exp(x^j/j))). - Vladeta Jovovic, Dec 29 2004; The sum over n should run to at least A000793(k) for producing the k-th entry. - Wouter Meeussen, Jun 16 2012

a(n) = Sum_{k>=1} k* A057731(n,k). - R. J. Mathar, Aug 31 2017

More terms from Vladeta Jovovic, Mar 18 2001

More terms from Alois P. Heinz, Feb 14 2013

A208231 Sum of the minimum cycle length over all functions f:{1,2,...,n}->{1,2,...,n} (endofunctions).

Original entry on oeis.org

0, 1, 5, 37, 373, 4761, 73601, 1336609, 27888281, 657386305, 17276807089, 500876786301, 15879053677697, 546470462226313, 20288935994319929, 808320431258439121, 34397370632215764001, 1557106493482564625793, 74713970491718324746529, 3787792171563440619543133, 202314171910557294992453009

Offset: 0

Geoffrey Critzer, Jan 10 2013

nonn

Sum of the number of endofunctions whose cycle lengths are >=i for all i >=1. A000312 + A065440 + A134362 + A208230 + ...

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

Cf. A000169, A028417, A000312, A065440, A134362, A208230, A208248, A290932.

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

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Apply[Plus,Table[Range[0,nn]!CoefficientList[Series[Exp[Sum[t^i/i,{i,n,nn}]]-1,{x,0,nn}],x],{n,1,nn}]]

E.g.f.: A(T(x)) = Sum_{k>=1} exp( Sum_{i>=k} T(x)^i/i) - 1 where A(x) is the e.g.f. for A028417 and T(x) is the e.g.f. for A000169.

A208248 Sum of the maximum cycle length over all functions f:{1,2,...,n} -> {1,2,...,n} (endofunctions).

Original entry on oeis.org

0, 1, 5, 40, 431, 5826, 94657, 1795900, 38963535, 951398890, 25819760021, 770959012704, 25117397416795, 886626537549130, 33708625339151505, 1373237757290215156, 59677939242566840303, 2755753623830236494930, 134746033233724391374765, 6954962673986411576581000

Offset: 0

Geoffrey Critzer, Jan 12 2013

nonn

a(n) is also the sum of the number of endofunctions with at least one cycle >= i for all i >= 1. In other words, a(n) = A000312(n) + A101334(n) + A208240(n) + ... .

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

Cf. A000169, A028418, A000312, A101334, A208231, A208240, A290932.

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-> add(b(j, 0)*n^(n-j)*binomial(n-1, j-1), j=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 20 2016

nn=20; t=Sum[n^(n-1)x^n/n!, {n,1,nn}]; Apply[Plus, Table[Range[0,nn]! CoefficientList[Series[1/(1-t) - Exp[Sum[t^i/i, {i,1,n}]], {x,0,nn}], x], {n, 0, nn-1}]]

E.g.f.: Sum_{k>=0} 1/(1-T(x)) - exp(Sum_{i=1...k} T(x)^i/i) = A(T(x)) where A(x) is the e.g.f. for A028418 and T(x) is the e.g.f. for A000169.

cp's OEIS Frontend

A222029 Triangle of number of functions in a size n set for which the sequence of composition powers ends in a length k cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A060014 Sum of orders of all permutations of n letters.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A208231 Sum of the minimum cycle length over all functions f:{1,2,...,n}->{1,2,...,n} (endofunctions).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A208248 Sum of the maximum cycle length over all functions f:{1,2,...,n} -> {1,2,...,n} (endofunctions).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula