A162682 -id:A162682 - 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

A074859 Number of elements of S_n having the maximum possible order g(n), where g(n) is Landau's function (A000793).

Original entry on oeis.org

1, 1, 1, 2, 6, 20, 240, 420, 2688, 18144, 120960, 2661120, 7983360, 103783680, 1037836800, 12454041600, 149448499200, 1693749657600, 60974987673600, 289631191449600, 5792623828992000, 121645100408832000, 3568256278659072000, 30776210403434496000, 738629049682427904000, 12310484161373798400000

Offset: 0

Christopher J. Smyth, Sep 11 2002

J.-L. Nicolas, On Landau's function g(n), pp. 228-240 of R. L. Graham et al., eds., Mathematics of Paul Erdős I.

Alois P. Heinz, Table of n, a(n) for n = 0..175
J. Kuzmanovich and A. Pavlichenkov, Finite groups of matrices whose entries are integers, Amer. Math. Monthly, 109 (2002), 173-186.
W. Miller, The Maximum Order of an Element of Finite Symmetric Group, Am. Math. Monthly, Jun-Jul 1987, pp. 497-506.
J.-L. Nicolas, Sur l'ordre maximum d'un élément dans le groupe S_n des permutations, Acta Arith., 14 (1968), 315-332.
J.-L. Nicolas, Ordre maximal d'un élément du groupe S_n de permutations et 'highly composite numbers', Bull. Math. Soc. France 97 (1969) 129-191.

Cf. A000793 (Landau's function g(n)).
Cf. A074064, A074103, A074115, A162682.
Last row element of A057731. - Alois P. Heinz, Feb 14 2013

g[n_] := Max[ Apply[ LCM, IntegerPartitions[n], 1]]; f[x_, n_] := Total[ (MoebiusMu[g[n]/#]*Exp[ Total[ (x^#/# & ) /@ Divisors[#]]] & ) /@ Divisors[g[n]]]; a[n_] := n!*Coefficient[ Series[f[x, n], {x, 0, n}], x^n]; Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Nov 03 2011, after Vladeta Jovovic *)

a(n) = n!*coefficient of x^n in expansion of Sum_{i divides A000793(n)} mu(A000793(n)/i)*exp(Sum_{j divides i} x^j/j). - Vladeta Jovovic, Sep 29 2002

Corrected and extended by Vladeta Jovovic, Sep 20 2002

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