A246049 -id:A246049 - cp's OEIS frontend

A045531 Number of sticky functions: endofunctions of [n] having a fixed point.

1, 3, 19, 175, 2101, 31031, 543607, 11012415, 253202761, 6513215599, 185311670611, 5777672071535, 195881901213181, 7174630439858727, 282325794823047151, 11878335717996660991, 532092356706983938321, 25283323623228812584415, 1270184310304975912766347

Offset: 1

Len Smiley

a(n) is also the number of functions f{1,2,...,n}->{1,2,...,n} with at least one element mapped to 1. - Geoffrey Critzer, Dec 10 2012
Equivalently, a(n) is the number of endofunctions with minimum 1. - Olivier Gérard, Aug 02 2016
Number of bargraphs of width n and height n. Equivalently: number of ordered n-tuples of positive integers such that the largest is n. Example: a(3) = 19 because we have 113, 123, 213, 223, 131, 132, 231, 232, 311, 312, 321, 322, 331, 332, 313, 323, 133, 233, and 333. - Emeric Deutsch, Jan 30 2017

Vincenzo Librandi, Table of n, a(n) for n = 1..100
A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, The height and width of bargraphs, Discrete Applied Math. 180, (2015), 36-44.

Column |a(n, 2)| of A039621. Row sums of triangle A055858.
Cf. A000312, A066274, A066275, A047969.
Column k=1 of A246049.
Cf. A068996, A350454.

[n^n-(n-1)^n: n in [1..20] ]; // Vincenzo Librandi, May 07 2011

Table[Sum[Binomial[n, i] (n - 1)^(n - i), {i, 1, n}], {n, 1, 20}]

a(n) = sum(k!*binomial(n-1,k-1)*stirling2(n,k),k,1,n); /* Vladimir Kruchinin, Mar 01 2014 */

a(n)=n^n-(n-1)^n; \\ Charles R Greathouse IV, May 08 2011

a(n) = n^n - (n-1)^n.
E.g.f.: (T - x)/(T-T^2), where T=T(x) is Euler's tree function (see A000169).
With interpolated zeros, ceiling(n/2)^ceiling(n/2) - floor(n/2)^ceiling(n/2). - Paul Barry, Jul 13 2005
a(n) = A047969(n,n). - Alford Arnold, May 07 2005
a(n) = Sum_{i=1..n} binomial(n,i)*(i-1)^(i-1)*(n-i)^(n-i) = Sum_{i=1..n} binomial(n,i)*A000312(i-1)*A000312(n-i). - Vladimir Shevelev, Sep 30 2010
a(n) = Sum_{k=1..n} k!*binomial(n-1,k-1)*Stirling2(n,k). - Vladimir Kruchinin, Mar 01 2014
a(n) = A350454(n+1, 1) / (n+1). - Mélika Tebni, Dec 20 2022
Limit_{n->oo} a(n)/n^n = 1 - 1/e = A068996. - Luc Rousseau, Jan 20 2023

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

Alois P. Heinz, Aug 10 2014

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

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

Alois P. Heinz, Rows n = 0..140, flattened

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.

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

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

A243098 Number T(n,k) of endofunctions on [n] with all cycles of length 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, 6, 2, 0, 125, 51, 24, 6, 0, 1296, 560, 300, 120, 24, 0, 16807, 7575, 4360, 2160, 720, 120, 0, 262144, 122052, 73710, 41160, 17640, 5040, 720, 0, 4782969, 2285353, 1430016, 861420, 430080, 161280, 40320, 5040

Offset: 0

Alois P. Heinz, Aug 18 2014

T(0,0) = 1 by convention.

			Triangle T(n,k) begins:
  1;
  0,      1;
  0,      3,      1;
  0,     16,      6,     2;
  0,    125,     51,    24,     6;
  0,   1296,    560,   300,   120,    24;
  0,  16807,   7575,  4360,  2160,   720,  120;
  0, 262144, 122052, 73710, 41160, 17640, 5040, 720;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-4 give: A000007, A000272(n+1) for n>0, A057817(n+1), 2*A060917, 6*A060918.
Row sums give A241980.
T(2n,n) gives A246050.
Main diagonal gives A000142(n-1) for n>0.
Cf. A241981, A246049.

with(combinat):
T:= (n, k)-> `if`(k*n=0, `if`(k+n=0, 1, 0),
    add(binomial(n-1, j*k-1)*n^(n-j*k)*(k-1)!^j*
    multinomial(j*k, k$j, 0)/j!, j=0..n/k)):
seq(seq(T(n, k), k=0..n), n=0..10);

multinomial[n_, k_] := n!/Times @@ (k!); T[n_, k_] := If[k*n==0, If[k+n == 0, 1, 0], Sum[Binomial[n-1, j*k-1]*n^(n-j*k)*(k-1)!^j*multinomial[j*k, Append[Array[k&, j], 0]]/j!, {j, 0, n/k}]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 19 2017, translated from Maple *)

E.g.f. of column k>0: exp((-LambertW(-x))^k/k), e.g.f. of column k=0: 1.

A246050 Number of endofunctions on [2n] where the smallest cycle length equals n.

Original entry on oeis.org

1, 3, 51, 4360, 861420, 302472576, 165549605760, 130241382036480, 139296260790086400, 194427690066299289600, 343266609438110040883200, 747889929370001008617062400, 1971026055567996899374212710400, 6180432763819774878006029844480000

Offset: 0

Alois P. Heinz, Aug 11 2014

nonn

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

Cf. A241982, A246049, A243098.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 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, k), j=0..n):
a:= n-> `if`(n=0, 1, A(2*n, n) -A(2*n, n+1)):
seq(a(n), n=0..15);

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i>n, 0, Sum[(i-1)!^j*multinomial[n, Join[{n-i*j}, Array[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, k], {j, 0, n}]; a[n_] := If[n == 0, 1, A[2*n, n] - A[2*n, n+1]]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Feb 11 2015, after Alois P. Heinz *)

a(n) = A246049(2n,n) = A243098(2n,n).

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

A246189 Number of endofunctions on [n] where the smallest cycle length equals 2.

Original entry on oeis.org

1, 6, 51, 580, 8265, 141246, 2810437, 63748728, 1622579985, 45775778950, 1417347491241, 47776074289164, 1741386177576409, 68238497945688630, 2860625245955274225, 127736893134458097136, 6052712065187733972513, 303322427195785592735502, 16028016368907840953165425

Offset: 2

Alois P. Heinz, Aug 18 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..200

Column k=2 of A246049.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 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, k), j=0..n):
a:= n-> A(n, 2) -A(n, 3):
seq(a(n), n=2..25);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n==0, 1, If[i>n, 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, k], {j, 0, n}];
a[n_] := A[n, 2] - A[n, 3];
a /@ Range[2, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

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

A246190 Number of endofunctions on [n] where the smallest cycle length equals 3.

Original entry on oeis.org

2, 24, 300, 4360, 74130, 1456224, 32562152, 817596000, 22785399450, 697951656160, 23306666102148, 842567564800416, 32781106696806650, 1365579024023558400, 60639189588419033040, 2859165143013913590016, 142651621238828972159538, 7508140027468431374563200

Offset: 3

Alois P. Heinz, Aug 18 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..200

Column k=3 of A246049.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 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, k), j=0..n):
a:= n-> A(n, 3) -A(n, 4):
seq(a(n), n=3..25);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n==0, 1, If[i>n, 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, k], {j, 0, n}];
a[n_] := A[n, 3] - A[n, 4];
a /@ Range[3, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

a(n) ~ (exp(-3/2) - exp(-11/6)) * n^n. - Vaclav Kotesovec, Aug 21 2014

A246191 Number of endofunctions on [n] where the smallest cycle length equals 4.

Original entry on oeis.org

6, 120, 2160, 41160, 861420, 19949328, 510320160, 14348862000, 440879024520, 14716697990280, 530761366078944, 20577610843203960, 853717568817968400, 37746072677473752480, 1771994498414094109440, 88032162789004128733152, 4614300279345812506938720

Offset: 4

Alois P. Heinz, Aug 18 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..200

Column k=4 of A246049.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 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, k), j=0..n):
a:= n-> A(n, 4) -A(n, 5):
seq(a(n), n=4..25);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n==0, 1, If[i>n, 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, k], {j, 0, n}];
a[n_] := A[n, 4] - A[n, 5];
a /@ Range[4, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

a(n) ~ (exp(-11/6) - exp(-25/12)) * n^n. - Vaclav Kotesovec, Aug 21 2014

A246192 Number of endofunctions on [n] where the smallest cycle length equals 5.

Original entry on oeis.org

24, 720, 17640, 430080, 11022480, 302472576, 8937981360, 284552040960, 9743091569640, 357820740076800, 14051646110285784, 588177615908413440, 26161789829441054880, 1232890909824506204160, 61387038018996808785120, 3221070809733138102829056

Offset: 5

Alois P. Heinz, Aug 18 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 5..200

Column k=5 of A246049.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 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, k), j=0..n):
a:= n-> A(n, 5) -A(n, 6):
seq(a(n), n=5..25);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n==0, 1, If[i>n, 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, k], {j, 0, n}];
a[n_] := A[n, 5] - A[n, 6];
a /@ Range[5, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

a(n) ~ (exp(-25/12) - exp(-137/60)) * n^n. - Vaclav Kotesovec, Aug 21 2014

A246193 Number of endofunctions on [n] where the smallest cycle length equals 6.

Original entry on oeis.org

120, 5040, 161280, 4898880, 151200000, 4870182240, 165549605760, 5964805154880, 228051369786240, 9247246914906000, 397146441431900160, 18033691478872567680, 864117601222345666560, 43606402916521420059840, 2312912761606956925440000, 128696545326829348772023680

Offset: 6

Alois P. Heinz, Aug 18 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..200

Column k=6 of A246049.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 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, k), j=0..n):
a:= n-> A(n, 6) -A(n, 7):
seq(a(n), n=6..25);

a(n) ~ (exp(-137/60) - exp(-49/20)) * n^n. - Vaclav Kotesovec, Aug 21 2014

A246194 Number of endofunctions on [n] where the smallest cycle length equals 7.

Original entry on oeis.org

720, 40320, 1632960, 60480000, 2213719200, 82771476480, 3211179491520, 130241382036480, 5541589755702000, 247667354552217600, 11627089698327143040, 573008938660751523840, 29613698207957813302080, 1602975684200327700480000, 90757379602253683020931200

Offset: 7

Alois P. Heinz, Aug 18 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..200

Column k=7 of A246049.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 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, k), j=0..n):
a:= n-> A(n, 7) -A(n, 8):
seq(a(n), n=7..25);

a(n) ~ (exp(-49/20) - exp(-363/140)) * n^n. - Vaclav Kotesovec, Aug 21 2014

cp's OEIS Frontend

A045531 Number of sticky functions: endofunctions of [n] having a fixed point.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A243098 Number T(n,k) of endofunctions on [n] with all cycles of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246050 Number of endofunctions on [2n] where the smallest cycle length equals n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246189 Number of endofunctions on [n] where the smallest cycle length equals 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246190 Number of endofunctions on [n] where the smallest cycle length equals 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246191 Number of endofunctions on [n] where the smallest cycle length equals 4.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246192 Number of endofunctions on [n] where the smallest cycle length equals 5.

Views

Author