A000272 -id:A000272 - cp's OEIS frontend

A368927 Number of labeled loop-graphs covering a subset of {1..n} such that it is possible to choose a different vertex from each edge.

1, 2, 7, 39, 314, 3374, 45630, 744917, 14245978, 312182262, 7708544246, 211688132465, 6397720048692, 210975024924386, 7537162523676076, 289952739051570639, 11949100971787370300, 525142845422124145682, 24515591201199758681892, 1211486045654016217202663

Offset: 0

Gus Wiseman, Jan 15 2024

nonn

These are loop-graphs where every connected component has a number of edges less than or equal to the number of vertices. Also loop-graphs with at most one cycle (unicyclic) in each connected component.

			The a(0) = 1 through a(2) = 7 loop-graphs (loops shown as singletons):
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}

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

Without the choice condition we have A006125.
The case of a unique choice is A088957, unlabeled A087803.
The case without loops is A133686, complement A367867, covering A367869.
For exactly n edges and no loops we have A137916, unlabeled A137917.
For exactly n edges we have A333331 (maybe), complement A368596.
For edges of any positive size we have A367902, complement A367903.
The covering case is A369140, complement A369142.
The complement is counted by A369141.
The complement for n edges and no loops is A369143, covering A369144.
The unlabeled version is A369145, complement A369146.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts labeled covering loop-graphs, connected A062740.
Cf. A000169, A000272, A000666, A014068, A057500, A116508, A367863, A368601, A368924, A368984, A369200.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}]

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(exp(3*t/2 - 3*t^2/4)/sqrt(1-t) ))} \\ Andrew Howroyd, Feb 02 2024

Binomial transform of A369140.
Exponential transform of A369197 with A369197(1) = 2.
E.g.f.: exp(3*T(x)/2 - 3*T(x)^2/4)/sqrt(1-T(x)), where T(x) is the e.g.f. of A000169. - Andrew Howroyd, Feb 02 2024

a(7) onwards from Andrew Howroyd, Feb 02 2024

A369141 Number of labeled loop-graphs covering a subset of {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 25, 710, 29394, 2051522, 267690539, 68705230758, 35184059906570, 36028789310419722, 73786976083150073999, 302231454897259573627852, 2475880078570549574773324062, 40564819207303333310731978895956, 1329227995784915872613854321228773937

Offset: 0

Gus Wiseman, Jan 20 2024

nonn

Also labeled loop-graphs having at least one connected component containing more edges than vertices.

			The a(0) = 0 through a(3) = 25 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{1,2}}
                         {{1},{3},{1,3}}
                         {{2},{3},{2,3}}
                         {{1},{2},{3},{1,2}}
                         {{1},{2},{3},{1,3}}
                         {{1},{2},{3},{2,3}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,2},{2,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3}}
                         {{1},{3},{1,2},{2,3}}
                         {{1},{3},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3}}
                         {{2},{3},{1,2},{2,3}}
                         {{2},{3},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{2},{1,2},{1,3},{2,3}}
                         {{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{3},{1,2},{2,3}}
                         {{1},{2},{3},{1,3},{2,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Without the choice condition we have A006125, unlabeled A000088.
The case of a unique choice is A088957, unlabeled A087803.
The case without loops is A367867, covering A367868.
For edges of any positive size we have A367903, complement A367902.
For exactly n edges we have A368596, complement A333331 (maybe).
The complement is counted by A368927, covering A369140.
The covering case is A369142.
For n edges and no loops we have A369143, covering A369144.
The unlabeled version is A369146 (covering A369147), complement A369145.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable graphs, covering A367869.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
Cf. A000272, A000666, A006649, A062740, A116508, A137916, A368924, A368984, A369194.

Table[Length[Select[Subsets[Subsets[Range[n], {1,2}]],Length[Select[Tuples[#],UnsameQ@@#&]]==0&]],{n,0,5}]

Binomial transform of A369142.

a(n) = A006125(n + 1) - A368927(n). - Andrew Howroyd, Feb 02 2024

a(6) onwards from Andrew Howroyd, Feb 02 2024

A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 6, 15, 16, 1, 10, 45, 110, 125, 1, 15, 105, 435, 1080, 1296, 1, 21, 210, 1295, 5250, 13377, 16807, 1, 28, 378, 3220, 18865, 76608, 200704, 262144, 1, 36, 630, 7056, 55755, 320544, 1316574, 3542940, 4782969, 1, 45, 990, 14070, 143325, 1092105, 6258000, 26100000, 72000000, 100000000

Offset: 1

N. J. A. Sloane, May 09 2008

The rows of the triangle give the coefficients of the Ehrhart polynomials of integral Coxeter permutahedra of type A. These polynomials count lattice points in a dilated lattice polytope. For a definition see Ardila et al. (p. 1158), the generating functions of these polynomials for the classical root systems are given in theorem 5.2 (p. 1163). - Peter Luschny, May 01 2021

			Triangle begins:
[1]  1;
[2]  1,  1;
[3]  1,  3,   3;
[4]  1,  6,  15,   16;
[5]  1, 10,  45,  110,  125;
[6]  1, 15, 105,  435, 1080,  1296;
[7]  1, 21, 210, 1295, 5250, 13377, 16807;

Alois P. Heinz, Rows n = 1..141, flattened
Federico Ardila, Matthias Beck, and Jodi McWhirter, The arithmetic of Coxeter permutahedra, Rev. Acad. Colomb. Cienc. Ex. Fis. Nat. 44(173):1152-1166, 2020.
John Riordan and N. J. A. Sloane, Correspondence, 1974

Row sums give A001858. Rightmost diagonal gives A000272. Cf. A136605.
Rows reflected give A105599. - Alois P. Heinz, Oct 28 2011
Cf. A088956.
Lower diagonals give: A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687. - Alois P. Heinz, Apr 11 2014
T(2n,n) gives A302112.
For Ehrhart polynomials of integral Coxeter permutahedra of classical type cf. this sequence (type A), A343805 (type B), A343806 (type C), A343807 (type D).

T:= proc(n) option remember; if n=0 then 0 else T(n-1) +n^(n-1) *x^n/n! fi end: TT:= proc(n) option remember; expand(T(n) -T(n)^2/2) end: f:= proc(k) option remember; if k=0 then 1 else unapply(f(k-1)(x) +x^k/k!, x) fi end: A:= proc(n,k) option remember; series(f(k)(TT(n)), x,n+1) end: aa:= (n,k)-> coeff(A(n,k), x,n) *n!: a:= (n,k)-> aa(n,n-k) -aa(n,n-k-1): seq(seq(a(n,k), k=0..n-1), n=1..10);  # Alois P. Heinz, Sep 02 2008
alias(W = LambertW): EhrA := exp(-W(-t*x)/t - W(-t*x)^2/(2*t)):
ser := series(EhrA, x, 12): cx := n -> n!*coeff(ser, x, n):
T := n -> seq(coeff(cx(n), t, k), k=0..n-1):
seq(T(n), n = 1..10); # Peter Luschny, Apr 30 2021

t[0, 0] = 1; t[n_ /; n >= 1, k_] /; (0 <= k <= n-1) := t[n, k] = Sum[(i+1)^(i-1)*Binomial[n-1, i]*t[n-i-1, k-i], {i, 0, k}]; t[, ] = 0; Table[t[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Peter Bala *)
gf := E^(-(ProductLog[-(t x)] (2 + ProductLog[-(t x)]))/(2 t));
ser := Series[gf, {x, 0, 12}]; cx[n_] := n! Coefficient[ser, x, n];
Table[CoefficientList[cx[n], t], {n, 1, 10}] // Flatten  (* Peter Luschny, May 01 2021 *)

From Peter Bala, Aug 14 2012: (Start)
T(n+1,k) = Sum_{i=0..k} (i+1)^(i-1)*binomial(n,i)*T(n-i,k-i) with T(0,0)=1.
Recurrence equation for row polynomials R(n,t): R(n,t) = Sum_{k=0..n-1} (k+1)^(k-1)*binomial(n-1,k)*t^k*R(n-k-1,t) with R(0,t) = R(1,t) = 1.
The production matrix for the row polynomials of the triangle is obtained from A088956 and starts:
    1    t
    1    1    t
    3    2    1    t
   16    9    3    1    t
  125   64   18    4    1   t
(End)
E.g.f.: exp( Sum_{n >= 1} n^(n-2)*t^(n-1)*x^n/n! ). - Peter Bala, Nov 08 2015
T(n, k) = [t^k] n! [x^n] exp(-W(-t*x)/t - W(-t*x)^2/(2*t)), where W denotes the Lambert function. - Peter Luschny, Apr 30 2021 [Typo corrected after note from Andrew Howroyd, Peter Luschny, Jun 20 2021]

More terms from Alois P. Heinz, Sep 02 2008

A333331 Number of integer points in the convex hull in R^n of parking functions of length n.

Original entry on oeis.org

1, 3, 17, 144, 1623, 22804, 383415, 7501422

Offset: 1

Richard Stanley, Mar 15 2020

It is observed by Gus Wiseman in A368596 and A368730 that this sequence appears to be the complement of those sequences. If this is the case, then a(n) is the number of labeled graphs with loops allowed in which each connected component has an equal number of vertices and edges and the conjectured formula holds. Terms for n >= 9 are expected to be 167341283, 4191140394, 116425416531, ... - Andrew Howroyd, Jan 10 2024
From Gus Wiseman, Mar 22 2024: (Start)
An equivalent conjecture is that a(n) is the number of loop-graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. I call these graphs choosable. For example, the a(3) = 17 choosable loop-graphs are the following (loops shown as singletons):
  {{1},{2},{3}}  {{1},{2},{1,3}}  {{1},{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
                 {{1},{2},{2,3}}  {{1},{1,2},{2,3}}
                 {{1},{3},{1,2}}  {{1},{1,3},{2,3}}
                 {{1},{3},{2,3}}  {{2},{1,2},{1,3}}
                 {{2},{3},{1,2}}  {{2},{1,2},{2,3}}
                 {{2},{3},{1,3}}  {{2},{1,3},{2,3}}
                                  {{3},{1,2},{1,3}}
                                  {{3},{1,2},{2,3}}
                                  {{3},{1,3},{2,3}}
(End)

			For n=2 the parking functions are (1,1), (1,2), (2,1). They are the only integer points in their convex hull. For n=3, in addition to the 16 parking functions, there is the additional point (2,2,2).

R. P. Stanley (Proposer), Problem 12191, Amer. Math. Monthly, 127:6 (2020), 563.

Thomas Selig, The stochastic sandpile model on complete graphs, arXiv:2209.07301 [math.PR], 2022.

All of the following relative references pertain to the conjecture:
The case of unique choice A000272.
The version without the choice condition is A014068, covering A368597.
The case of just pairs A137916.
For any number of edges of any positive size we have A367902.
The complement A368596, covering A368730.
Allowing edges of any positive size gives A368601, complement A368600.
Counting by singletons gives A368924.
For any number of edges we have A368927, complement A369141.
The connected case is A368951.
The unlabeled version is A368984, complement A368835.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
Cf. A000169, A000666, A057500, A062740, A129271, A133686, A367863, A367903, A369146, A369199.

Conjectured e.g.f.: exp(-log(1-T(x))/2 + T(x)/2 - T(x)^2/4) where T(x) = -LambertW(-x) is the e.g.f. of A000169. - Andrew Howroyd, Jan 10 2024

A368596 Number of n-element sets of singletons or pairs of distinct elements of {1..n}, or loop graphs with n edges, such that it is not possible to choose a different element from each.

Original entry on oeis.org

0, 0, 0, 3, 66, 1380, 31460, 800625, 22758918, 718821852, 25057509036, 957657379437, 39878893266795, 1799220308202603, 87502582432459584, 4566246347310609247, 254625879822078742956, 15115640124974801925030, 952050565540607423524658, 63425827673509972464868323

Offset: 0

Gus Wiseman, Jan 04 2024

nonn

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The a(3) = 3 set-systems:
  {{1},{2},{1,2}}
  {{1},{3},{1,3}}
  {{2},{3},{2,3}}

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

The version without the choice condition is A014068, covering A368597.
The complement appears to be A333331.
For covering pairs we have A367868.
Allowing edges of any positive size gives A368600, any length A367903.
The covering case is A368730.
The unlabeled version is A368835.
A000085 counts set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A100861 counts set partitions into singletons or pairs by number of pairs.
A111924 counts set partitions into singletons or pairs by length.
A322661 counts covering half-loop-graphs, connected A062740.
A369141 counts non-choosable loop-graphs, covering A369142.
A369146 counts unlabeled non-choosable loop-graphs, covering A369147.
Cf. A000272, A000666, A057500, A129271, A133686, A367769, A367863, A367867, A367869, A367901, A367907, A368097, A369199.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}], {n}],Length[Select[Tuples[#],UnsameQ@@#&]]==0&]],{n,0,5}]

Terms a(7) and beyond from Andrew Howroyd, Jan 10 2024

A000435 Normalized total height of all nodes in all rooted trees with n labeled nodes.

Original entry on oeis.org

0, 1, 8, 78, 944, 13800, 237432, 4708144, 105822432, 2660215680, 73983185000, 2255828154624, 74841555118992, 2684366717713408, 103512489775594200, 4270718991667353600, 187728592242564421568, 8759085548690928992256, 432357188322752488126152, 22510748754252398927872000

Offset: 1

N. J. A. Sloane

This is the sequence that started it all: the first sequence in the database!
The height h(V) of a node V in a rooted tree is its distance from the root. a(n) = Sum_{all nodes V in all n^(n-1) rooted trees on n nodes} h(V)/n.
In the trees which have [0, n-1] = (0, 1, ..., n-1) as their ordered set of nodes, the number of nodes at distance i from node 0 is f(n,i) = (n-1)...(n-i)(i+1)n^(j-1), 0 <= i < n-1, i+j = n-1 (and f(n,n-1) = (n-1)!): (n-1)...(n-i) counts the words coding the paths of length i from any node to 0, n^(j-1) counts the Pruefer codes of the rest, words build by iterated deletion of the greater node of degree 1 ... except the last one, (i+1), necessary pointing at the path. If g(n,i) = (n-1)...(n-i)n^j, i+j = n-1, f(n,i) = g(n,i) - g(n,i+1), g(n,i) = Sum_{k>=i} f(n,k), the sequence is Sum_{i=1..n-1} g(n,i). - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 26 2001
If one randomly selects one ball from an urn containing n different balls, with replacement, until exactly one ball has been selected twice, the probability that this ball was also the second ball to be selected once is a(n)/n^n. See also A001865. - Matthew Vandermast, Jun 15 2004
a(n) is the number of connected endofunctions with no fixed points. - Geoffrey Critzer, Dec 13 2011
a(n) is the number of weakly connected simple digraphs on n labeled nodes where every node has out-degree 1. A digraph where all out-degrees are 1 can be called a functional digraph due to the correspondence with endofunctions. - Andrew Howroyd, Feb 06 2024

			For n = 3 there are 3^2 = 9 rooted labeled trees on 3 nodes, namely (with o denoting a node, O the root node):
   o
   |
   o     o   o
   |      \ /
   O       O
The first can be labeled in 6 ways and contains nodes at heights 1 and 2 above the root, so contributes 6*(1+2) = 18 to the total; the second can be labeled in 3 ways and contains 2 nodes at height 1 above the root, so contributes 3*2=6 to the total, giving 24 in all. Dividing by 3 we get a(3) = 24/3 = 8.
For n = 4 there are 4^3 = 64 rooted labeled trees on 4 nodes, namely (with o denoting a node, O the root node):
   o
   |
   o     o        o   o
   |     |         \ /
   o     o   o      o     o o o
   |      \ /       |      \|/
   O       O        O       O
  (1)     (2)      (3)     (4)
Tree (1) can be labeled in 24 ways and contains nodes at heights 1, 2, 3 above the root, so contributes 24*(1+2+3) = 144 to the total;
tree (2) can be labeled in 24 ways and contains nodes at heights 1, 1, 2 above the root, so contributes 24*(1+1+2) = 96 to the total;
tree (3) can be labeled in 12 ways and contains nodes at heights 1, 2, 2 above the root, so contributes 12*(1+2+2) = 60 to the total;
tree (4) can be labeled in 4 ways and contains nodes at heights 1, 1, 1 above the root, so contributes 4*(1+1+1) = 12 to the total;
giving 312 in all. Dividing by 4 we get a(4) = 312/4 = 78.

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

Robert G. Wilson v, Table of n, a(n) for n = 1..1000 (first 100 terms from T. D. Noe)
Vijayakumar Ambat, Article in the Malayalam newspaper Ayala Manorama - Padhippura, 12 June 2015, that mentions the OEIS, and in particular this sequence.
V. I. Arnold, Topological classification of complex trigonometric polynomials and the combinatorics of graphs with the same number of edges and vertices, Functional Anal. Appl., 30 (1996), 1-17.
Shalosh B. Ekhad and Doron Zeilberger, Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees, arXiv:1607.05776 [math.CO], 2016.
Shalosh B. Ekhad and Doron Zeilberger, Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees, Version on DZ's home page with more links; Local copy, pdf file only, no active links
I. P. Goulden and D. M. Jackson, A proof of a conjecture for the number of ramified coverings of the sphere by the torus, arXiv:math/9902009 [math.AG], 1999.
I. P. Goulden, D. M. Jackson, and A. Vainshtein, The number of ramified coverings of the sphere by the torus and surfaces of higher genera, arXiv:math/9902125 [math.AG], 1999.
I. P. Goulden, D. M. Jackson, and A. Vainshtein, The number of ramified coverings of the sphere by the torus and surfaces of higher genera Ann. Comb. 4 (2000), no. 1, 27-46. (See Theorem 1.1.)
Brady Haran, The Number Collector (with Neil Sloane), Numberphile Podcast (2019)
Andrew Lohr and Doron Zeilberger, On the limiting distributions of the total height on families of trees, Integers (2018) 18, Article #A32.
T. Kyle Petersen, Exponential generating functions and Bell numbers, Inquiry-Based Enumerative Combinatorics (2019) Chapter 7, Undergraduate Texts in Mathematics, Springer, Cham, 98-99.
A. Rényi and G. Szekeres, On the height of trees, Journal of the Australian Mathematical Society 7.04 (1967): 497-507. See (4.7).
Marko Riedel et al., Connected endofunctions with no fixed points, Mathematics Stack Exchange, Dec 2014.
J. Riordan, Letter to N. J. A. Sloane, Aug. 1970
J. Riordan and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.
N. J. A. Sloane, Page from 1964 notebook showing start of OEIS [includes A000027, A000217, A000292, A000332, A000389, A000579, A000110, A007318, A000058, A000215, A000289, A000324, A234953 (= A001854(n)/n), A000435, A000169, A000142, A000272, A000312, A000111]
N. J. A. Sloane, Cover of same notebook
N. J. A. Sloane, Lengths of Cycle Times in Random Neural Networks, Ph. D. Dissertation, Cornell University, February 1967; also Report No. 10, Cognitive Systems Research Program, Cornell University, 1967. This sequence appears on page 119.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Illustration of a(3) and a(4)
Yukun Yao and Doron Zeilberger, An Experimental Mathematics Approach to the Area Statistic of Parking Functions, arXiv:1806.02680 [math.CO], 2018.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 3.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A001863, A001864, A001854, A002862 (unlabeled version), A234953, A259334.

Column k=1 of A350452.

A000435 := n-> (n-1)!*add (n^k/k!, k=0..n-2);
seq(simplify((n-1)*GAMMA(n-1,n)*exp(n)),n=1..20); # Vladeta Jovovic, Jul 21 2005

f[n_] := (n - 1)! Sum [n^k/k!, {k, 0, n - 2}]; Array[f, 18] (* Robert G. Wilson v, Aug 10 2010 *)
nx = 18; Rest[ Range[0, nx]! CoefficientList[ Series[ LambertW[-x] - Log[1 + LambertW[-x]], {x, 0, nx}], x]] (* Robert G. Wilson v, Apr 13 2013 *)

x='x+O('x^30); concat(0, Vec(serlaplace(lambertw(-x)-log(1+lambertw(-x))))) \\ Altug Alkan, Sep 05 2018

A000435(n)=(n-1)*A001863(n) \\ M. F. Hasler, Dec 10 2018

from math import comb
def A000435(n): return ((sum(comb(n,k)*(n-k)**(n-k)*k**k for k in range(1,(n+1>>1)))<<1) + (0 if n&1 else comb(n,m:=n>>1)*m**n))//n # Chai Wah Wu, Apr 25-26 2023

a(n) = (n-1)! * Sum_{k=0..n-2} n^k/k!.
a(n) = A001864(n)/n.
E.g.f.: LambertW(-x) - log(1+LambertW(-x)). - Vladeta Jovovic, Apr 10 2001
a(n) = A001865(n) - n^(n-1).
a(n) = A001865(n) - A000169(n). - Geoffrey Critzer, Dec 13 2011
a(n) ~ sqrt(Pi/2)*n^(n-1/2). - Vaclav Kotesovec, Aug 07 2013
a(n)/A001854(n) ~ 1/2 [See Renyi-Szekeres, (4.7)]. Also a(n) = Sum_{k=0..n-1} k*A259334(n,k). - David desJardins, Jan 20 2017
a(n) = (n-1)*A001863(n). - M. F. Hasler, Dec 10 2018

Additional references from Valery A. Liskovets
Editorial changes by N. J. A. Sloane, Feb 03 2012
Edited by M. F. Hasler, Dec 10 2018

A007830 a(n) = (n+3)^n.

Original entry on oeis.org

1, 4, 25, 216, 2401, 32768, 531441, 10000000, 214358881, 5159780352, 137858491849, 4049565169664, 129746337890625, 4503599627370496, 168377826559400929, 6746640616477458432, 288441413567621167681, 13107200000000000000000, 630880792396715529789561

Offset: 0

Peter J. Cameron, Mar 15 1996

a(n-2) is the number of trees with n+1 unlabeled vertices and n labeled edges for n > 1. - Christian G. Bower, 12/99 [corrected by Jonathan Vos Post, Sep 22 2012]
a(n) is the number of nonequivalent primitive meromorphic functions with one pole of order n+3 on a Riemann surface of genus 0. - Noam Katz (noamkj(AT)hotmail.com), Mar 30 2001
Pikhurko writes: "Cameron demonstrated that the total number of edge-labeled trees with n >= 2 edges is (n+1)^(n-2) by showing that the number of vertex-labeled trees of size n is n+1 times larger than the number of edge-labeled ones." - Jonathan Vos Post, Sep 22 2012
With offset 1, a(n) is the number of ways to build a rooted labeled forest with some (possibly all or none) of the nodes from {1,2,...,n} and then build another forest with the remaining nodes. - Geoffrey Critzer, May 10 2013

M. Shapiro, B. Shapiro and A. Vainshtein - Ramified coverings of S^2 with one degenerate branching point and enumeration of edge-ordered graphs, Amer. Math. Soc. Transl., Vol. 180 (1997), pp. 219-227.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.27.

T. D. Noe, Table of n, a(n) for n = 0..100
Christian Brouder, William J. Keith, and Ângela Mestre, Closed forms for a multigraph enumeration, arXiv preprint arXiv:1301.0874 [math.CO], 2013-2015.
P. J. Cameron, Two-graphs and Trees, Discrete Math. 127 (1994) 63-74.
P. J. Cameron, Counting two-graphs related to trees, Elec. J. Combin., Vol. 2, #R4.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
Oleg Pikhurko, Generating Edge-Labeled Trees, American Math. Monthly, 112 (2005) 919-921.
M. Shapiro, B. Shapiro and A. Vainshtein, Ramified coverings of S^2 with one degenerate branching point and enumeration of edge-ordered graphs, 1996.
Index entries for sequences related to trees

Cf. A000169, A000272, A000312, A007778.

Cf. A008785, A008786, A008787, A008788, A008789, A008790, A008791.

[(n+3)^n: n in [0..20]]; // G. C. Greubel, Mar 06 2020

A007830:=n->(n+3)^n; seq(A007830(n), n=0..20);
T := -LambertW(-x): ser := series(exp(3*T)/(1-T), x, 20):
seq(n!*coeff(ser, x, n), n = 0..18); # Peter Luschny, Jan 20 2023

Mathematica
```
Table[(n+3)^n, {n, 0, 18}]
```

a(n)=(n+3)^n \\ Charles R Greathouse IV, Feb 06 2017

[(n+3)^n for n in (0..20)] # G. C. Greubel, Mar 06 2020

E.g.f. for b(n) = a(n-3): T(x) - (3/4)*T^2(x) + (1/6)*T^3(x), where T(x) is Euler's tree function (see A000169). - Len Smiley, Nov 17 2001
E.g.f.: -LambertW(-x)^3/(x^3 * (1+LambertW(-x))). - Vladeta Jovovic, Nov 07 2003
With offset 1: E.g.f.: exp(T(x))^2/2 where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, May 10 2013
E.g.f.: (1/2)*d/dx (LambertW(-x)/(-x))^2. - Wolfdieter Lang, Oct 25 2022

More terms from Wesley Ivan Hurt, May 05 2014

A055290 Triangle of trees with n nodes and k leaves, 2 <= k <= n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 3, 4, 2, 1, 0, 1, 4, 8, 6, 3, 1, 0, 1, 5, 14, 14, 9, 3, 1, 0, 1, 7, 23, 32, 26, 12, 4, 1, 0, 1, 8, 36, 64, 66, 39, 16, 4, 1, 0, 1, 10, 54, 123, 158, 119, 60, 20, 5, 1, 0, 1, 12, 78, 219, 350, 325, 202, 83, 25, 5, 1, 0

Offset: 2

Christian G. Bower, May 09 2000

			Triangle begins:
  n=2:  1
  n=3:  1   0
  n=4:  1   1   0
  n=5:  1   1   1   0
  n=6:  1   2   2   1   0
  n=7:  1   3   4   2   1   0
  n=8:  1   4   8   6   3   1   0
  n=9:  1   5  14  14   9   3   1   0
  n=10: 1   7  23  32  26  12   4   1   0
  n=11: 1   8  36  64  66  39  16   4   1   0
  n=12: 1  10  54 123 158 119  60  20   5   1   0
  n=13: 1  12  78 219 350 325 202  83  25   5   1   0

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 80, Problem 3.9.

Andrew Howroyd, Table of n, a(n) for n = 2..1226 (rows 2..50)
Index entries for sequences related to trees

Row sums give A000055, row sums with weight k give A003228.
Columns 3 through 12: A001399(n-4), A055291, A055292, A055293, A055294, A055295, A055296, A055297, A055298, A055299.
Cf. A055300, A055301, A238416, A304222.
The labeled version is A055314.
Central column is A358107.
Left of central column is A359398.
Cf. A000088, A000272, A001349, A001433, A002494, A185650.

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
T(n)={my(u=[y]); for(n=2, n, u=concat([y], EulerMT(u))); my(r=x*Ser(u), v=Vec(r*(1-x+x*y) + (substvec(r,[x,y],[x^2,y^2]) - r^2)/2)); vector(n-1, k, Vecrev(v[1+k]/y^2, k))}
{ my(A=T(10)); for(n=1, #A, print(A[n])) }

G.f.: A(x, y)=(1-x+x*y)*B(x, y)+(1/2)*(B(x^2, y^2)-B(x, y)^2), where B(x, y) is g.f. of A055277.

A343656 Array read by antidiagonals where A(n,k) is the number of divisors of n^k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 1, 4, 3, 3, 1, 1, 5, 4, 5, 2, 1, 1, 6, 5, 7, 3, 4, 1, 1, 7, 6, 9, 4, 9, 2, 1, 1, 8, 7, 11, 5, 16, 3, 4, 1, 1, 9, 8, 13, 6, 25, 4, 7, 3, 1, 1, 10, 9, 15, 7, 36, 5, 10, 5, 4, 1, 1, 11, 10, 17, 8, 49, 6, 13, 7, 9, 2, 1, 1, 12, 11, 19, 9, 64, 7, 16, 9, 16, 3, 6, 1

Offset: 1

Gus Wiseman, Apr 28 2021

First differs from A343658 at A(4,2) = 5, A343658(4,2) = 6.

As a triangle, T(n,k) = number of divisors of k^(n-k).

			Array begins:
       k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7
  n=1:  1   1   1   1   1   1   1   1
  n=2:  1   2   3   4   5   6   7   8
  n=3:  1   2   3   4   5   6   7   8
  n=4:  1   3   5   7   9  11  13  15
  n=5:  1   2   3   4   5   6   7   8
  n=6:  1   4   9  16  25  36  49  64
  n=7:  1   2   3   4   5   6   7   8
  n=8:  1   4   7  10  13  16  19  22
  n=9:  1   3   5   7   9  11  13  15
Triangle begins:
  1
  1  1
  1  2  1
  1  3  2  1
  1  4  3  3  1
  1  5  4  5  2  1
  1  6  5  7  3  4  1
  1  7  6  9  4  9  2  1
  1  8  7 11  5 16  3  4  1
  1  9  8 13  6 25  4  7  3  1
  1 10  9 15  7 36  5 10  5  4  1
  1 11 10 17  8 49  6 13  7  9  2  1
  1 12 11 19  9 64  7 16  9 16  3  6  1
  1 13 12 21 10 81  8 19 11 25  4 15  2  1
For example, row n = 8 counts the following divisors:
  1  64  243  256  125  36  7  1
     32  81   128  25   18  1
     16  27   64   5    12
     8   9    32   1    9
     4   3    16        6
     2   1    8         4
     1        4         3
              2         2
              1         1

Seiichi Manyama, Antidiagonals n = 1..140, flattened

Columns k=1..9 of the array give A000005, A048691, A048785, A344327, A344328, A344329, A343526, A344335, A344336.
Row n = 6 of the array is A000290.
Diagonal n = k of the array is A062319.
Array antidiagonal sums (row sums of the triangle) are A343657.
Dominated by A343658.
A000312 = n^n.
A007318 counts k-sets of elements of {1..n}.
A009998(n,k) = n^k (as an array, offset 1).
A059481 counts k-multisets of elements of {1..n}.
Cf. A000169, A000272, A002064, A002109, A066959, A143773, A146291, A176029, A251683, A282935, A326358, A327527, A334996, A343652.

Table[DivisorSigma[0,k^(n-k)],{n,10},{k,n}]

A(n, k) = numdiv(n^k); \\ Seiichi Manyama, May 15 2021

A(n,k) = A000005(A009998(n,k)), where A009998(n,k) = n^k is the interpretation as an array.

A(n,k) = Sum_{d|n} k^omega(d). - Seiichi Manyama, May 15 2021

A369197 Number of labeled connected loop-graphs with n vertices, none isolated, and at most n edges.

Original entry on oeis.org

1, 1, 3, 13, 95, 972, 12732, 202751, 3795864, 81609030, 1980107840, 53497226337, 1592294308992, 51758060711792, 1824081614046720, 69272000503031475, 2819906639193992192, 122488526636380368714, 5654657850859704139776, 276462849597009068108405, 14270030377126199463936000

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

			The a(0) = 0 through a(3) = 13 loop-graphs (loops shown as singletons):
  .  {{1}}  {{1,2}}      {{1,2},{1,3}}
            {{1},{1,2}}  {{1,2},{2,3}}
            {{2},{1,2}}  {{1,3},{2,3}}
                         {{1},{1,2},{1,3}}
                         {{1},{1,2},{2,3}}
                         {{1},{1,3},{2,3}}
                         {{2},{1,2},{1,3}}
                         {{2},{1,2},{2,3}}
                         {{2},{1,3},{2,3}}
                         {{3},{1,2},{1,3}}
                         {{3},{1,2},{2,3}}
                         {{3},{1,3},{2,3}}
                         {{1,2},{1,3},{2,3}}

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

The minimal case is A000272.
Connected case of A066383 and A369196, loopless A369192 and A369193.
The loopless case is A129271, connected case of A369191.
The case of equality is A368951, connected case of A368597.
This is the connected case of A369194.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A001187 counts connected graphs, unlabeled A001349.
A006125 counts (simple) graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A062740 counts connected loop-graphs.
A322661 counts covering loop-graphs, unlabeled A322700.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000169, A000666, A001429, A005703, A006649, A057500, A116508, A140638, A143543, A367863, A369145.

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(log(1/(1-t))/2 + 3*t/2 - 3*t^2/4 + 1 - x))} \\ Andrew Howroyd, Feb 02 2024

Logarithmic transform of A368927.
From Andrew Howroyd, Feb 02 2024: (Start)
a(n) = A000169(n) + A129271(n).
E.g.f.: log(1/(1-T(x)))/2 + 3*T(x)/2 - 3*T(x)^2/4 + 1 - x, where T(x) is the e.g.f. of A000169. (End)

a(0) changed to 1 and a(7) onwards from Andrew Howroyd, Feb 02 2024

cp's OEIS Frontend

A368927 Number of labeled loop-graphs covering a subset of {1..n} such that it is possible to choose a different vertex from each edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A369141 Number of labeled loop-graphs covering a subset of {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A333331 Number of integer points in the convex hull in R^n of parking functions of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A368596 Number of n-element sets of singletons or pairs of distinct elements of {1..n}, or loop graphs with n edges, such that it is not possible to choose a different element from each.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A000435 Normalized total height of all nodes in all rooted trees with n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A007830 a(n) = (n+3)^n.

Views

Author