login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A222029
Triangle of number of functions in a size n set for which the sequence of composition powers ends in a length k cycle.
15
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
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
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
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