A055897 -id:A055897 - cp's OEIS frontend

A055541 Total number of leaves (nodes of vertex degree 1) in all labeled trees with n nodes.

0, 2, 6, 36, 320, 3750, 54432, 941192, 18874368, 430467210, 11000000000, 311249095212, 9659108818944, 326173191714734, 11905721598812160, 467086816406250000, 19599665578316398592, 875901453762003632658, 41532319635035234107392, 2082547005958224830656820

Offset: 1

Eric W. Weisstein

nonn

Equivalently, a(n) is the number of rooted labeled trees such that the root node has degree 1. - Geoffrey Critzer, Feb 07 2012

G. C. Greubel, Table of n, a(n) for n = 1..385
Dixy Msapato, Counting the number of tau-exceptional sequences over Nakayama algebras, arXiv:2002.12194 [math.RT], 2020.
Eric Weisstein's World of Mathematics, Tree Leaf.
Index entries for sequences related to trees

Cf. A003227, A003228, A055314, A055540, A055897.

Essentially the same as A061302.

[0,2] cat [n*(n-1)^(n-2): n in [3..10]]; // G. C. Greubel, Nov 11 2017

Join[{0,2}, Table[Sum[n!/k! StirlingS2[n-2,n-k] k, {k,2,n-1}], {n,3,20}]] (* Geoffrey Critzer, Nov 22 2011 *)
Join[{0,2}, Table[n*(n-1)^(n-2), {n,3,50}]] (* or *) Rest[With[{nmax = 40}, CoefficientList[Series[-x*LambertW[-x], {x, 0, nmax}], x]*Range[0, nmax]!]] (* G. C. Greubel, Nov 11 2017 *)

for(n=1, 30, print1(if(n==1, 0, if(n==2, 2, n*(n-1)^(n-2))), ", ")) \\ G. C. Greubel, Nov 11 2017

From Vladeta Jovovic, Mar 31 2001: (Start)
a(n) = n*(n-1)^(n-2), n > 1.
E.g.f.: -x*LambertW(-x). (End)
a(n) = Sum_{k=1..n} (A055314(n, k)*k). - Christian G. Bower, Jun 12 2000
E.g.f.: x*T(x) where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Feb 07 2012

More terms from Christian G. Bower, Jun 12 2000

A055134 Triangle read by rows: T(n,k) = number of labeled endofunctions on n points with k fixed points.

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

Offset: 0

Christian G. Bower, Apr 25 2000

The same triangle (except for signs) may be obtained from the determinants of the Brahmagupta matrices, setting x->Sqrt[z], y->1, t->n. - Roger L. Bagula, Apr 09 2008
From Bob Selcoe, Nov 15 2014 (Start):
T(n,k)/A000312(n) is the probability P(n,k) that any member (j) of set J={1..n} will be selected k times given n random draws from J. This is equivalent to rolling an n-sided die (with standard assumptions) with sides numbered j=1..n: P(n,k) is the probability that any j will show k times with n rolls.
P(n,k) = (n-2)!*(n-1)^(n-k+1 )/k!*(n-k)!*n^(n-1); n>1. As n approaches infinity, P(n,0) and P(n,1) approach 1/e. (End)
Row sums give n^n (see A000312). - Bob Selcoe, Sep 08 2015

			Triangle T(n,k) begins:
       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;
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Eric W. Weisstein's World of Mathematics, Brahmagupta Matrix.

Columns k=0-2 give: A065440, A055897, A081132(n-2) for n>=2.
Row sums give A000312.
Cf. A055135, A055136.

Clear[B] 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] (* Roger L. Bagula, Apr 09 2008 *)
row[n_] := CoefficientList[(x + n - 1)^n + O[x]^(n+1), x];
Table[row[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 13 2017, after Geoffrey Critzer *)
Join[{1, 0, 1}, Table[Binomial[n, k]*(n - 1)^(n - k), {n, 2, 49}, {k, 0, n}]] // Flatten (* G. C. Greubel, Nov 14 2017 *)

for(n=0,15, for(k=0,n, print1(if(n==0 && k==0, 1, if(n==1 && k==0, 0, if(n==1 && k==1, 1, binomial(n,k)*(n-1)^(n-k)))), ", "))) \\ G. C. Greubel, Nov 14 2017

T(n, k) = C(n, k)*(n-1)^(n-k), for n>1.
E.g.f.: (-LambertW(-y)/y)^(x-1)/(1+LambertW(-y)). - Vladeta Jovovic
O.g.f. for row n: (x + n - 1)^n. - Geoffrey Critzer, Mar 21 2010

A265583 Array T(n,k) = k*(k-1)^(n-1) read by ascending antidiagonals; k,n >= 1.

Original entry on oeis.org

1, 0, 2, 0, 2, 3, 0, 2, 6, 4, 0, 2, 12, 12, 5, 0, 2, 24, 36, 20, 6, 0, 2, 48, 108, 80, 30, 7, 0, 2, 96, 324, 320, 150, 42, 8, 0, 2, 192, 972, 1280, 750, 252, 56, 9, 0, 2, 384, 2916, 5120, 3750, 1512, 392, 72, 10, 0, 2, 768, 8748, 20480, 18750, 9072, 2744, 576, 90, 11

Offset: 1

R. J. Mathar, Dec 10 2015

T(n,k) is the number of n-letter words in a k-letter alphabet with no adjacent letters the same. The factor k represents the number of choices of the first letter, and the n-1 times repeated factor k-1 represents the choices of the next n-1 letters avoiding their predecessor.

The antidiagonal sums are s(d) = 1, 2, 5, 12, 31, 88, 275, 942, 3513, 14158, 61241, 282632, .. for d = n+k >= 2.

			      1       2       3       4       5       6       7
      0       2       6      12      20      30      42
      0       2      12      36      80     150     252
      0       2      24     108     320     750    1512
      0       2      48     324    1280    3750    9072
      0       2      96     972    5120   18750   54432
      0       2     192    2916   20480   93750  326592
T(3,3)=12 counts aba, abc, aca, acb, bab, bac, bca, bcb, cab, cac, cba, cbc. Words like aab or cbb are not counted.

Robert Israel, Table of n, a(n) for n = 1..10011(first 141 antidiagonals, flattened)

Cf. A007283 (column 3), A003946 (column 4), A003947 (column 5), A002378 (row 2), A011379 (row 3), A179824 (row 4), A055897 (diagonal), A265584.

T:= function(n,k)
    if (n=1 and k=1) then return 1;
    else return k*(k-1)^(n-k-1);
    fi;
  end;
Flat(List([2..15], n-> List([1..n-1], k-> T(n,k) ))); # G. C. Greubel, Aug 10 2019

T:= func< n,k | (n eq 1 and k eq 1) select 1 else k*(k-1)^(n-k-1) >;
[T(n,k): k in [1..n-1], n in [2..15]]; // G. C. Greubel, Aug 10 2019

A265583 := proc(n,k)
    k*(k-1)^(n-1) ;
end proc:
seq(seq( A265583(d-k,k),k=1..d-1),d=2..13) ;

T[1,1] = 1; T[n_, k_] := If[k==1, 0, k*(k-1)^(n-1)]; Table[T[n-k,k], {n,2,12}, {k,1,n-1}] // Flatten (* Amiram Eldar, Dec 13 2018 *)

T(n,k) = if(n==k==1, 1, k*(k-1)^(n-k-1) );
for(n=2,15, for(k=1,n-1, print1(T(n,k), ", "))) \\ G. C. Greubel, Aug 10 2019

def T(n, k):
    if (n==k==1): return 1
    else: return k*(k-1)^(n-k-1)
[[T(n, k) for k in (1..n-1)] for n in (2..15)] # G. C. Greubel, Aug 10 2019

T(n,k) = k*A051129(n-1,k-1) = k*A003992(k-1,n-1).
G.f. for column k: k*x/(1-(k-1)*x). - R. J. Mathar, Dec 12 2015
G.f. for array: y/(y-1) - (1+1/x)*y*LerchPhi(y,1,-1/x). - Robert Israel, Dec 13 2018

A240993 A000142 (n+1) * A002109(n), a product of factorials and hyperfactorials.

Original entry on oeis.org

1, 2, 24, 2592, 3317760, 62208000000, 20316635136000000, 133852981198454784000000, 20211123400293732996612096000000, 78302033109811407811828935756349440000000, 8613223642079254859301182933198438400000000000000000

Offset: 0

Reinhard Zumkeller, Aug 31 2014

nonn

a(n+1) / a(n) = A055897(n+2);

row products of the triangle A245334.

Reinhard Zumkeller, Table of n, a(n) for n = 0..36

Cf. A000142, A002109, A245334, A055897, A245334, A111063, A074962.

Haskell
```
a240993 n = a000142 (n + 1) * a002109 n
```

Table[(n+1)!*Hyperfactorial[n], {n, 0, 10}] (* Vaclav Kotesovec, Nov 14 2014 *)
Table[(n+1)*(n!)^(n+1)/BarnesG[n+1], {n, 0, 10}] (* Vaclav Kotesovec, Nov 14 2014 *)

a(n) ~ A * sqrt(2*Pi) * n^(n^2/2+3*n/2+19/12) / exp(n*(n+4)/4), where A = 1.2824271291... is the Glaisher-Kinkelin constant (see A074962). - Vaclav Kotesovec, Nov 14 2014

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)

A118537 Number of functions f: {1, 2, ..., n} --> {1, 2, ..., n} such that f(1) != f(2), f(2) != f(3), ..., f(n-1) != f(n), f(n) != f(1).

Original entry on oeis.org

2, 6, 84, 1020, 15630, 279930, 5764808, 134217720, 3486784410, 99999999990, 3138428376732, 106993205379060, 3937376385699302, 155568095557812210, 6568408355712890640, 295147905179352825840, 14063084452067724991026

Offset: 2

Warut Roonguthai, May 06 2006

nonn

a(n) is also the number of circuits of length n in the complete graph on n vertices. - Thibaut Lienart (syncthib(AT)gmail.com), Jan 29 2010
Circuits are allowed to be self-intersecting and are directional with a designated start node. The number of (self-avoiding) directed cycles is given by A124355. - Andrew Howroyd, Sep 05 2018
a(n) is also the number of graph colorings of the cycle graph C_n with n colors. - Orson R. L. Peters, Jul 27 2020

Andrew Howroyd, Table of n, a(n) for n = 2..100

Cf. A055897, A124355.

[(n-1)^n + (-1)^n*(n-1) : n in [2..20]]; // Wesley Ivan Hurt, Jul 27 2020

a[n_]:=(n-1)^n + (-1)^n*(n-1); Array[a, 50, {2, 51}] (* Stefano Spezia, Sep 07 2018 *)

a(n) = (n-1)^n + (-1)^n*(n-1); \\ Andrew Howroyd, Sep 05 2018

a(n) = (n-1)^n + (-1)^n*(n-1).

A176043 a(n) = (2n-1)(n-1)^(n-1).

Original entry on oeis.org

1, 1, 3, 20, 189, 2304, 34375, 606528, 12353145, 285212672, 7360989291, 210000000000, 6562168424053, 222902511206400, 8177627877990831, 322248197941182464, 13574710601806640625, 608742554432415203328, 28953409166021786746195, 1455817098785971890290688, 77158366570752229975835181

Offset: 0

Michel Lagneau, Apr 07 2010

Determinant of the symmetric n X n matrix M_n where M_n(j,k) = n for j = k, M_n(j,k) = 1 otherwise.
The eigenvalues are 2*n-1, and n-1 with multiplicity n-1. The determinant of M_n is (2n-1)*(n-1)^(n-1), where 0^0 = 1.
Number of functions from [n] to [n] with zero or one fixed point. - Olivier Gérard, Jul 31 2016

			a(5) = determinant(M_5) = 2304 where M_5 is the matrix
  [5 1 1 1 1]
  [1 5 1 1 1]
  [1 1 5 1 1]
  [1 1 1 5 1]
  [1 1 1 1 5]
The 20 functions from [3] to [3] with one or zero fixed point are:
  0fp : 211,212,231,232,311,312,331,332
  1fp : 111,112,131,132,   221,222,321,322,   213,233,313,333

Vincenzo Librandi, Table of n, a(n) for n = 0..100, (corrected by _Peter Luschny_, Jan 19 2019)

Cf. A174964.
Cf. A007778 (functions from [n] to [n] without fixed point).
Cf. A055897 (functions from [n] to [n] with one fixed point).
Cf. A212291 (bijections of [n] with zero or one fixed point).
Cf. A000166 (bijections of [n] without fixed point).
Cf. A000240 (bijections of [n] with one fixed point).

[ (2*n-1)*(n-1)^(n-1): n in [1..17] ]; // Klaus Brockhaus, Apr 19 2010

[ Determinant( SymmetricMatrix( &cat[ [ j eq k select n else 1: k in [1..j] ]: j in [1..n] ] ) ): n in [1..17] ]; // Klaus Brockhaus, Apr 19 2010

for n from 2 to 30 do:x:=(2*n-1)*(n-1)^(n-1):print(x) :od:

Join[{1},Table[(2n-1)(n-1)^(n-1),{n,2,20}]] (* Harvey P. Dale, Jan 16 2014 *)

a(n)=n--; (2*n+1)*n^n \\ Charles R Greathouse IV, Jul 31 2016

a(n) = (2*n-1)*(n-1)^(n-1).
A176043(n) = A007778(n-1) + A055897(n).
a(n+1) = n! * [x^n] exp(n*x)*(1 + 2*n*x) for n >= 0. - Stefano Spezia, May 07 2023

Edited by Klaus Brockhaus, Apr 19 2010

New interpretation and cross-references by Olivier Gérard, Jul 31 2016

A185390 Triangular array read by rows. T(n,k) is the number of partial functions on n labeled objects in which the domain of definition contains exactly k elements such that for all i in {1,2,3,...}, (f^i)(x) is defined.

Original entry on oeis.org

1, 1, 1, 3, 2, 4, 16, 9, 12, 27, 125, 64, 72, 108, 256, 1296, 625, 640, 810, 1280, 3125, 16807, 7776, 7500, 8640, 11520, 18750, 46656, 262144, 117649, 108864, 118125, 143360, 196875, 326592, 823543, 4782969, 2097152, 1882384, 1959552, 2240000, 2800000, 3919104, 6588344, 16777216

Offset: 0

Geoffrey Critzer, Feb 09 2012

Here, for any x in the domain of definition (f^i)(x) denotes the i-fold composition of f with itself, e.g., (f^2)(x) = f(f(x)). The domain of definition is the set of all values x for which f(x) is defined.
T(n,n) = n^n, the partial functions that are total functions.
T(n,0) = A000272(offset), see comment and link by Dennis P. Walsh.

			Triangle begins:
      1;
      1,     1;
      3,     2,     4;
     16,     9,    12,    27;
    125,    64,    72,   108,   256;
   1296,   625,   640,   810,  1280,  3125;
  16807,  7776,  7500,  8640, 11520, 18750, 46656;
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Geoffrey Critzer, Distribution of non-functional points under a random partial function
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 132, II.21.

Row sums give A000169(n+1).
T(n,n-1) gives A055897(n).
T(n,n)-T(n,n-1) gives A060226(n).
Cf. A000272, A000312, A185391.

T(n, k) = binomial(n, k)*k^k*(n-k+1)^(n-k-1)
for n in 0:9 (println([T(n, k) for k in 0:n])) end
# Peter Luschny, Jan 12 2024

T:= (n, k)-> binomial(n,k)*k^k*(n-k+1)^(n-k-1):
seq(seq(T(n,k), k=0..n), n=0..10);  # Alois P. Heinz, Jan 12 2024

nn = 7; tx = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; txy = Sum[n^(n - 1) (x y)^n/n!, {n, 1, nn}]; f[list_] := Select[list, # > 0 &]; Map[f, Range[0, nn]! CoefficientList[Series[Exp[tx]/(1 - txy), {x, 0, nn}], {x, y}]] // Flatten

E.g.f.: exp(T(x))/(1-T(x*y)) where T(x) is the e.g.f. for A000169.
T(n,k) = binomial(n,k)*k^k*(n-k+1)^(n-k-1). - Geoffrey Critzer, Feb 28 2022
Sum_{k=0..n} k * T(n,k) = A185391(n). - Alois P. Heinz, Jan 12 2024

A228154 T(n,k) is the number of s in {1,...,n}^n having longest contiguous subsequence with the same value of length k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 2, 2, 12, 12, 3, 108, 120, 24, 4, 1280, 1520, 280, 40, 5, 18750, 23400, 3930, 510, 60, 6, 326592, 423360, 65016, 7644, 840, 84, 7, 6588344, 8800008, 1241464, 132552, 13440, 1288, 112, 8, 150994944, 206622720, 26911296, 2622528, 244944, 22032, 1872, 144, 9

Offset: 1

Walt Rorie-Baety, Aug 15 2013

			T(1,1) =  1: [1].
T(2,1) =  2: [1,2], [2,1].
T(2,2) =  2: [1,1], [2,2].
T(3,1) = 12: [1,2,1], [1,2,3], [1,3,1], [1,3,2], [2,1,2], [2,1,3], [2,3,1], [2,3,2], [3,1,2], [3,1,3], [3,2,1], [3,2,3].
T(3,2) = 12: [1,1,2], [1,1,3], [1,2,2], [1,3,3], [2,1,1], [2,2,1], [2,2,3], [2,3,3], [3,1,1], [3,2,2], [3,3,1], [3,3,2].
T(3,3) =  3: [1,1,1], [2,2,2], [3,3,3].
Triangle T(n,k) begins:
.       1;
.       2,       2;
.      12,      12,       3;
.     108,     120,      24,      4;
.    1280,    1520,     280,     40,     5;
.   18750,   23400,    3930,    510,    60,    6;
.  326592,  423360,   65016,   7644,   840,   84,   7;
. 6588344, 8800008, 1241464, 132552, 13440, 1288, 112,  8;

Alois P. Heinz, Rows n = 1..141, flattened
Project Euler, Problem 427: n-sequences

Row sums give: A000312.
Column k=1 gives: A055897.
Main diagonal gives: A000027.
Lower diagonal gives: 2*A180291.
Cf. A228194, A228273, A228617.

T:= proc(n) option remember; local b; b:=
      proc(m, s, i) option remember; `if`(m>i or s>m, 0,
        `if`(i=1, n, `if`(s=1, (n-1)*add(b(m, h, i-1), h=1..m),
         b(m, s-1, i-1) +`if`(s=m, b(m-1, s-1, i-1), 0))))
      end; forget(b);
      seq(add(b(k, s, n), s=1..k), k=1..n)
    end:
seq(T(n), n=1..12);  # Alois P. Heinz, Aug 18 2013

T[n_] := T[n] = Module[{b}, b[m_, s_, i_] := b[m, s, i] = If[m>i || s>m, 0, If[i == 1, n, If[s == 1, (n-1)*Sum[b[m, h, i-1], {h, 1, m}], b[m, s-1, i-1] + If[s == m, b[m-1, s-1, i-1], 0]]]]; Table[Sum[b[k, s, n], {s, 1, k}], {k, 1, n}]]; Table[ T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Mar 06 2015, after Alois P. Heinz *)

Sum_{k=1..n} k * T(n,k) = A228194(n). - Alois P. Heinz, Dec 23 2020

A158497 Triangle T(n,k) formed by the coordination sequences and the number of leaves for trees.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 12, 1, 4, 12, 36, 108, 1, 5, 20, 80, 320, 1280, 1, 6, 30, 150, 750, 3750, 18750, 1, 7, 42, 252, 1512, 9072, 54432, 326592, 1, 8, 56, 392, 2744, 19208, 134456, 941192, 6588344, 1, 9, 72, 576, 4608, 36864, 294912, 2359296, 18874368, 150994944, 1, 10, 90, 810, 7290, 65610, 590490, 5314410, 47829690, 430467210, 3874204890

Offset: 0

Thomas Wieder, Mar 20 2009

Consider the k-fold Cartesian products CP(n,k) of the vector A(n) = [1, 2, 3, ..., n].
An element of CP(n,k) is a n-tuple T_t of the form T_t = [i_1, i_2, i_3, ..., i_k] with t=1, .., n^k.
We count members T of CP(n,k) which satisfy some condition delta(T_t), so delta(.) is an indicator function which attains values of 1 or 0 depending on whether T_t is to be counted or not; the summation sum_{CP(n,k)} delta(T_t) over all elements T_t of CP produces the count.
For the triangle here we have delta(T_t) = 0 if for any two i_j, i_(j+1) in T_t one has i_j = i_(j+1): T(n,k) = Sum_{CP(n,k)} delta(T_t) = Sum_{CP(n,k)} delta(i_j = i_(j+1)).
The test on i_j > i_(j+1) generates A158498. One gets the Pascal triangle A007318 if the indicator function tests whether for any two i_j, i_(j+1) in T_t one has i_j >= i_(j+1).
Use of other indicator functions can also calculate the Bell numbers A000110, A000045 or A000108.

			Array, A(n, k) = n*(n-1)^(k-1) for n > 1, A(n, k) = 1 otherwise, begins as:
  1,  1,   1,    1,     1,      1,       1,        1,        1, ... A000012;
  1,  1,   1,    1,     1,      1,       1,        1,        1, ... A000012;
  1,  2,   2,    2,     2,      2,       2,        2,        2, ... A040000;
  1,  3,   6,   12,    24,     48,      96,      192,      384, ... A003945;
  1,  4,  12,   36,   108,    324,     972,     2916,     8748, ... A003946;
  1,  5,  20,   80,   320,   1280,    5120,    20480,    81920, ... A003947;
  1,  6,  30,  150,   750,   3750,   18750,    93750,   468750, ... A003948;
  1,  7,  42,  252,  1512,   9072,   54432,   326592,  1959552, ... A003949;
  1,  8,  56,  392,  2744,  19208,  134456,   941192,  6588344, ... A003950;
  1,  9,  72,  576,  4608,  36864,  294912,  2359296, 18874368, ... A003951;
  1, 10,  90,  810,  7290,  65610,  590490,  5314410, 47829690, ... A003952;
  1, 11, 110, 1100, 11000, 110000, 1100000, 11000000, ............. A003953;
  1, 12, 132, 1452, 15972, 175692, 1932612, 21258732, ............. A003954;
  1, 13, 156, 1872, 22464, 269568, 3234816, 38817792, ............. A170732;
  ... ;
The triangle begins as:
  1
  1, 1;
  1, 2,  2;
  1, 3,  6,  12;
  1, 4, 12,  36,  108;
  1, 5, 20,  80,  320,  1280;
  1, 6, 30, 150,  750,  3750,  18750;
  1, 7, 42, 252, 1512,  9072,  54432, 326592;
  1, 8, 56, 392, 2744, 19208, 134456, 941192, 6588344;
  ...;
T(3,3) = 12 counts the triples (1,2,1), (1,2,3), (1,3,1), (1,3,2), (2,1,2), (2,1,3), (2,3,1), (2,3,2), (3,1,2), (3,1,3), (3,2,1), (3,2,3) out of a total of 3^3 = 27 triples in the CP(3,3).

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Array rows n: A170733 (n=14), ..., A170769 (n=50).
Columns k: A000012(n) (k=0), A000027(n) (k=1), A002378(n-1) (k=2), A011379(n-1) (k=3), A179824(n) (k=4), A101362(n-1) (k=5), 2*A168351(n-1) (k=6), 2*A168526(n-1) (k=7), 2*A168635(n-1) (k=8), 2*A168675(n-1) (k=9), 2*A170783(n-1) (k=10), 2*A170793(n-1) (k=11).
Diagonals k: A055897 (k=n), A055541 (k=n-1), A373395 (k=n-2), A379612 (k=n-3).
Sums: (-1)^n*A065440(n) (signed row).
Cf. A000045, A000108, A000110, A007318, A079901, A158498.

A158497:= func< n,k | k le 1 select n^k else n*(n-1)^(k-1) >;
[A158497(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Mar 18 2025

A158497[n_, k_]:= If[n<2 || k==0, 1, n*(n-1)^(k-1)];
Table[A158497[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Mar 18 2025 *)

def A158497(n,k): return n^k if k<2 else n*(n-1)^(k-1)
print(flatten([[A158497(n,k) for k in range(n+1)] for n in range(13)])) # G. C. Greubel, Mar 18 2025

T(n, k) = (n-1)^(k-1) + (n-1)^k = n*A079901(n-1,k-1), k > 0.

Sum_{k=0..n} T(n,k) = (n*(n-1)^n - 2)/(n-2), n > 2.

Edited by R. J. Mathar, Mar 31 2009

More terms added by G. C. Greubel, Mar 18 2025

cp's OEIS Frontend

A055541 Total number of leaves (nodes of vertex degree 1) in all labeled trees with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A055134 Triangle read by rows: T(n,k) = number of labeled endofunctions on n points with k fixed points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A265583 Array T(n,k) = k*(k-1)^(n-1) read by ascending antidiagonals; k,n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A240993 A000142 (n+1) * A002109(n), a product of factorials and hyperfactorials.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

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

A118537 Number of functions f: {1, 2, ..., n} --> {1, 2, ..., n} such that f(1) != f(2), f(2) != f(3), ..., f(n-1) != f(n), f(n) != f(1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A176043 a(n) = (2*n-1)*(n-1)^(n-1).

Views

Author

Keywords

A176043 a(n) = (2n-1)(n-1)^(n-1).