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,3

Comments

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}|.

Links

Alois P. Heinz, Rows n = 0..30, flattened

Chad Brewbaker, Ruby program for A222029

Formula

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

Example

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;
  ...

Maple

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

Mathematica

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 *)

Prog

#(Ruby 1.9+) see link.
(Python)
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

Crossrefs

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.

Sequence in context: A102012 A128249 A071211 * A038675 A264902 A350446

Adjacent sequences: A222026 A222027 A222028 * A222030 A222031 A222032

Keyword

nonn,look,tabf

Author

Chad Brewbaker, May 14 2013

Extensions

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

Status

approved