A222029 - OEIS

%I #67 Mar 21 2021 13:00:11

%S 1,1,3,1,16,9,2,125,93,32,6,1296,1155,480,150,24,20,16807,17025,7880,

%T 3240,864,840,262144,292383,145320,71610,24192,26250,720,0,0,504,0,

%U 420,4782969,5752131,3009888,1692180,653184,773920,46080,5040,0,32256,0,26880,0,0,2688

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

%C 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.

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

%H Alois P. Heinz, <a href="/A222029/b222029.txt">Rows n = 0..30, flattened</a>

%H Chad Brewbaker, <a href="/A222029/a222029.txt">Ruby program for A222029</a>

%F Sum_{k=1..A000793(n)} k * T(n,k) = A290932. - _Alois P. Heinz_, Aug 14 2017

%e T(1,1) = |{[0]}|, T(2,1) = |{[0,0],[0,1],[1,1]}|, T(2,2) = |{[0,1]}|.

%e Triangle starts:

%e        1;

%e        1;

%e        3,      1;

%e       16,      9,      2;

%e      125,     93,     32,     6;

%e     1296,   1155,    480,   150,    24,    20;

%e    16807,  17025,   7880,  3240,   864,   840;

%e   262144, 292383, 145320, 71610, 24192, 26250, 720, 0, 0, 504, 0, 420;

%e   ...

%p b:= proc(n, m) option remember; `if`(n=0, x^m, add((j-1)!*

%p       b(n-j, ilcm(m, j))*binomial(n-1, j-1), j=1..n))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(add(

%p          b(j, 1)*n^(n-j)*binomial(n-1, j-1), j=0..n)):

%p seq(T(n), n=0..10);  # _Alois P. Heinz_, Aug 14 2017

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

%o #(Ruby 1.9+) see link.

%o (Python)

%o from sympy.core.cache import cacheit

%o from sympy import binomial, Symbol, lcm, factorial as f, Poly, flatten

%o x=Symbol('x')

%o @cacheit

%o 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)])

%o 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:]

%o print([T(n) for n in range(11)]) # _Indranil Ghosh_, Aug 17 2017

%Y Columns k=1-10 give A000272, A163951, A163952, A291110, A291111, A291112, A291113, A291114, A291115, A291116.

%Y Rows sums give A000312.

%Y Row lengths are A000793.

%Y Number of nonzero elements of rows give A009490.

%Y Last elements of rows give A162682.

%Y Main diagonal gives A290961.

%Y Cf. A057731 (the same for permutations), A290932.

%K nonn,look,tabf

%O 0,3

%A _Chad Brewbaker_, May 14 2013

%E T(0,1)=1 prepended by _Alois P. Heinz_, Aug 14 2017