cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A246212 Duplicate of A163951.

Original entry on oeis.org

1, 9, 93, 1155, 17025, 292383, 5752131, 127790505, 3167896005, 86756071545, 2602658092419, 84917405260779, 2994675198208785, 113538315994418175
Offset: 2

Views

Author

Keywords

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

Original entry on oeis.org

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

Views

Author

Chad Brewbaker, May 14 2013

Keywords

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

Examples

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

Links

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.

Programs

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

Formula

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

Extensions

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

A241981 Number T(n,k) of endofunctions on [n] where the largest cycle length equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 3, 1, 0, 16, 9, 2, 0, 125, 93, 32, 6, 0, 1296, 1155, 500, 150, 24, 0, 16807, 17025, 8600, 3240, 864, 120, 0, 262144, 292383, 165690, 72030, 24696, 5880, 720, 0, 4782969, 5752131, 3568768, 1719060, 688128, 215040, 46080, 5040
Offset: 0

Views

Author

Alois P. Heinz, Aug 10 2014

Keywords

Comments

T(0,0) = 1 by convention.
In general, number of endofunctions on [n] where the largest cycle length equals k is asymptotic to (k*exp(H(k)) - (k-1)*exp(H(k-1))) * n^(n-1), where H(k) is the harmonic number A001008/A002805, k>=1. The multiplicative constant is (for big k) asymptotic to 2*k*exp(gamma), where gamma is the Euler-Mascheroni constant (see A001620 and A073004). - Vaclav Kotesovec, Aug 21 2014

Examples

			Triangle T(n,k) begins:
  1;
  0,      1;
  0,      3,      1;
  0,     16,      9,      2;
  0,    125,     93,     32,     6;
  0,   1296,   1155,    500,   150,    24;
  0,  16807,  17025,   8600,  3240,   864,  120;
  0, 262144, 292383, 165690, 72030, 24696, 5880, 720;
  ...

Links

Crossrefs

Columns k=0-10 give: A000007, A000272(n+1) for n>0, A163951, A246213, A246214, A246215, A246216, A246217, A246218, A246219, A246220.
T(2n,n) gives A241982.
Row sums give A000312.
Main diagonal gives A000142(n-1) for n>0.
Cf. A246049, A243098.

Programs

  • Maple
    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):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..10);
  • Mathematica
    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, {n-i*j, Sequence @@ 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}]; T[0, 0] = 1; T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k-1]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 06 2015, after Alois P. Heinz *)

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

Original entry on oeis.org

0, 0, 0, 2, 32, 480, 7880, 145320, 3009888, 69554240, 1779185360, 49995179520, 1532580072320, 50934256044672, 1825145974743000, 70172455476381440, 2882264153273207360, 125985060813367664640, 5840066736661562391968, 286204501001426735001600
Offset: 0

Views

Author

Carlos Alves, Aug 07 2009

Keywords

Comments

See A163951 for the cases ending with length 2 cycles and fixed points.

Examples

			Any period 3 permutation (or disjoint combinations) is one element to be counted.
For n=3, where there are only 2 cases: f1:{1,2,3}->{2,3,1} and f2:{1,2,3}->{3,1,2} but for n>3 there are other elements (non-permutations) to be counted (for instance, with n=5, we count with f:{1,2,3,4,5}->{2,4,5,3,4}).

Links

Crossrefs

Cf. A163951, A163947, A163859.
Column k=3 of A222029.

Programs

  • Maple
    b:= proc(n, m) option remember; `if`(m>3, 0, `if`(n=0, x^m, add(
      (j-1)!*b(n-j, ilcm(m, j))*binomial(n-1, j-1), j=1..n)))
    end:
a:= n-> coeff(add(b(j, 1)*n^(n-j)*binomial(n-1, j-1), j=0..n), x, 3):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 14 2017
  • Mathematica
    b[n_, m_] := b[n, m] = If[m>3, 0, If[n == 0, x^m, Sum[(j - 1)! b[n - j, LCM[m, j]] Binomial[n - 1, j - 1], {j, 1, n}]]];
a[n_] := If[n==0, 0, Coefficient[Sum[b[j, 1] n^(n-j) Binomial[n-1, j-1], {j, 0, n}], x, 3]];
a /@ Range[0, 25] (* Jean-François Alcover, Dec 18 2020, after Alois P. Heinz *)

Formula

a(n) ~ (2*exp(4/3)-exp(1)) * n^(n-1). - Vaclav Kotesovec, Aug 18 2017

Extensions

a(0), a(8)-a(19) from Alois P. Heinz, Aug 14 2017
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.