A053506 -id:A053506 - cp's OEIS frontend

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

1, 0, 1, 0, 2, 2, 0, 18, 6, 3, 0, 192, 48, 12, 4, 0, 2500, 500, 100, 20, 5, 0, 38880, 6480, 1080, 180, 30, 6, 0, 705894, 100842, 14406, 2058, 294, 42, 7, 0, 14680064, 1835008, 229376, 28672, 3584, 448, 56, 8, 0, 344373768, 38263752, 4251528, 472392, 52488, 5832, 648, 72, 9

Offset: 0

Alois P. Heinz, Aug 19 2013

			T(0,0) = 1: [].
T(1,1) = 1: [1].
T(2,1) = 2: [1,2], [2,1].
T(2,2) = 2: [1,1], [2,2].
T(3,1) = 18: [1,1,2], [1,1,3], [1,2,1], [1,2,3], [1,3,1], [1,3,2], [2,1,2], [2,1,3], [2,2,1], [2,2,3], [2,3,1], [2,3,2], [3,1,2], [3,1,3], [3,2,1], [3,2,3], [3,3,1], [3,3,2].
T(3,2) = 6: [1,2,2], [1,3,3], [2,1,1], [2,3,3], [3,1,1], [3,2,2].
T(3,3) = 3: [1,1,1], [2,2,2], [3,3,3].
Triangle T(n,k) begins:
  1;
  0,        1;
  0,        2,       2;
  0,       18,       6,      3;
  0,      192,      48,     12,     4;
  0,     2500,     500,    100,    20,    5;
  0,    38880,    6480,   1080,   180,   30,   6;
  0,   705894,  100842,  14406,  2058,  294,  42,  7;
  0, 14680064, 1835008, 229376, 28672, 3584, 448, 56,  8;

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

Row sums give: A000312.
Columns k=0-4 give: A000007, A066274(n) = 2*A081131(n) for n>1, A053506(n) for n>2, A055865(n-1) = A085389(n-1) for n>3, A085390(n-1) for n>4.
Main diagonal gives: A028310.
Lower diagonals include (offsets may differ): A002378, A045991, A085537, A085538, A085539.
Cf. A228154, A228617.

T:= (n, k)-> `if`(n=0 and k=0, 1, `if`(k<1 or k>n, 0,
             `if`(k=n, n, (n-1)*n^(n-k)))):
seq(seq(T(n,k), k=0..n), n=0..12);

f[0,0]=1;
f[n_,k_]:=Which[1<=k<=n-1,n^(n-k)*(n-1),k<1,0,k==n,n,k>n,0];
Table[Table[f[n,k],{k,0,n}],{n,0,10}]//Grid (* Geoffrey Critzer, May 19 2014 *)

T(0,0) = 1, else T(n,k) = 0 for k<1 or k>n, else T(n,n) = n, else T(n,k) = (n-1)*n^(n-k).
Sum_{k=0..n}   T(n,k) = A000312(n).
Sum_{k=0..n} k*T(n,k) = A031972(n).

A053508 a(n) = binomial(n-1,3)*n^(n-4).

Original entry on oeis.org

0, 0, 0, 1, 20, 360, 6860, 143360, 3306744, 84000000, 2338460520, 70946979840, 2332989862060, 82726831323136, 3148511132812500, 128071114403348480, 5546563698427324720, 254873089955815096320, 12387799656377835411984, 635043840000000000000000

Offset: 1

N. J. A. Sloane, Jan 15 2000

nonn

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Prop. 5.3.2.

G. C. Greubel, Table of n, a(n) for n = 1..250

Cf. A000169, A053506, A053507, A053509.

List([1..25], n-> Binomial(n-1,3)*n^(n-4)); # G. C. Greubel, May 15 2019

[Binomial(n-1,3)*n^(n-4): n in [1..25]]; // G. C. Greubel, Nov 14 2017

Table[Binomial[n-1,3]n^(n-4),{n,25}] (* Harvey P. Dale, Jun 17 2014 *)
With[{nmax = 25}, CoefficientList[Series[LambertW[-x]^4/4!, {x, 0, nmax}], x]*Range[0, nmax]!] (* G. C. Greubel, Nov 14 2017 *)

vector(25, n, binomial(n-1,3)*n^(n-4)) \\ G. C. Greubel, Jan 18 2017

[binomial(n-1,3)*n^(n-4) for n in (1..25)] # G. C. Greubel, May 15 2019

E.g.f.: LambertW(-x)^4/4!. - Vladeta Jovovic, Apr 07 2001

A053509 a(n) = binomial(n-1,4)*n^(n-5).

Original entry on oeis.org

0, 0, 0, 0, 1, 30, 735, 17920, 459270, 12600000, 372027810, 11824496640, 403786706895, 14772648450560, 577227041015625, 24013333950627840, 1060372471758165020, 49558656380297379840, 2444960458495625410260, 127008768000000000000000

Offset: 1

N. J. A. Sloane, Jan 15 2000

nonn

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Prop. 5.3.2.

G. C. Greubel, Table of n, a(n) for n = 1..250

Cf. A000169, A053506, A053507, A053508.

List([1..25], n-> Binomial(n-1,4)*n^(n-5)) # G. C. Greubel, May 15 2019

[Binomial(n-1,4)*n^(n-5): n in [1..30]]; // G. C. Greubel, Nov 14 2017

Table[Binomial[n-1,4]*n^(n-5), {n,1,25}] (* G. C. Greubel, Jan 18 2017 *)

vector(25, n, binomial(n-1,4)*n^(n-5)) \\ G. C. Greubel, Jan 18 2017

[binomial(n-1,4)*n^(n-5) for n in (1..25)] # G. C. Greubel, May 15 2019

E.g.f.: -LambertW(-x)^5/5!. - Vladeta Jovovic, Apr 07 2001

A057817 Moebius invariant of cographic hyperplane arrangement for complete graph K_n. Also value of Tutte dichromatic polynomial T_G(0,1) for G=K_n. Also alternating sum F_{n,1} - F_{n,2} + F_{n,3} - ..., where F_{n,k} is the number of labeled forests on n nodes with k connected components.

Original entry on oeis.org

1, 0, 1, 6, 51, 560, 7575, 122052, 2285353, 48803904, 1171278945, 31220505800, 915350812299, 29281681800384, 1015074250155511, 37909738774479600, 1517587042234033425, 64830903253553212928, 2944016994706445303937

Offset: 1

Alex Postnikov (apost(AT)math.mit.edu), Nov 06 2000

The rank of reduced homology groups for the matroid complex of acyclic subgraphs in complete graph K_n (n>1). It is also the number of labeled edge-rooted forests on n-1 nodes where each connected component contains at least one edge.

The description of this sequence as the number of labeled edge-rooted forests on n-1 nodes appeared in W. Kook's Ph.D. thesis (G. Carlsson, advisor), Categories of acyclic graphs and automorphisms of free groups, Stanford University, 1996.

			For n=4, the number of labeled edge-rooted forests on three (= n-1) nodes is 6: There are 3 labeled trees on three nodes. These are the only forests with at least one edge in each connected component. Each tree has 2 edges and each of the two may be marked as the root.

W. Kook, Categories of acyclic graphs and automorphisms of free groups, Ph.D. thesis (G. Carlsson, advisor), Stanford University, 1996

Vincenzo Librandi, Table of n, a(n) for n = 1..200
I. Novik, A. Postnikov and B. Sturmfels, Syzygies of oriented matroids, arXiv:math/0009241 [math.CO], 2000.
A. Postnikov, Papers

Cf. A053506, A060917, A060918.

Cf. column k=2 of A243098.

for n from 1 to 50 do printf(`%d,`, (n-1)*sum((n-2)!/(2^k*k!*(n-2-2*k)!)*n^(n-2-2*k), k=0..floor((n-2)/2))) od:

s=20;(*generates first s terms starting from n=2*) K := Exp[Sum[(m-1)*(m^(m-2))*(x^m)/m!, {m, 2, 2s}]]; S := Series[K, {x, 0, s}]; h[i_] := SeriesCoefficient[S, i-1]*(i-1)!; Table[h[n+1], {n, s}]
a[n_] := (n-2)*Sum[ (n-1)^(n-2k-3)*(n-3)! / (2^k*k!*(n-2k-3)!), {k, 0, Floor[ (n-3)/ 2 ]}]; a[1] = 1; Table[a[n], {n, 1, 19}] (* Jean-François Alcover, Dec 11 2012, after Maple *)

a(n)=if(n<1,0,(n-1)!*polcoeff(exp(sum(k=1,n-1,k^(k-1)*x^k/k!,O(x^n))^2/2),n-1))

a(n)=if(n<2,n==1,sum(k=0,(n-3)\2,(n-1)!/(2^k*k!*(n-3-2*k)!)*(n-1)^(n-4-2*k)))

df(n)=(2*n)!/(n!*2^n);  \\ A001147
he(n,x)=x^n+sum(k=1, n\2, binomial(n,2*k) * df(k) * x^(n-2*k) );
a(n)=if( n<3, n==1, (n-2)*he(n-3, n-1) );
/* Joerg Arndt, May 06 2013 */

E.g.f.: exp(1/2*LambertW(-x)^2). - Vladeta Jovovic, Apr 10 2001
E.g.f.: integral exp( Sum_{m>1}(m-1)*m^{m-2}*x^{m}/m!) dx (n-1) Sum_{k=0}^{[(n-2)/2]} binomial((n-2)! , 2^k k! (n-2-2k)!) n^{n-2-2k}.
E.g.f.: exp( Sum_{m>1}(m-1)*m^{m-2}*x^{m}/m!).
E.g.f.: integral(exp(1/2*LambertW(-x)^2)dx). - Vladeta Jovovic, Apr 10 2001
a(n) ~ exp(-1/2)*n^(n-2). - Vaclav Kotesovec, Dec 12 2012
a(n) = n^(n-2) - Sum_{k=1..n-1} binomial(n-1,k-1) * k^(k-2) * a(n-k). - Ilya Gutkovskiy, Feb 07 2020

More terms from James Sellers, Nov 08 2000
Additional comments from Woong Kook (andrewk(AT)math.uri.edu), Feb 12 2002
Further comments from Michael Somos, Sep 18 2002
Updated author's URL and e-mail address R. J. Mathar, May 23 2010

A065513 Number of endofunctions of [n] with a cycle a->b->c->a and for all x in [n], some iterate f^k(x)=a.

Original entry on oeis.org

2, 24, 300, 4320, 72030, 1376256, 29760696, 720000000, 19292299290, 567575838720, 18197320924068, 631732166467584, 23613833496093750, 945755921747804160, 40410678374256222960, 1835086247681868693504, 88263072551692077310386, 4482662400000000000000000

Offset: 3

Len Smiley, Nov 27 2001

nonn

			a(4)=24: 1->2->3->1<-4; 2->3->1->2<-4; 3->1->2->3<-4 1->3->2->1<-4; 3->2->1->3<-4; 2->1->3->2<-4 (repeat with 1,2, then 3 excluded from cycle)

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

Cf. A000169 (unique cycle is length 1), A053506 (unique cycle has length 2).

Column k=3 of A201685.

[(n-1)*(n-2)*n^(n-3): n in [3..50]]; // G. C. Greubel, Nov 14 2017

T := x->-LambertW(-x); a := []; f := series((T(x))^3/3,x,24); for m from 1 to 24 do a := [op(a),op(2*m-1,f)*(m+2)! ] od; print(a);

nn = 18; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}];
Range[0, nn]! CoefficientList[Series[2 t^3/3!, {x, 0, nn}], x] (* Geoffrey Critzer, Aug 14 2013 *)

for(n=3,50, print1((n-1)*(n-2)*n^(n-3), ", ")) \\ G. C. Greubel, Nov 14 2017

E.g.f.: T^3/3 where T=T(x) is Euler's tree function (see A000169).
a(n) = (n-1)*(n-2)*n^(n-3). - Vaclav Kotesovec, Oct 05 2013
a(n) = 2*A053507(n). - Vaclav Kotesovec, Oct 07 2016

A085389 a(1) = 1; for n >= 2, a(n) = (n*(n+1)^(n-1))/(n+1).

Original entry on oeis.org

1, 2, 12, 100, 1080, 14406, 229376, 4251528, 90000000, 2143588810, 56757583872, 1654301902188, 52644347205632, 1816448730468750, 67553994410557440, 2694045224950414864, 114692890480116793344, 5191945444217181018258, 249036800000000000000000, 12617615847934310595791220

Offset: 1

Paul Barry, Jun 30 2003

Paolo Xausa, Table of n, a(n) for n = 1..350
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

Cf. A053506, A085390.

A085389[n_] := If[n == 1, 1, n*(n+1)^(n-2)];
Array[A085389, 25] (* Paolo Xausa, Aug 07 2025 *)

Main subdiagonal of A085388.
a(n) = A055865(n), n>1. - R. J. Mathar, Sep 12 2008
a(n) = [x^n] x*(1 - x)/(1 - x - n*x). - Ilya Gutkovskiy, Oct 02 2017

Name edited by Paolo Xausa, Aug 07 2025

A085388 First differences of n^k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 6, 4, 0, 1, 4, 12, 18, 8, 0, 1, 5, 20, 48, 54, 16, 0, 1, 6, 30, 100, 192, 162, 32, 0, 1, 7, 42, 180, 500, 768, 486, 64, 0, 1, 8, 56, 294, 1080, 2500, 3072, 1458, 128, 0, 1, 9, 72, 448, 2058, 6480, 12500, 12288, 4374, 256, 0, 1, 10, 90, 648

Offset: 1

Paul Barry, Jun 30 2003

T(n,k) is the number of k-digit numbers in base n; n,k >= 2. - Mohammed Yaseen, Nov 11 2022

			Rows begin
  1,   0,   0,   0,   0, ...
  1,   1,   2,   4,   8, ...
  1,   2,   6,  18,  54, ...
  1,   3,  12,  48, 192, ...
  1,   4,  20, 100, 500, ...

Rows include A011782, A025192, A002001, A005054, A052934, A055272, A055274, A055275, A052268, A055276.
Diagonals include A053506, A085389, A085390.
Row-wise binomial transform is A083064.

T(n,k) = (n-1)*n^(k-1) + 0^k/n. - Corrected by Mohammed Yaseen, Nov 11 2022

T(n,0) = 1; T(n,k) = n^k - n^(k-1) for k >= 1. - Mohammed Yaseen, Nov 11 2022

Offset corrected by Mohammed Yaseen, Nov 11 2022

A065888 a(n) = number of endofunctions on [n] with a 4-cycle a->b->c->d->a and for any x in [n], some iterate f^k(x) = a.

Original entry on oeis.org

6, 120, 2160, 41160, 860160, 19840464, 504000000, 14030763120, 425681879040, 13997939172360, 496360987938816, 18891066796875000, 768426686420090880, 33279382190563948320, 1529238539734890577920, 74326797938267012471904

Offset: 4

Len Smiley, Nov 27 2001

nonn

			a(4) = 6 : 3 [choices of 1's opposite in cycle] * 2 [choices of 1's image]

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

Cf. A000169 (1-cycle), A053506 (2-cycle), A065513 (3-cycle), A065889 (= A065888/2: underlying simple graphs).

Rest[Rest[Rest[Rest[CoefficientList[Series[(LambertW[-x])^4/4, {x, 0, 20}], x]* Range[0, 20]!]]]] (* Vaclav Kotesovec, Oct 05 2013 *)
Table[(n-1)(n-2)(n-3)n^(n-4),{n,4,20}] (* Harvey P. Dale, Dec 04 2015 *)

E.g.f.: T^4/4 where T = T(x) is Euler's tree function (see A000169).

a(n) = (n-1)*(n-2)*(n-3)*n^(n-4). - Vaclav Kotesovec, Oct 05 2013

A085390 a(n) = (n(n+1)^(n-2)+0^(n-2))/(n+1).

Original entry on oeis.org

1, 3, 20, 180, 2058, 28672, 472392, 9000000, 194871710, 4729798656, 127253992476, 3760310514688, 121096582031250, 4222124650659840, 158473248526494992, 6371827248895377408, 273260286537746369382, 12451840000000000000000

Offset: 2

Paul Barry, Jun 30 2003

A diagonal of square array A085388.

Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets

Cf. A085389, A053506.

A201685 Triangular array read by rows. T(n,k) is the number of connected endofunctions on {1,2,...,n} that have exactly k nodes in the unique cycle of its digraph representation.

Original entry on oeis.org

1, 2, 1, 9, 6, 2, 64, 48, 24, 6, 625, 500, 300, 120, 24, 7776, 6480, 4320, 2160, 720, 120, 117649, 100842, 72030, 41160, 17640, 5040, 720, 2097152, 1835008, 1376256, 860160, 430080, 161280, 40320, 5040, 43046721, 38263752, 29760696, 19840464, 11022480, 4898880, 1632960, 362880, 40320

Offset: 1

Geoffrey Critzer, Dec 03 2011

Column k=1: A000169,
Column k=2: A053506,
Column k=3: A065513.
Row sums:   A001865.
T(n,n) = (n-1)!, T(n,n-1) = n!.
Sum_{k=1..n} T(n,k)*k = n^n. - Geoffrey Critzer, May 13 2013
From the asymptotic given by N-E. Fahssi in A001865, we see the expected size of the cycle grows as (2*n/Pi)^(1/2). - Geoffrey Critzer, May 13 2013
Central terms: A277168. - Paul D. Hanna, Oct 01 2016

			Triangle begins as:
     1;
     2,    1;
     9,    6,    2;
    64,   48,   24,    6;
   625,  500,  300,  120,  24;
  7776, 6480, 4320, 2160, 720, 120;

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A000169, A001865, A053506, A065513, A277168.

Flat(List([1..12], n-> List([1..n], k-> Binomial(n-1,k-1)*n^(n-k)*Factorial(k-1) ))); # G. C. Greubel, Jan 08 2020

[Binomial(n-1,k-1)*n^(n-k)*Factorial(k-1): k in [1..n], n in [1..12]]; // G. C. Greubel, Jan 08 2020

T:= (n, k)-> binomial(n-1, k-1)*n^(n-k)*(k-1)!:
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Aug 14 2013

f[list_] := Select[list, # > 0 &]; t = Sum[n^(n - 1) x^n/n!, {n, 1, 20}]; Map[f, Drop[Range[0, 10]! CoefficientList[Series[Log[1/(1 - y t)], {x, 0, 10}], {x, y}], 1]] // Grid

T(n,k) = binomial(n-1,k-1)*n^(n-k)*(k-1)!; \\ G. C. Greubel, Jan 08 2020

[[binomial(n-1,k-1)*n^(n-k)*factorial(k-1) for k in (1..n)] for n in (1..12)] # G. C. Greubel, Jan 08 2020

E.g.f.: log(1/(1-y*A(x))) where A(x) is the e.g.f. for A000169.

T(n,k) = binomial(n-1,k-1)*n^(n-k)*(k-1)!. - Geoffrey Critzer, May 13 2013

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A053508 a(n) = binomial(n-1,3)*n^(n-4).

Views

Author

Keywords

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A053509 a(n) = binomial(n-1,4)*n^(n-5).

Views

Author

Keywords

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A057817 Moebius invariant of cographic hyperplane arrangement for complete graph K_n. Also value of Tutte dichromatic polynomial T_G(0,1) for G=K_n. Also alternating sum F_{n,1} - F_{n,2} + F_{n,3} - ..., where F_{n,k} is the number of labeled forests on n nodes with k connected components.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A065513 Number of endofunctions of [n] with a cycle a->b->c->a and for all x in [n], some iterate f^k(x)=a.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A085389 a(1) = 1; for n >= 2, a(n) = (n*(n+1)^(n-1))/(n+1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions