login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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 xrange(1, n + 1)])

def T(n): return Poly(sum([b(j, 1)*n**(n - j)*binomial(n - 1, j - 1) for j in xrange(n + 1)])).all_coeffs()[::-1][1:]

print flatten(map(T, xrange(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 A156653

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 08:47 EDT 2019. Contains 328292 sequences. (Running on oeis4.)