A055134 -id:A055134 - cp's OEIS frontend

A055135 Matrix inverse of triangle A055134.

1, 0, 1, -1, -2, 1, -2, 0, -6, 1, -3, 0, 18, -12, 1, -4, 0, -40, 80, -20, 1, -5, 0, 75, -400, 225, -30, 1, -6, 0, -126, 1680, -1890, 504, -42, 1, -7, 0, 196, -6272, 13230, -6272, 980, -56, 1, -8, 0, -288, 21504, -81648, 64512, -16800, 1728, -72, 1, -9, 0, 405

Offset: 0

Christian G. Bower, Apr 25 2000

			1;
0,1;
-1,-2,1;
-2,0,-6,1;
-3,0,18,-12,1;
...

Cf. A055136.

rows = 12; row[n_] := Join[CoefficientList[(x+n-1)^n + O[x]^(n+1), x], Table[0, {rows-n-1}]]; M = Inverse[Table[row[n], {n, 0, rows-1}]]; Table[ M[[n+1, k+1]], {n, 0, rows-1}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 14 2017 *)

A190295 A055134(n,k)*k.

Original entry on oeis.org

1, 2, 2, 12, 12, 3, 108, 108, 36, 4, 1280, 1280, 480, 80, 5, 18750, 18750, 7500, 1500, 150, 6, 326592, 326592, 136080, 30240, 3780, 252, 7, 6588344, 6588344, 2823576, 672280, 96040, 8232, 392, 8

Offset: 1

Geoffrey Critzer, May 07 2011

Triangular array read by rows.  T(n,k) is the total number of fixed points in the endofunctions on {1,2,...,n} that have exactly k fixed points.
Row sums = A000312 = n^n so we see the expected number of fixed points is 1.
T(n,k) is also the number of endofunctions f:{1,2,...,n}->{1,2,...,n} in which there are exactly k elements j in {1,2,...,n-1} such that f(j)= f(j+1). - Geoffrey Critzer, Jun 25 2013

			Triangle begins
1
2     2
12    12    3
108   108   36    4
1280  1280  480   80    5
18750 18750 7500  1500  150   6

Flatten[CoefficientList[Table[Series[n((n-1)+x)^(n-1),{x,0,20}],{n,1,8}],x]]

O.g.f. for row n: n*((n-1)+x)^(n-1)

A137370 Triangle: signed version of A055134.

Original entry on oeis.org

1, 0, 1, 1, -2, 1, -8, 12, -6, 1, 81, -108, 54, -12, 1, -1024, 1280, -640, 160, -20, 1, 15625, -18750, 9375, -2500, 375, -30, 1, -279936, 326592, -163296, 45360, -7560, 756, -42, 1, 5764801, -6588344, 3294172, -941192, 168070, -19208, 1372, -56, 1, -134217728, 150994944, -75497472, 22020096, -4128768

Offset: 1

Roger L. Bagula, Apr 09 2008

			{1},
{0, 1},
{1, -2, 1},
{-8, 12, -6, 1},
{81, -108, 54, -12, 1},
{-1024, 1280, -640, 160, -20, 1},
{15625, -18750, 9375, -2500, 375, -30, 1},
{-279936, 326592, -163296, 45360, -7560, 756, -42, 1},...

B[0] = {{x, y}, {t*y, x}}; B[n_] := B[n] = B[n - 1].B[0];
Table[Det[B[n]] /. x -> Sqrt[z] /. y -> 1 /. t -> n, {n, 0, 10}];
a = Join[{{1}}, Table[CoefficientList[Det[B[n]] /. x -> Sqrt[z] /. y ->1 /. t -> n, z], {n, 0, 10}]];
Flatten[a]

Edited by Joerg Arndt, Feb 12 2024

A065440 a(n) = (n-1)^n.

Original entry on oeis.org

1, 0, 1, 8, 81, 1024, 15625, 279936, 5764801, 134217728, 3486784401, 100000000000, 3138428376721, 106993205379072, 3937376385699289, 155568095557812224, 6568408355712890625, 295147905179352825856, 14063084452067724991009, 708235345355337676357632

Offset: 0

Len Smiley, Nov 17 2001

a(n) is the number of functions from {1,2,...,n} into {1,2,...,n} that have no fixed points.

The probability that a random function from {1,2,...,n} into {1,2,...,n} has no fixed point is equal to a(n)/n^n; it tends to 1/e when n tends to infinity. - Robert FERREOL, Mar 29 2017

Harry J. Smith, Table of n, a(n) for n = 0..100
Mustafa Obaid et al., The number of complete exceptional sequences for a Dynkin algebra, arXiv preprint arXiv:1307.7573 [math.RT], 2013.

Essentially the same as A007778 - note T(x) = -W(-x).
Column k=0 of A055134.
Row sums of A350452.
Cf. A158497, A284458.

A065440:= func< n | (n-1)^n >;
[A065440(n): n in [0..30]]; // G. C. Greubel, Mar 23 2025

Table[(n-1)^n,{n,0,20}] (* Harvey P. Dale, Jan 03 2015 *)

a(n) = { (n - 1)^n } \\ Harry J. Smith, Oct 19 2009

def A065440(n): return (n-1)**n
print([A065440(n) for n in range(31)]) # G. C. Greubel, Mar 23 2025

a(n) = A007778(n-1).
E.g.f.: x/(T(x)*(1-T(x))) (where T(x) is Euler's tree function, the E.g.f. for n^(n-1)) (see A000169).
a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)*n^(n-k). - Robert FERREOL, Mar 28 2017
a(n) = Sum_{k=0..n} (-1)^k*binomial(n+2,k+2)*(k+1)*(2*k+n+3)^n. - Vladimir Kruchinin, Aug 13 2025

A349454 Number T(n,k) of endofunctions on [n] with exactly k fixed points, all of which are isolated; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 8, 3, 0, 1, 81, 32, 6, 0, 1, 1024, 405, 80, 10, 0, 1, 15625, 6144, 1215, 160, 15, 0, 1, 279936, 109375, 21504, 2835, 280, 21, 0, 1, 5764801, 2239488, 437500, 57344, 5670, 448, 28, 0, 1, 134217728, 51883209, 10077696, 1312500, 129024, 10206, 672, 36, 0, 1

Offset: 0

Alois P. Heinz, Dec 30 2021

			Triangle T(n,k) begins:
        1;
        0,       1;
        1,       0,      1;
        8,       3,      0,     1;
       81,      32,      6,     0,    1;
     1024,     405,     80,    10,    0,   1;
    15625,    6144,   1215,   160,   15,   0,  1;
   279936,  109375,  21504,  2835,  280,  21,  0, 1;
  5764801, 2239488, 437500, 57344, 5670, 448, 28, 0, 1;
  ...

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

Column k=0 gives A065440.
Row sums give A204042.
Main diagonal and first lower diagonal give A000012, A000004.
T(n+1,n-1) gives A000217.
T(n+3,n) gives A130809.
T(n+3,n-1) gives A102741 for n>=1.
Cf. A055134, A217701, A350212, A350454.

T:= (n, k)-> binomial(n, k)*(n-k-1)^(n-k):
seq(seq(T(n, k), k=0..n), n=0..10);

T(n,k) = binomial(n,k) * (n-k-1)^(n-k).
From Mélika Tebni, Apr 02 2023: (Start)
E.g.f. of column k: -x / (LambertW(-x)*(1+LambertW(-x)))*x^k / k!.
Sum_{k=0..n} k^k*T(n,k) = A217701(n). (End)

A350212 Number T(n,k) of endofunctions on [n] with exactly k isolated fixed points; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 3, 0, 1, 17, 9, 0, 1, 169, 68, 18, 0, 1, 2079, 845, 170, 30, 0, 1, 31261, 12474, 2535, 340, 45, 0, 1, 554483, 218827, 43659, 5915, 595, 63, 0, 1, 11336753, 4435864, 875308, 116424, 11830, 952, 84, 0, 1, 262517615, 102030777, 19961388, 2625924, 261954, 21294, 1428, 108, 0, 1

Offset: 0

Alois P. Heinz, Dec 19 2021

			T(3,1) = 9: 122, 133, 132, 121, 323, 321, 113, 223, 213.
Triangle T(n,k) begins:
         1;
         0,       1;
         3,       0,      1;
        17,       9,      0,      1;
       169,      68,     18,      0,     1;
      2079,     845,    170,     30,     0,   1;
     31261,   12474,   2535,    340,    45,   0,  1;
    554483,  218827,  43659,   5915,   595,  63,  0, 1;
  11336753, 4435864, 875308, 116424, 11830, 952, 84, 0, 1;
  ...

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

Columns k=0-1 give: |A069856|, A348590.
Row sums give A000312.
T(n+1,n-1) gives A045943.
Cf. A001865, A008290, A008291, A055134, A055897, A060281, A086659, A124323, A350134, A349454.

g:= proc(n) option remember; add(n^(n-j)*(n-1)!/(n-j)!, j=1..n) end:
b:= proc(n, m) option remember; `if`(n=0, x^m, add(g(i)*
      b(n-i, m+`if`(i=1, 1, 0))*binomial(n-1, i-1), i=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..10);
# second Maple program:
A350212 := (n,k)-> add((-1)^(j-k)*binomial(j,k)*binomial(n,j)*(n-j)^(n-j), j=0..n):
seq(print(seq(A350212(n, k), k=0..n)), n=0..9); # Mélika Tebni, Nov 24 2022

g[n_] := g[n] = Sum[n^(n - j)*(n - 1)!/(n - j)!, {j, 1, n}];
b[n_, m_] := b[n, m] = If[n == 0, x^m, Sum[g[i]*
     b[n - i, m + If[i == 1, 1, 0]]*Binomial[n - 1, i - 1], {i, 1, n}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Mar 11 2022, after Alois P. Heinz *)

Sum_{k=0..n} k * T(n,k) = A055897(n).
Sum_{k=1..n} T(n,k) = A350134(n).
From Mélika Tebni, Nov 24 2022: (Start)
T(n,k) = binomial(n, k)*|A069856(n-k)|.
E.g.f. column k: exp(-x)*x^k / ((1 + LambertW(-x))*k!).
T(n,k) = Sum_{j=0..n} (-1)^(j-k)*binomial(j, k)*binomial(n, j)*(n-j)^(n-j). (End)

A350446 Number T(n,k) of endofunctions on [n] with exactly k cycles of length larger than 1; triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

Original entry on oeis.org

1, 1, 3, 1, 16, 11, 125, 128, 3, 1296, 1734, 95, 16807, 27409, 2425, 15, 262144, 499400, 61054, 945, 4782969, 10346328, 1605534, 42280, 105, 100000000, 240722160, 44981292, 1706012, 11025, 2357947691, 6222652233, 1351343346, 67291910, 763875, 945

Offset: 0

Alois P. Heinz, Dec 31 2021

			Triangle T(n,k) begins:
           1;
           1;
           3,          1;
          16,         11;
         125,        128,          3;
        1296,       1734,         95;
       16807,      27409,       2425,       15;
      262144,     499400,      61054,      945;
     4782969,   10346328,    1605534,    42280,    105;
   100000000,  240722160,   44981292,  1706012,  11025;
  2357947691, 6222652233, 1351343346, 67291910, 763875, 945;
  ...

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

Column k=0 gives A000272(n+1).
Row sums give A000312.
T(2n,n) gives A001147.
Cf. A055134, A060281, A349454, A350452.
Cf. A136394, A190314, A217701.

c:= proc(n) option remember; add(n!*n^(n-k-1)/(n-k)!, k=2..n) end:
t:= proc(n) option remember; n^(n-1) end:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
      b(n-i)*binomial(n-1, i-1)*(c(i)*x+t(i)), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n/2))(b(n)):
seq(T(n), n=0..12);
# second Maple program:
egf := k-> (LambertW(-x)-log(1+LambertW(-x)))^k/(exp(LambertW(-x))*k!):
A350446 := (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):
seq(print(seq(A350446(n, k), k=0..n/2)), n=0..10); # Mélika Tebni, Mar 23 2023

c[n_] := c[n] = Sum[n!*n^(n - k - 1)/(n - k)!, {k, 2, n}];
t[n_] := t[n] = n^(n - 1);
b[n_] := b[n] = Expand[If[n == 0, 1, Sum[
     b[n - i]*Binomial[n - 1, i - 1]*(c[i]*x + t[i]), {i, 1, n}]]];
T[n_] :=  With[{p = b[n]}, Table[Coefficient[p, x, i], {i, 0, n/2}]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, May 06 2022, after Alois P. Heinz *)

From Mélika Tebni, Mar 23 2023: (Start)
E.g.f. of column k: (W(-x)-log(1 + W(-x)))^k / (exp(W(-x))*k!), W(x) the Lambert W-function.
T(n,k) = Sum_{j=k..n} n^(n-j)*binomial(n-1,j-1)*A136394(j,k), for n > 0.
T(n,k) = Sum_{j=k..n} (n-j+1)^(n-j-1)*binomial(n,j)*A350452(j,k).
Sum_{k=0..n/2} (k+1)*T(n,k) = A190314(n), for n > 0.
Sum_{k=0..n/2} 2^k*T(n,k) = A217701(n). (End)

A185070 Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k 3-cycles. n>=0, 0<=k<=floor(n/3).

Original entry on oeis.org

1, 1, 4, 25, 2, 224, 32, 2625, 500, 38056, 8560, 40, 657433, 164150, 1960, 13178880, 3526656, 71680, 300585601, 84389928, 2442720, 2240, 7683776000, 2232672000, 83328000, 224000, 217534555161, 64830707370, 2931500880, 14907200

Offset: 0

Geoffrey Critzer, Dec 25 2012

The total number of 3-cycles over all functions on {1,2,...,n} is 2*binomial(n,3)*n^(n-3). So we see that as n gets large the probability that a random function would contain k 3-cycles is a Poisson distribution with mean = 1/3. Generally, the total number of j-cycles over all functions on {1,2,...,n} is (j-1)!*binomial(n,j)*n^(n-j).

			          1;
          1;
          4;
         25,        2;
        224,       32;
       2625,      500;
      38056,     8560,      40;
     657433,   164150,    1960;
   13178880,  3526656,   71680;
  300585601, 84389928, 2442720, 2240;
  ...

Cf. A185025, A055134, A190314.

nn=10;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[Exp[t^3/3(y-1)]/(1-t),{x,0,nn}],{x,y}]//Grid

E.g.f.: exp(T(x)^3/3*(y - 1))/(1-T(x)) where T(x) is the e.g.f. for A000169.

cp's OEIS Frontend

A055135 Matrix inverse of triangle A055134.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A190295 A055134(n,k)*k.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula

A137370 Triangle: signed version of A055134.

Views

Author

Keywords

Examples

Programs

Mathematica

Extensions

A065440 a(n) = (n-1)^n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A349454 Number T(n,k) of endofunctions on [n] with exactly k fixed points, all of which are isolated; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A350212 Number T(n,k) of endofunctions on [n] with exactly k isolated fixed points; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A350446 Number T(n,k) of endofunctions on [n] with exactly k cycles of length larger than 1; triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A185070 Triangular array read by rows. T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k 3-cycles. n>=0, 0<=k<=floor(n/3).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica