A003227 -id:A003227 - cp's OEIS frontend

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

1, 2, 12, 108, 1280, 18750, 326592, 6588344, 150994944, 3874204890, 110000000000, 3423740047332, 115909305827328, 4240251492291542, 166680102383370240, 7006302246093750000, 313594649253062377472, 14890324713954061755186, 747581753430634213933056

Offset: 1

Christian G. Bower, Jun 12 2000

nonn

Total number of leaves in all labeled rooted trees with n nodes.
Number of endofunctions of [n] such that no element of [n-1] is fixed. E.g., a(3)=12: 123 -> 331, 332, 333, 311, 312, 313, 231, 232, 233, 211, 212, 213.
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). - Warut Roonguthai, May 06 2006
Determinant of the n X n matrix ((2n, n^2, 0, ..., 0), (1, 2n, n^2, 0, ..., 0), (0, 1, 2n, n^2, 0, ..., 0), ..., (0, ..., 0, 1, 2n)). - Michel Lagneau, May 04 2010
For n > 1: a(n) = A240993(n-1) / A240993(n-2). - Reinhard Zumkeller, Aug 31 2014
Total number of points m such that f^(-1)(m) = {m}, (i.e., the preimage of m is the singleton set {m}) summed over all functions f:[n]->[n]. - Geoffrey Critzer, Jan 20 2022

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Frank Ellermann, Illustration of binomial transforms
Index entries for sequences related to rooted trees

Cf. A003227, A003228, A055314, A055540, A055541, A060226, A118537.

Cf. A240993. Diagonal of A265583.

List([1..20], n-> n*(n-1)^(n-1)); # G. C. Greubel, Aug 10 2019

a055897 n = n * (n - 1) ^ (n - 1) -- Reinhard Zumkeller, Aug 31 2014

[n*(n-1)^(n-1): n in [1..20]] // Wesley Ivan Hurt, Jun 26 2014

A055897:=n->`if`(n=1,1,n*(n-1)^(n-1)); seq(A055897(n), n=1..20); # Wesley Ivan Hurt, Jun 26 2014

Join[{1},Table[n(n-1)^(n-1), {n,2,20}]] (* Harvey P. Dale, Jul 18 2011 *)

{a(n)=polcoeff(1/(1-n*x+x*O(x^n))^2, n)} \\ Paul D. Hanna, Dec 27 2012

[n*(n-1)^(n-1) for n in (1..20)] # G. C. Greubel, Aug 10 2019

E.g.f.: x/(1-T), where T=T(x) is Euler's tree function (see A000169).
a(n) = Sum_{k=1..n} A055302(n, k)*k.
a(n) = the n-th term of the (n-1)-th binomial transform of {1, 1, 4, 18, 96, ..., (n-1)*(n-1)!, ...} (cf. A001563). - Paul D. Hanna, Nov 17 2003
a(n) = (n-1)^(n-1) + Sum_{i=2..n} (n-1)^(n-i)*binomial(n-1, i-1)*(i-1) *(i-1)!. - Paul D. Hanna, Nov 17 2003
a(n) = [x^(n-1)] 1/(1 - (n-1)*x)^2. - Paul D. Hanna, Dec 27 2012
a(n) ~ exp(-1) * n^n. - Vaclav Kotesovec, Nov 14 2014

Additional comments from Vladeta Jovovic, Mar 31 2001 and Len Smiley, Dec 11 2001

A261919 Number of n-node unlabeled graphs without isolated nodes or endpoints (i.e., no nodes of degree 0 or 1).

Original entry on oeis.org

1, 0, 0, 1, 3, 11, 62, 510, 7459, 197867, 9808968, 902893994, 153723380584, 48443158427276, 28363698856991892, 30996526139142442460, 63502034434187094606966, 244852545450108200518282934, 1783161611521019613186341526720, 24603891216946828886755056314074748

Offset: 0

N. J. A. Sloane, Sep 15 2015

nonn

			From _Gus Wiseman_, Aug 15 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(5) = 11 graphs (empty columns not shown):
  {}  {12,13,23}  {12,13,24,34}        {12,13,24,35,45}
                  {13,14,23,24,34}     {12,14,25,34,35,45}
                  {12,13,14,23,24,34}  {12,15,25,34,35,45}
                                       {13,14,23,24,35,45}
                                       {12,13,24,25,34,35,45}
                                       {13,15,24,25,34,35,45}
                                       {14,15,24,25,34,35,45}
                                       {12,13,15,24,25,34,35,45}
                                       {14,15,23,24,25,34,35,45}
                                       {13,14,15,23,24,25,34,35,45}
                                       {12,13,14,15,23,24,25,34,35,45}
(End)

F. Harary, Graph Theory, Wiley, 1969. See illustrations in Appendix 1.

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..26 from Max Alekseyev)
N. J. A. Sloane, Illustration of a(0)-a(5) [Ignore the graphs with isolated nodes]

Cf. A004108 (connected version), A004110 (version allowing isolated nodes).
The labeled version is A100743.
Cf. A003227, A006125, A007146, A059166, A095983, A322396.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1-x^p[[i]], {i, 1, Length[p]}], x, n-k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}]; b[0] = 1;
a[n_] := b[n] - b[n-1];
a /@ Range[0, 19] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd in A004110 *)

First differences of A004110: a(n) = A004110(n)-A004110(n-1).

Euler transform of A004108, if we assume A004108(1) = 0. - Gus Wiseman, Aug 15 2019

a(1)-a(11) computed by Brendan McKay, Sep 15 2015
a(12)-a(26) computed from A004110 by Max Alekseyev, Sep 16 2015
a(0) = 1 prepended by Gus Wiseman, Aug 15 2019

A302515 T(n,k)=Number of nXk 0..1 arrays with every element equal to 0, 1, 4 or 5 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Original entry on oeis.org

1, 2, 2, 3, 3, 4, 5, 3, 4, 8, 8, 5, 11, 6, 16, 13, 7, 15, 9, 9, 32, 21, 13, 21, 28, 14, 14, 64, 34, 23, 52, 36, 48, 21, 22, 128, 55, 37, 118, 80, 90, 89, 28, 35, 256, 89, 63, 220, 235, 199, 184, 163, 37, 56, 512, 144, 109, 408, 541, 689, 458, 376, 297, 51, 90, 1024, 233, 183

Offset: 1

R. H. Hardin, Apr 09 2018

Table starts
...1..2..3...5....8...13....21.....34......55......89......144.......233
...2..3..3...5....7...13....23.....37......63.....109......183.......309
...4..4.11..15...21...52...118....220.....408.....852.....1764......3460
...8..6..9..28...36...80...235....541....1115....2554.....6095.....13920
..16..9.14..48...90..199...689...2125....5410...13908....39850....114503
..32.14.21..89..184..458..1784...7182...22544...67096...220654....775150
..64.22.28.163..376.1088..4558..23944...95681..344525..1302832...5550086
.128.35.37.297..832.2651.12324..82857..414880.1775176..7735877..39371229
.256.56.51.544.1744.6257.32336.282857.1748514.8778929.44362463.272701915

			Some solutions for n=5 k=4
..0..0..1..0. .0..1..0..1. .0..1..1..1. .0..1..0..1. .0..1..0..1
..1..1..1..0. .0..1..0..1. .0..1..0..1. .0..1..1..1. .0..1..0..1
..1..0..1..0. .0..0..1..1. .0..1..0..1. .0..0..0..1. .0..1..0..1
..1..0..1..0. .1..1..0..0. .0..1..0..1. .0..1..0..1. .0..1..0..1
..1..0..0..0. .1..0..1..0. .0..0..0..1. .0..1..0..1. .0..1..0..1

R. H. Hardin, Table of n, a(n) for n = 1..511

Column 1 is A000079(n-1).
Column 2 is A001611(n+1).
Row 1 is A000045(n+1).
Row 2 is A003227(n-1) for n>2.

Empirical for column k:
k=1: a(n) = 2*a(n-1)
k=2: a(n) = 2*a(n-1) -a(n-3)
k=3: a(n) = a(n-1) +a(n-4) for n>7
k=4: a(n) = a(n-1) +2*a(n-3) +2*a(n-4) -a(n-6) -a(n-7) for n>10
k=5: a(n) = a(n-1) +6*a(n-3) +2*a(n-5) -12*a(n-6) -4*a(n-7) +8*a(n-9) for n>11
k=6: a(n) = a(n-1) +6*a(n-3) +5*a(n-4) +3*a(n-5) -8*a(n-6) -6*a(n-7) -3*a(n-8) for n>12
k=7: [order 15] for n>21
Empirical for row n:
n=1: a(n) = a(n-1) +a(n-2)
n=2: a(n) = a(n-1) +2*a(n-3) for n>5
n=3: a(n) = a(n-1) +2*a(n-3) +4*a(n-4) for n>7
n=4: a(n) = a(n-1) +a(n-2) +3*a(n-3) +5*a(n-4) -a(n-5) -5*a(n-6) -4*a(n-7) for n>10
n=5: [order 13] for n>17
n=6: [order 23] for n>29
n=7: [order 50] for n>55

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

Original entry on oeis.org

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

A003228 Endpoints in trees with n nodes.

Original entry on oeis.org

1, 2, 2, 5, 9, 21, 43, 101, 226, 556, 1333, 3365, 8500, 22007, 57258, 151264, 401761, 1077063, 2902599, 7871250, 21440642, 58672589, 161155637, 444240627, 1228400744, 3406668865, 9472308269, 26402207803, 73755064178

Offset: 1

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson and A. J. Schwenk, The distribution of trees in a large random tree, Discr. Math., 12 (1975), 359-372.
Eric Weisstein's World of Mathematics, Tree Leaf.
Index entries for sequences related to trees

Cf. A000055, A003227, A055290, A055372.

a(n) = Sum_{k=1..n} k*c(n, k), where c(n, k) = A055290(n, k) has g.f. (1-x+x*y)*B(x, y)+(1/2)*(B(x^2, y^2)-B(x, y)^2) and B(x, y) is g.f. for A055372.

Corrected and extended with formula by Christian G. Bower, May 25 2000

A055540 Total number of leaves (nodes of vertex degree 1) in all graphs of n nodes.

Original entry on oeis.org

0, 2, 4, 14, 38, 153, 766, 6259, 88064, 2324157, 116563882, 11060411527, 1968703079886, 654492092481733, 406111248305672980, 471005105043787823717, 1023566652048387537072658, 4179937690541808658135640875, 32172436158252943170541450460638

Offset: 1

Eric W. Weisstein

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Tree Leaf

Cf. A003227, A003228, A055541, A327371.

\\ See A327371 for G.
seq(n)=Vec(subst(deriv(G(n), y), y, 1), -n) \\ Andrew Howroyd, Jan 22 2021

a(n) = Sum_{k=1..n} k*A327371(n, k). - Andrew Howroyd, Sep 04 2019

a(8) and a(9) from Eric W. Weisstein, Jun 02 2004
a(10) from Andrew Howroyd, Sep 04 2019
Terms a(11) and beyond from Andrew Howroyd, Jan 22 2021

A317580 Number of unlabeled rooted identity trees with n nodes and a distinguished leaf.

Original entry on oeis.org

1, 1, 1, 3, 5, 12, 28, 66, 153, 367, 880, 2121, 5127, 12441, 30248, 73746, 180077, 440571, 1079438, 2648511, 6506170, 16001256, 39393173, 97074140, 239419963, 590972968, 1459808862, 3608483107, 8925476591, 22090139751, 54702648393, 135533335933, 335967782916

Offset: 1

Gus Wiseman, Jul 31 2018

nonn

Total number of leaves in all rooted identity trees with n nodes. - Andrew Howroyd, Aug 28 2018

			The a(6) = 12 rooted identity trees with a distinguished leaf:
(((((O))))),
(((O(o)))), (((o(O)))),
((O((o)))), ((o((O)))),
(O(((o)))), (o(((O)))),
((O)((o))), ((o)((O))),
(O(o(o))), (o(O(o))), (o(o(O))).

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000081, A001678, A003227, A003238, A004111, A038046, A055327, A067824, A301342, A316784.

urit[n_]:=Join@@Table[Select[Union[Sort/@Tuples[urit/@ptn]],UnsameQ@@#&],{ptn,IntegerPartitions[n-1]}];
Table[Sum[Length[Flatten[{t/.{}->1}]],{t,urit[n]}],{n,10}]

WeighMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, (-1)^(i-1)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
seq(n)={my(v=[y]); for(n=2, n, v=concat([y], WeighMT(v))); apply(p -> subst(deriv(p), y, 1), v)} \\ Andrew Howroyd, Aug 28 2018

a(n) = Sum_{k=1, n} k*A055327(n, k). - Andrew Howroyd, Aug 28 2018

Terms a(26) and beyond from Andrew Howroyd, Aug 28 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A261919 Number of n-node unlabeled graphs without isolated nodes or endpoints (i.e., no nodes of degree 0 or 1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A302515 T(n,k)=Number of nXk 0..1 arrays with every element equal to 0, 1, 4 or 5 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A003228 Endpoints in trees with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A055540 Total number of leaves (nodes of vertex degree 1) in all graphs of n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A317580 Number of unlabeled rooted identity trees with n nodes and a distinguished leaf.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs