A001864 -id:A001864 - cp's OEIS frontend

A036276 a(n) = A001864(n+1)/2.

0, 1, 12, 156, 2360, 41400, 831012, 18832576, 476200944, 13301078400, 406907517500, 13534968927744, 486470108273448, 18790567023993856, 776343673316956500, 34165751933338828800, 1595693034061797583328, 78831769938218360930304, 4107393289066148637198444

Offset: 0

N. J. A. Sloane

This is Sum_{all n^(n-2) labeled trees T on n nodes} Sum_{1<=i

a(n) is the total number of all defects in defective parking functions of length n+1. - Alois P. Heinz, Nov 28 2015

With offset 1, a(n) is the number of unordered pairs {f,g} where for some nonempty proper subset S of [n], f:S->S and g:[n]\S->[n]\S. - Geoffrey Critzer, Apr 23 2017

Alois P. Heinz, Table of n, a(n) for n = 0..380
J. Riordan and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.
Peter Winkler, Mean distance in a tree, in Computational algorithms, operations research and computer science (Burnaby, BC, 1987). Discrete Appl. Math. 27 (1990), no. 1-2, 179-185. [For background information only.]

Cf. A001864, A264902.

Table[Sum[Binomial[n, k] (n - k)^(n - k) k^k, {k, n - 1}]/2, {n, 18}] (* Michael De Vlieger, Apr 24 2017, after Harvey P. Dale at A001864 *)

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

a(n) = Sum_{k>0} k * A264902(n+1,k). - Alois P. Heinz, Nov 28 2015

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

A001863 Normalized total height of rooted trees with n nodes.

Original entry on oeis.org

0, 1, 4, 26, 236, 2760, 39572, 672592, 13227804, 295579520, 7398318500, 205075286784, 6236796259916, 206489747516416, 7393749269685300, 284714599444490240, 11733037015160276348, 515240326393584058368, 24019843795708471562564, 1184776250223810469888000

Offset: 1

N. J. A. Sloane

a(n) is the number of partial functions f from [n-1] into [n-1] such that f^k(1) is undefined for some k>=1. - Geoffrey Critzer, Mar 05 2022

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).

G. C. Greubel, Table of n, a(n) for n = 1..385 (terms 1..100 from T. D. Noe)
H. Bergeron, E. M. F. Curado, J. P. Gazeau and L. M. C. S. Rodrigues, A note about combinatorial sequences and Incomplete Gamma function, arXiv preprint arXiv: 1309.6910 [math.CO], 2013.
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.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000435, A000169, A001864.

[0] cat [&+[Factorial(n-2)*n^k div Factorial(k): k in [0..n-2]]: n in [2..24]]; // Vincenzo Librandi, Dec 10 2018

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

a[n_] := Sum[(n-2)!*n^k/k!, {k, 0, n-2}]; Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Oct 09 2012, from Maple *)
Table[Sum[(n-2)! n^k/k!,{k,0,n-2}],{n,30}] (* Harvey P. Dale, Jun 19 2016 *)

apply( A001863(n)=sum(k=0,n-2,(n-2)!/k!*n^k), [1..20]) \\ This defines the function A001863; apply(...) provides a check and illustration. - G. C. Greubel, Nov 14 2017, edited by M. F. Hasler, Dec 09 2018

from math import comb
def A001863(n): return 0 if n<2 else ((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//(n-1) # Chai Wah Wu, Apr 25-26 2023

E.g.f.: -exp(1)*x*(Ei(-1-LambertW(-x))-Ei(-1)) - LambertW(-x) + log(1+LambertW(-x)). - Vladeta Jovovic, Sep 29 2003
a(n)*(n-1) = A000435(n). - M. F. Hasler, Dec 10 2018
E.g.f.: x*diff(A000169(x),x)^2. - Vladimir Kruchinin, Jun 07 2020
a(n) = (n-2)! * Sum_{k=0..n-2} n^k/k! for n > 1. - Jianing Song, Aug 08 2022

A066324 Number of endofunctions on n labeled points constructed from k rooted trees.

Original entry on oeis.org

1, 2, 2, 9, 12, 6, 64, 96, 72, 24, 625, 1000, 900, 480, 120, 7776, 12960, 12960, 8640, 3600, 720, 117649, 201684, 216090, 164640, 88200, 30240, 5040, 2097152, 3670016, 4128768, 3440640, 2150400, 967680, 282240, 40320, 43046721

Offset: 1

Christian G. Bower, Dec 14 2001

T(n,k) = number of endofunctions with k recurrent elements. - Mitch Harris, Jul 06 2006

The sum of row n is n^n, for any n. Basically the same sequence arises when studying random mappings (see A243203, A243202). - Stanislav Sykora, Jun 01 2014

			Triangle T(n,k) begins:
       1;
       2,      2;
       9,     12,      6;
      64,     96,     72,     24;
     625,   1000,    900,    480,   120;
    7776,  12960,  12960,   8640,  3600,   720;
  117649, 201684, 216090, 164640, 88200, 30240, 5040;
  ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 87, see (2.3.28).
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.32.

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

Column 1: A000169.
Main diagonal: A000142.
T(n, n-1): A062119.
Row sums give A000312.
Cf. A001864, A021010, A063169, A122525, A144084, A243203.

T:= (n, k)-> k*n^(n-k)*(n-1)!/(n-k)!:
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Aug 22 2012

f[list_] := Select[list, # > 0 &]; t = Sum[n^(n - 1) x^n/n!, {n, 1, 20}]; Flatten[Map[f, Drop[Range[0, 10]! CoefficientList[Series[1/(1 - y*t), {x, 0, 10}], {x, y}], 1]]] (* Geoffrey Critzer, Dec 05 2011 *)

T(n, k)=k*n^(n-k)*(n-1)!/(n-k)! \\ Charles R Greathouse IV, Dec 05 2011

T(n,k) = k*n^(n-k)*(n-1)!/(n-k)!.
E.g.f. (relative to x): A(x, y)=1/(1-y*B(x)) - 1 = y*x +(2*y+2*y^2)*x^2/2! + (9*y+12*y^2+6*y^3)*x^3/3! + ..., where B(x) is e.g.f. A000169.
From Peter Bala, Sep 30 2011: (Start)
Let F(x,t) = x/(1+t*x)*exp(-x/(1+t*x)) = x*(1 - (1+t)*x + (1+4*t+2*t^2)*x^2/2! - ...). F is essentially the e.g.f. for A144084 (see also A021010). Then the e.g.f. for the present table is t*F(x,t)^(-1), where the compositional inverse is taken with respect to x.
Removing a factor of n from the n-th row entries results in A122525 in row reversed form.
(End)
Sum_{k=2..n} (k-1) * T(n,k) = A001864(n). - Geoffrey Critzer, Aug 19 2013
Sum_{k=1..n} k * T(n,k) = A063169(n). - Alois P. Heinz, Dec 15 2021

A368849 Triangle read by rows: T(n, k) = binomial(n, k - 1)(k - 1)^(k - 1)(n - k)*(n - k + 1)^(n - k).

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 0, 18, 6, 0, 0, 192, 72, 48, 0, 0, 2500, 960, 720, 540, 0, 0, 38880, 15000, 11520, 9720, 7680, 0, 0, 705894, 272160, 210000, 181440, 161280, 131250, 0, 0, 14680064, 5647152, 4354560, 3780000, 3440640, 3150000, 2612736, 0

Offset: 0

Peter Luschny, Jan 11 2024

A motivation for this triangle was to provide an alternative sum representation for A001864(n) = n! * Sum_{k=0..n-2} n^k/k!. See formula 3 and formula 15 in Riordan and Sloane.

			Triangle starts:
  [0] [0]
  [1] [0,        0]
  [2] [0,        2,       0]
  [3] [0,       18,       6,       0]
  [4] [0,      192,      72,      48,      0]
  [5] [0,     2500,     960,     720,     540,       0]
  [6] [0,    38880,   15000,   11520,    9720,    7680,       0]
  [7] [0,   705894,  272160,  210000,  181440,  161280,  131250,       0]
  [8] [0, 14680064, 5647152, 4354560, 3780000, 3440640, 3150000, 2612736, 0]

John Riordan and N. J. A. Sloane, Enumeration of rooted trees by total height, J. Austral. Math. Soc., vol. 10 pp. 278-282, 1969.

T(n, 1) = A066274(n) for n >= 1.
T(n, 1)/(n - 1) = A000169(n) for n >= 2.
T(n, n - 1) = 2*A081133(n) for n >= 1.
Sum_{k=0..n} T(n, k) = A001864(n).
(Sum_{k=0..n} T(n, k)) / n = A000435(n) for n >= 1.
(Sum_{k=0..n} T(n, k)) * n / 2 = A262973(n) for n >= 1.
(Sum_{k=2..n} T(n, k)) / (2*n) = A057500(n) for n >= 1.
T(n, 1)/(n - 1) + (Sum_{k=2..n} T(n, k)) / (2*n) = A368951(n) for n >= 2.
Sum_{k=0..n} (-1)^(k-1) * T(n, k) = A368981(n).

A368849[n_, k_] := Binomial[n, k-1] If[k == 1, 1, (k-1)^(k-1)] (n-k) (n-k+1)^(n-k);
Table[A368849[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, Jan 13 2024 *)

def T(n, k):
    return binomial(n, k - 1)*(k - 1)^(k - 1)*(n - k)*(n - k + 1)^(n - k)
for n in range(0, 9): print([n], [T(n, k) for k in range(n + 1)])

A061540 Number of connected labeled graphs with n nodes and n+1 edges.

Original entry on oeis.org

0, 0, 0, 6, 205, 5700, 156555, 4483360, 136368414, 4432075200, 154060613850, 5720327205120, 226378594906035, 9523895202838016, 424814409531910125, 20037831121798963200, 996964614369038858060, 52198565072252054814720, 2869621989939313379211204, 165302832533722012508160000

Offset: 1

RAVELOMANANA Vlady (vlad(AT)lri.fr), May 16 2001

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 407, Eq. (6.5).

Sergey Serebryakov, Table of n, a(n) for n = 1..40
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
E. M. Wright, The Number of Connected Sparsely Edged Graphs, Journal of Graph Theory Vol. 1 (1977), 317-330.

A diagonal of A343088.

Cf. A000169, A000272, A057500, A061541, A061542, A061543, A096117, A061544, A096150, A096224.

A001864 := proc(n)
    add(binomial(n,s)*s^s*(n-s)^(n-s),s=1..n-1) ;
end proc:
A061540 := proc(n)
    (n-1)*(5*n^2+3*n+2)*n^(n-2)-14*A001864(n) ;
    %/24 ;
end proc: # R. J. Mathar, May 10 2016 see Chapter 6.3 in Bona's Handbook of Combinatorics

max = 18; t[x_] := -ProductLog[-x]; w1[x_] := t[x]^4/24*(6-t[x])/(1-t[x])^3; Drop[ CoefficientList[ Series[ w1[x], {x, 0, max}], x]*Range[0, max]!, 1] (* Jean-François Alcover, Apr 02 2012, after e.g.f. *)

from math import comb
def A061540(n): return 0 if n<2 else ((n*(n*(5*n - 2) - 1) - 2)*n**(n-2)-14*((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)))//24 # Chai Wah Wu, Apr 26 2023

E.g.f.: W1(x) := T(x)^4/24 * (6-T(x))/(1-T(x))^3 where T(x) is the e.g.f. for rooted labeled trees (A000169), i.e. T(x) = -LambertW(-x) = x*exp(T(x)).

a(n) ~ 5*n^(n+1)/24 * (1 - 7/5*sqrt(2*Pi/n)). - Vaclav Kotesovec, Jul 09 2013

A216971 Triangle read by rows: T(n,k) is the number of functions f:{1,2,...,n}->{1,2,...,n} that have exactly k nonrecurrent elements mapped to some (one or more) recurrent element. n >= 1, 0 <= k <= n-1.

Original entry on oeis.org

1, 2, 2, 6, 18, 3, 24, 156, 72, 4, 120, 1520, 1260, 220, 5, 720, 17310, 21000, 7020, 600, 6, 5040, 232932, 363720, 187320, 32970, 1554, 7, 40320, 3698744, 6794256, 4746840, 1351840, 141288, 3920, 8, 362880, 68680656, 139241088, 121105152, 48822480, 8625456, 573048, 9720, 9, 3628800, 1471193370

Offset: 1

Geoffrey Critzer, Sep 21 2012

x in {1,2,...,n} is a recurrent element if there is some k such that f^k(x) = x where f^k(x) denotes iterated functional composition. In other words, a recurrent element is in a cycle of the functional digraph.
Row sums = n^n.
First column (k = 0) counts the n! bijective functions.
T(n,n-1) counts the n constant functions.
Conjecture: every entry in row n is divisible by n. - Jon Perry, Sep 21 2012

			Triangle starts:
     1,
     2,      2,
     6,     18,      3,
    24,    156,     72,      4,
   120,   1520,   1260,    220,      5,
   720,  17310,  21000,   7020,    600,      6,
  5040, 232932, 363720, 187320,  32970,   1554,      7,
  ...

Joerg Arndt, Table of n, a(n) for n = 1..528

Cf. A001864.

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

N=15; x='x+O('x^N);
T=serreverse(x*exp(-x));
egf=1/(1-x*exp('y*T)) - 1;
v=Vec(serlaplace(egf));
{ for (n=1, N-1, /* print triangle: */
    row = Pol( v[n], 'y );
    row = polrecip( row );
    print( Vec(row) );
); }
/* Joerg Arndt, Sep 21 2012 */

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

Sum_{k=1..n-1} k * T(n,k) = A001864(n). - Geoffrey Critzer, Jan 01 2013

A369016 Triangle read by rows: T(n, k) = binomial(n - 1, k - 1) * (k - 1)^(k - 1) * (n - k) * (n - k + 1)^(n - k - 1).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 6, 2, 0, 0, 48, 18, 12, 0, 0, 500, 192, 144, 108, 0, 0, 6480, 2500, 1920, 1620, 1280, 0, 0, 100842, 38880, 30000, 25920, 23040, 18750, 0, 0, 1835008, 705894, 544320, 472500, 430080, 393750, 326592, 0

Offset: 0

Peter Luschny, Jan 12 2024

			Triangle starts:
  [0] [0]
  [1] [0,       0]
  [2] [0,       1,      0]
  [3] [0,       6,      2,      0]
  [4] [0,      48,     18,     12,      0]
  [5] [0,     500,    192,    144,    108,      0]
  [6] [0,    6480,   2500,   1920,   1620,   1280,      0]
  [7] [0,  100842,  38880,  30000,  25920,  23040,  18750,      0]
  [8] [0, 1835008, 705894, 544320, 472500, 430080, 393750, 326592, 0]

A368849, A368982 and this sequence are alternative sum representation for A001864 with different normalizations.
T(n, k) = A368849(n, k) / n for n >= 1.
T(n, 1) = A053506(n) for n >= 1.
T(n, n - 1) = A055897(n - 1) for n >= 2.
Sum_{k=0..n} T(n, k) = A000435(n) for n >= 1.
Sum_{k=0..n} (-1)^(k+1)*T(n, k) = A368981(n) / n for n >= 1.
Cf. A066320, A369017.

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

A369016[n_, k_] := Binomial[n-1, k-1] If[k == 1, 1, (k-1)^(k-1)] (n-k) (n-k+1)^(n-k-1); Table[A369016[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, Jan 28 2024 *)

def T(n, k): return binomial(n-1, k-1)*(k-1)^(k-1)*(n-k)*(n-k+1)^(n-k-1)
for n in range(0, 9): print([T(n, k) for k in range(n + 1)])

T = B066320 - A369017 (where B066320 = A066320 after adding a 0-column to the left and then setting offset to (0, 0)).

A368982 Triangle read by rows: T(n, k) = binomial(n, k - 1) * (k - 1)^(k - 1) * (n - k) * (n - k + 1)^(n - k) / 2.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 9, 3, 0, 0, 96, 36, 24, 0, 0, 1250, 480, 360, 270, 0, 0, 19440, 7500, 5760, 4860, 3840, 0, 0, 352947, 136080, 105000, 90720, 80640, 65625, 0, 0, 7340032, 2823576, 2177280, 1890000, 1720320, 1575000, 1306368, 0

Offset: 0

Peter Luschny, Jan 11 2024

			Triangle starts:
  [0] [0]
  [1] [0,       0]
  [2] [0,       1,       0]
  [3] [0,       9,       3,       0]
  [4] [0,      96,      36,      24,       0]
  [5] [0,    1250,     480,     360,     270,       0]
  [6] [0,   19440,    7500,    5760,    4860,    3840,       0]
  [7] [0,  352947,  136080,  105000,   90720,   80640,   65625,       0]
  [8] [0, 7340032, 2823576, 2177280, 1890000, 1720320, 1575000, 1306368, 0]

A368849, A369016 and this sequence are alternative sum representation for A001864 with different normalizations.
T(n, k) = A368849(n, k) / 2.
T(n, 1) = A081131(n) for n >= 1.
T(n, n - 1) = A081133(n - 2) for n >= 2.
Sum_{k=0..n} T(n, k) = A036276(n - 1) for n >= 1.
Sum_{k=0..n} (-1)^(k+1)*T(n, k) = A368981(n) / 2 for n >= 0.
Cf. A369072, A369025.

T := (n, k) -> binomial(n, k-1)*(k-1)^(k-1)*(n-k)*(n-k+1)^(n-k)/2:
seq(seq(T(n, k), k = 0..n), n=0..9);

A368982[n_, k_] := Binomial[n, k-1] If[k == 1, 1, (k-1)^(k-1)] (n-k) (n-k+1)^(n-k)/2; Table[A368982[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, Jan 28 2024 *)

def T(n, k): return binomial(n, k-1)*(k-1)^(k-1)*(n-k)*(n-k+1)^(n-k)//2
for n in range(0, 9): print([T(n, k) for k in range(n + 1)])

T = A369072 - A369025.

A177453 Partial sums of A001863.

Original entry on oeis.org

0, 1, 5, 31, 267, 3027, 42599, 715191, 13942995, 309522515, 7707841015, 212783127799, 6449579387715, 212939326904131, 7606688596589431, 292321288041079671, 12025358303201356019, 527265684696785414387

Offset: 1

Jonathan Vos Post, May 09 2010

nonn

Partial sums of normalized total height of rooted trees with n nodes. The subsequence of primes in the partial sums begins: 5, 31, no more through a(15).

			a(5) = 0 + 1 + 4 + 26 + 236 = 267 = 3 * 89.

Cf. A000435, A001864, A001863.

A001863 := proc(n) if n = 1 then 0; else add( (n-2)!*n^k/k!,k=0..n-2) ; end if; end proc:
A177453 := proc(n) add(A001863(i),i=0..n) ; end proc: seq(A177453(n),n=1..20) ; # R. J. Mathar, May 28 2010

Accumulate[Table[Sum[(n-2)! n^k/k!,{k,0,n-2}],{n,20}]] (* Harvey P. Dale, Jun 19 2016 *)

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

a(n) = Sum_{i=1..n} A001863(i).

Extended by R. J. Mathar, May 28 2010

Showing 1-10 of 11 results. Next

cp's OEIS Frontend

A036276 a(n) = A001864(n+1)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

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

A001863 Normalized total height of rooted trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A066324 Number of endofunctions on n labeled points constructed from k rooted trees.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A368849 Triangle read by rows: T(n, k) = binomial(n, k - 1)*(k - 1)^(k - 1)*(n - k)*(n - k + 1)^(n - k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

SageMath

A061540 Number of connected labeled graphs with n nodes and n+1 edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

A368849 Triangle read by rows: T(n, k) = binomial(n, k - 1)(k - 1)^(k - 1)(n - k)*(n - k + 1)^(n - k).