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

A163951 The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle.

Original entry on oeis.org

0, 0, 1, 9, 93, 1155, 17025, 292383, 5752131, 127790505, 3167896005, 86756071545, 2602658092419, 84917405260779, 2994675198208785, 113538315994418175, 4606094297461892895, 199122610252964803857, 9139190793845641425261, 443881600924216704982425

Offset: 0

Carlos Alves, Aug 06 2009

nonn

The number of functions in a finite set {1,..,n} for which the sequence of composition powers ends in a fixed point gave terms of the sequence A000272(n-1)=(n+1)^(n-1).

This is to be seen as a conjecture, and the sequence ending with a length 2 cycle does not seem to have such an easy expression.

			Any transposition (or disjoint combination) is one element to be counted.
When n=2, there is only one, and a(2)=1. When n=3, there are only 3 transpositions, but there are other 6 elements, for instance
f:{1,2,3}->{2,1,1} gives fof:{1,2,3}->{1,2,2} and fofof=f (cycle 2),
(the others are similar), thus giving a(3)=9.

Alois P. Heinz, Table of n, a(n) for n = 0..387

Cf. A163947, A163952, A163859.

Column k=2 of A222029 and of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 2) -A(n, 1):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 19 2014

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[(i - 1)!^j*multinomial[ n, Join[{n - i*j}, Table[i, j]]]/j!*b[n - i*j, i - 1], {j, 0, n/i}]]];
A[n_, k_] :=  Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, Min[j, k]], {j, 0, n}];
a[0] = 0; a[n_] := A[n, 2] - A[n, 1];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jun 05 2018, after Alois P. Heinz *)

a(n) ~ (2*exp(3/2)-exp(1)) * n^(n-1). - Vaclav Kotesovec, Aug 20 2014

a(0), a(8)-a(19) added and A246212 merged into this sequence by Alois P. Heinz, Aug 14 2017

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