Displaying 1-10 of 25 results found.
Essentially A053506 but with leading 0 (instead of 1) and offset 0.
+20
2
0, 0, 6, 48, 500, 6480, 100842, 1835008, 38263752, 900000000, 23579476910, 681091006464, 21505924728444, 737020860878848, 27246730957031250, 1080863910568919040, 45798768824157052688, 2064472028642102280192
FORMULA
a(0) = 0 = a(1); a(n) = n*(n+1)^(n-1), n >= 2.
E.g.f.: -x + W(-x)^2/((1+W(-x))*x) = ((d/dx)W(-x)^2)/2-x, W(x) principal branch of Lambert's function.
Number of labeled rooted trees with n nodes: n^(n-1).
(Formerly M1946 N0771)
+10
376
1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000, 25937424601, 743008370688, 23298085122481, 793714773254144, 29192926025390625, 1152921504606846976, 48661191875666868481, 2185911559738696531968, 104127350297911241532841, 5242880000000000000000000
COMMENTS
Also the number of connected transitive subtree acyclic digraphs on n vertices. - Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001
For any given integer k, a(n) is also the number of functions from {1,2,...,n} to {1,2,...,n} such that the sum of the function values is k mod n. - Sharon Sela (sharonsela(AT)hotmail.com), Feb 16 2002
The n-th term of a geometric progression with first term 1 and common ratio n: a(1) = 1 -> 1,1,1,1,... a(2) = 2 -> 1,2,... a(3) = 9 -> 1,3,9,... a(4) = 64 -> 1,4,16,64,... - Amarnath Murthy, Mar 25 2004 In other words, if A is a finite set of size n-1, then a(n) is the number of binary relations on A that are also functions. Note that a(n) = Sum_{k=0..n-1} binomial(n-1,k)*(n-1)^k = n^(n-1), where binomial(n-1,k) is the number of ways to select a domain D of size k from A and (n-1)^k is the number of functions from D to A. - Dennis P. Walsh, Apr 21 2011 More generally, consider the class of sequences of the form a(n) = (n*c(1)*...*c(i))^(n-1). This sequence has c(1)=1. A052746 has a(n) = (2*n)^(n-1), A052756 has a(n) = (3*n)^(n-1), A052764 has a(n) = (4*n)^(n-1), A052789 has a(n) = (5*n)^(n-1) for n>0. These sequences have a combinatorial structure like simple grammars. - Ctibor O. Zizka, Feb 23 2008 a(n) is equal to the logarithmic transform of the sequence b(n) = n^(n-2) starting at b(2). - Kevin Hu (10thsymphony(AT)gmail.com), Aug 23 2010
Also, number of labeled connected multigraphs of order n without cycles except one loop. See link below to have a picture showing the bijection between rooted trees and multigraphs of this kind. (Note that there are no labels in the picture, but the bijection remains true if we label the nodes.) - Washington Bomfim, Sep 04 2010 a(n) is also the number of functions f:{1,2,...,n} -> {1,2,...,n} such that f(1) = 1.
For a signed version of A000169 arising from the Vandermonde determinant of (1,1/2,...,1/n), see the Mathematica section. - Clark Kimberling, Jan 02 2012 a(n+1) is the number of n x n binary matrices with no more than a single one in each row. Partitioning the set of such matrices by the number k of rows with a one, we obtain a(n+1) = Sum_{k=0..n} binomial(n,k)*n^k = (n+1)^n. - Dennis P. Walsh, May 27 2014 a(n) is the row sum of the n-th rows of A248120 and A055302, so it enumerates the monomials in the expansion of [x(1) + x(2) + ... + x(n)]^(n-1). - Tom Copeland, Jul 17 2015 For any given integer k, a(n) is the number of sums x_1 + ... + x_m = k (mod n) such that: x_1, ..., x_m are nonnegative integers less than n, the order of the summands does not matter, and each integer appears fewer than n times as a summand. - Carlo Sanna, Oct 04 2015 a(n) is the number of words of length n-1 over an alphabet of n letters. - Joerg Arndt, Oct 07 2015 a(n) is the number of parking functions whose largest element is n and length is n. For example, a(3) = 9 because there are nine such parking functions, namely (1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,1,2), (3,2,1), (1,1,3), (1,3,1), (3,1,1). - Ran Pan, Nov 15 2015 Consider the following problem: n^2 cells are arranged in a square array. A step can be defined as going from one cell to the one directly above it, to the right of it or under it. A step above cannot be followed by a step below and vice versa. Once the last column of the square array is reached, you can only take steps down. a(n) is the number of possible paths (i.e., sequences of steps) from the cell on the bottom left to the cell on the bottom right. - Nicolas Nagel, Oct 13 2016 The rationals c(n) = a(n+1)/a(n), n >= 1, appear in the proof of G. Pólya's "elementary, but not too elementary, theorem": Sum_{n>=1} (Product_{k=1..n} a_k)^(1/n) < exp(1)*Sum_{n>=1} a_n, for n >= 1, with the sequence {a_k}_{k>=1} of nonnegative terms, not all equal to 0. - Wolfdieter Lang, Mar 16 2018 Coefficients of the generating series for the preLie operadic algebra. Cf. p. 417 of the Loday et al. paper. - Tom Copeland, Jul 08 2018 a(n)/2^(n-1) is the square of the determinant of the n X n matrix M_n with elements m(j,k) = cos(Pi*j*k/n). See Zhi-Wei Sun, Petrov link. - Hugo Pfoertner, Sep 19 2021 a(n) is the determinant of the n X n matrix P_n such that, when indexed [0, n), P(0, j) = 1, P(i <= j) = i, and P(i > j) = i-n. - C.S. Elder, Mar 11 2024
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 169.
Jonathan L. Gross and Jay Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.
Hannes Heikinheimo, Heikki Mannila and Jouni K. Seppnen, Finding Trees from Unordered 01 Data, in Knowledge Discovery in Databases: PKDD 2006, Lecture Notes in Computer Science, Volume 4213/2006, Springer-Verlag. - N. J. A. Sloane, Jul 09 2009 Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 63.
John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.
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).
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 25, Prop. 5.3.2, and p. 37, (5.52).
LINKS
G. Pólya, With, or Without, Motivation?, Amer. Math. Monthly, Vol. 56, No. 10 (1949), pp. 684-691. Reprinted in "A Century of Mathematics", John Ewing (ed.), Math. Assoc. of Amer., 1994, pp. 195-200 (the reference there is wrong).
FORMULA
The e.g.f. T(x) = Sum_{n>=1} n^(n-1)*x^n/n! satisfies T(x) = x*exp(T(x)), so T(x) is the functional inverse (series reversion) of x*exp(-x).
Also T(x) = -LambertW(-x) where W(x) is the principal branch of Lambert's function.
T(x) is sometimes called Euler's tree function.
E.g.f.: LambertW(x)=x*G(0); G(k) = 1 - x*((2*k+2)^(2*k))/(((2*k+1)^(2*k)) - x*((2*k+1)^(2*k))*((2*k+3)^(2*k+1))/(x*((2*k+3)^(2*k+1)) - ((2*k+2)^(2*k+1))/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 30 2011 a(n) = Sum_{i=1..n} binomial(n-1,i-1)*i^(i-2)*(n-i)^(n-i). - Dmitry Kruchinin, Oct 28 2013 Sum_{n>=1} (-1)^(n+1)/a(n) = A262974. (End) a(n) = Sum_{k=0..n-1} (-1)^(n+k-1)*Pochhammer(n, k)*Stirling2(n-1, k). - Mélika Tebni, May 07 2023 In terms of Eulerian numbers A340556(n,k) of the second order Sum_{m>=1} m^(m+n) z^m/m! = 1/(1-T(z))^(2n+1) * Sum_{k=0..n} A2(n,k) T(z)^k. - Marko Riedel, Jan 10 2024
EXAMPLE
For n=3, a(3)=9 because there are exactly 9 binary relations on A={1, 2} that are functions, namely: {}, {(1,1)}, {(1,2)}, {(2,1)}, {(2,2)}, {(1,1),(2,1)}, {(1,1),(2,2)}, {(1,2),(2,1)} and {(1,2),(2,2)}. - Dennis P. Walsh, Apr 21 2011 G.f. = x + 2*x^2 + 9*x^3 + 64*x^4 + 625*x^5 + 7776*x^6 + 117649*x^7 + ...
MAPLE
# second program:
spec := [A, {A=Prod(Z, Set(A))}, labeled]; [seq(combstruct[count](spec, size=n), n=1..20)];
# third program:
A000169 := n -> add((-1)^(n+k-1)*pochhammer(n, k)*Stirling2(n-1, k), k = 0..n-1):
MATHEMATICA
(* Next, a signed version A000169 from the Vandermonde determinant of (1, 1/2, ..., 1/n) *) f[j_] := 1/j; z = 12;
v[n_] := Product[Product[f[k] - f[j], {j, 1, k - 1}], {k, 2, n}]
Table[v[n], {n, 1, z}]
Table[v[n]/v[n + 1], {n, 1, z - 1}] (* A000169 signed *) a[n_]:=Det[Table[If[i==0, 1, If[i<=j, i, i-n]], {i, 0, n-1}, {j, 0, n-1}]]; Array[a, 20] (* Stefano Spezia, Mar 12 2024 *)
PROG
(PARI) a(n) = n^(n-1)
(Python)
def a(n): return n**(n-1)
(Python)
from sympy import Matrix
def P(n): return [[ (i-n if i > j else i) + (i == 0) for j in range(n) ] for i in range(n)]
print(*(Matrix(P(n)).det() for n in range(1, 21)), sep=', ') # C.S. Elder, Mar 12 2024
CROSSREFS
Cf. A000055, A000081, A000272, A000312, A007778, A007830, A008785- A008791, A055860, A002061, A052746, A052756, A052764, A052789, A051129, A098686, A247363, A055302, A248120, A130293, A053506- A053509, A262974.
a(1) = 1; for n > 1, smallest digitally balanced number in base n.
+10
23
1, 2, 11, 75, 694, 8345, 123717, 2177399, 44317196, 1023456789, 26432593615, 754777787027, 23609224079778, 802772380556705, 29480883458974409, 1162849439785405935, 49030176097150555672, 2200618769387072998445, 104753196945250864004691, 5271200265927977839335179
FORMULA
a(n) = (102345....n-1) in base n. - Ulrich Schimke (ulrschimke(AT)aol.com)
EXAMPLE
a(6) = 102345_6 = 1*6^5 + 2*6^3 + 3*6^2 + 4*6^1 + 5*6^0 = 8345.
MAPLE
a:= n-> n^(n-1)+add((n-i)*n^(i-1), i=1..n-2):
MATHEMATICA
Table[FromDigits[Join[{1, 0}, Range[2, n-1]], n], {n, 20}] (* Harvey P. Dale, Oct 12 2012 *)
PROG
(Haskell)
a049363 n = foldl (\v d -> n * v + d) 0 (1 : 0 : [2..n-1])
(Python)
def A049363(n): return (n**n-n)//(n-1)**2+n**(n-2)*(n-1)-1 if n>1 else 1 # Chai Wah Wu, Mar 13 2024
EXTENSIONS
More terms from Ulrich Schimke (ulrschimke(AT)aol.com)
a(n) = binomial(n-1,2)*n^(n-3).
+10
15
0, 0, 1, 12, 150, 2160, 36015, 688128, 14880348, 360000000, 9646149645, 283787919360, 9098660462034, 315866083233792, 11806916748046875, 472877960873902080, 20205339187128111480, 917543123840934346752, 44131536275846038655193
COMMENTS
Number of connected unicyclic simple graphs on n labeled nodes such that the unique cycle has length 3. - Len Smiley, Nov 27 2001 Each simple graph (of this type) corresponds to exactly two 'functional digraphs' counted by A065513.
REFERENCES
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Prop. 5.3.2.
MATHEMATICA
Range[0, nn]! CoefficientList[Series[t^3/3!, {x, 0, nn}], x], 1] (* Geoffrey Critzer, Jan 22 2012 *) Table[Binomial[n-1, 2]n^(n-3), {n, 20}] (* Harvey P. Dale, Sep 24 2019 *)
PROG
(PARI) vector(20, n, binomial(n-1, 2)*n^(n-3)) \\ G. C. Greubel, Jan 18 2017 (Magma) [Binomial(n-1, 2)*n^(n-3): n in [1..20]]; // G. C. Greubel, May 15 2019 (Sage) [binomial(n-1, 2)*n^(n-3) for n in (1..20)] # G. C. Greubel, May 15 2019 (GAP) List([1..20], n-> Binomial(n-1, 2)*n^(n-3)) # G. C. Greubel, May 15 2019
Triangle read by rows: T(n, k) is the number of labeled trees on n nodes with maximal node degree k (0 < k < n).
+10
14
1, 2, 1, 9, 6, 1, 64, 48, 12, 1, 625, 500, 150, 20, 1, 7776, 6480, 2160, 360, 30, 1, 117649, 100842, 36015, 6860, 735, 42, 1, 2097152, 1835008, 688128, 143360, 17920, 1344, 56, 1, 43046721, 38263752, 14880348, 3306744, 459270, 40824, 2268, 72, 1
COMMENTS
This is a formula from Comtet, Theorem F, vol. I, p. 81 (French edition) used in proving Theorem D.
If we let N = n+1, binomial(N-2, k-1)*(N-1)^(N-k-1) = binomial(n-1, k-1)*n^(n-k), so this sequence with offset 1,1 also gives the number of rooted forests of k trees over [n]. - Washington Bomfim, Jan 09 2008 Let S(n,k) be the signed triangle, S(n,k) = (-1)^(n-k)T(n,k), which starts 1, -2, 1, 9, -6, 1, ..., then the inverse of S is the triangle of idempotent numbers A059298. - Peter Luschny, Mar 13 2009 With offset 1 also number of labeled multigraphs of k components, n nodes, and no cycles except one loop in each component. See link below to have a picture showing the bijection between rooted forests and multigraphs of this kind. (Note that there are no labels in the picture, but the bijection remains true if we label the nodes.) - Washington Bomfim, Sep 04 2010 With offset 1, T(n,k) is the number of forests of rooted trees on n nodes with exactly k (rooted) trees. - Geoffrey Critzer, Feb 10 2012 Also the Bell transform of the sequence (n+1)^n ( A000169(n+1)) without column 0. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 21 2016 Abel polynomials A(n,x) = x*(x+n)^(n-1) satisfy d/dx A(n,x) = n*A(n-1,x+1). - Michael Somos, May 10 2024
REFERENCES
L. Comtet, Analyse Combinatoire, P.U.F., Paris 1970. Volume 1, p 81.
L. Comtet, Advanced Combinatorics, Reidel, 1974.
LINKS
Jim Pitman, Coalescent Random Forests, Journal of Combinatorial Theory, Series A, Volume 85, Issue 2, February 1999, Pages 165-193.
FORMULA
T(n, k) = binomial(n-2, k-1)*(n-1)^(n-k-1).
Let T(x) = Sum_{n >= 0} n^(n-1)*x^n/n! denote the tree function of A000169. E.g.f.: F(x,t) := exp(t*T(x)) - 1 = -1 + {T(x)/x}^t = t*x + t*(2 + t)*x^2/2! + t*(9 + 6*t + t^2)*x^3/3! + .... The compositional inverse with respect to x of (1/t)*F(x,t) is the e.g.f. for a signed version of the row reverse of A028421. The row generating polynomials are the Abel polynomials A(n,x) = x*(x+n)^(n-1) for n >= 1.
Define B(n,x) = x^n/(1+n*x)^(n+1) = (-1)^n*A(-n,-1/x) for n >= 1. The k-th column entries are the coefficients in the formal series expansion of x^k in terms of B(n,x). For example, Col. 1: x = B(1,x) + 2*B(2,x) + 9*B(3,x) + 64*B(4,x) + ..., Col. 2: x^2 = B(2,x) + 6*B(3,x) + 48*B(4,x) + 500*B(5,x) + ... Compare with A059297. The o.g.f.'s for the diagonals of the triangle are the rational functions R(n,x)/(1-x)^(2*n+1), where R(n,x) are the row polynomials of A155163. See below for examples. (End)
T(n,m) = C(n,m)*Sum_{k=1..n-m} m^k*T(n-m,k), T(n,n) = 1. - Vladimir Kruchinin, Mar 31 2015
EXAMPLE
: 1;
: 2, 1;
: 9, 6, 1;
: 64, 48, 12, 1;
: 625, 500, 150, 20, 1;
: 7776, 6480, 2160, 360, 30, 1;
...
O.g.f.'s for the diagonals begin:
1/(1-x) = 1 + x + x^2 + x^3 + ...
2*x/(1-x)^3 = 2 + 6*x + 12*x^3 + ... A002378(n+1) (9+3*x)/(1-x)^5 = 9 + 48*x + 150*x^2 + ... 3* A004320(n+1) The numerator polynomials are the row polynomials of A155163. (End)
MAPLE
# The function BellMatrix is defined in A264428. # Adds (1, 0, 0, 0, ...) as column 0 to the triangle.
MATHEMATICA
nn = 7; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; f[list_] := Select[list, # > 0 &]; Map[f, Drop[Range[0, nn]! CoefficientList[Series[Exp[y t], {x, 0, nn}], {x, y}], 1]] // Flatten (* Geoffrey Critzer, Feb 10 2012 *) T[n_, m_] := T[n, m] = Binomial[n, m]*Sum[m^k*T[n-m, k], {k, 1, n-m}]; T[n_, n_] = 1; Table[T[n, m], {n, 1, 9}, {m, 1, n}] // Flatten (* Jean-François Alcover, Mar 31 2015, after Vladimir Kruchinin *) Table[Binomial[n - 2, k - 1]*(n - 1)^(n - k - 1), {n, 2, 12}, {k, 1, n - 1}] // Flatten (* G. C. Greubel, Nov 12 2017 *) BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len-1}, {k, 0, len-1}]];
rows = 10;
M = BellMatrix[(# + 1)^#&, rows];
PROG
(Maxima) create_list(binomial(n, k)*(n+1)^(n-k), n, 0, 20, k, 0, n); /* Emanuele Munarini, Apr 01 2014 */ (Sage) # uses[bell_matrix from A264428] # Adds (1, 0, 0, 0, ...) as column 0 to the triangle.
(PARI) for(n=2, 11, for(k=1, n-1, print1(binomial(n-2, k-1)*(n-1)^(n-k-1), ", "))) \\ G. C. Greubel, Nov 12 2017
Number of connected labeled graphs with n edges and n vertices and with loops allowed.
+10
13
1, 1, 2, 10, 79, 847, 11436, 185944, 3533720, 76826061, 1880107840, 51139278646, 1530376944768, 49965900317755, 1767387701671424, 67325805434672100, 2747849045156064256, 119626103584870552921, 5533218319763109888000, 270982462739224265922466
LINKS
Eric Weisstein's World of Mathematics, Graph Loop.
FORMULA
E.g.f.: 1 - log(1-T(x))/2 + T(x)/2 - T(x)^2/4 where T(x) = -LambertW(-x) is the e.g.f. of A000169. a(n) = (exp(n)*Gamma(n + 1, n) - (n - 1)*n^(n - 1))/(2*n) for n > 0.
EXAMPLE
The a(0) = 1 through a(3) = 10 loop-graphs:
{} {11} {11,12} {11,12,13}
{22,12} {11,12,23}
{11,13,23}
{22,12,13}
{22,12,23}
{22,13,23}
{33,12,13}
{33,12,23}
{33,13,23}
{12,13,23}
(End)
MAPLE
egf:= (L-> 1-L/2-log(1+L)/2-L^2/4)(LambertW(-x)):
a:= n-> n!*coeff(series(egf, x, n+1), x, n):
PROG
(PARI) seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(-log(1-t)/2 + t/2 - t^2/4 + 1))}
CROSSREFS
This is the connected covering case of A014068. Allowing any number of edges gives A062740, connected case of A322661. This is the connected case of A368597. For at most n edges we have A369197. A000085 counts set partitions into singletons or pairs.
Coefficient triangle for certain polynomials.
+10
11
1, 1, 2, 4, 9, 6, 27, 64, 48, 36, 256, 625, 500, 400, 320, 3125, 7776, 6480, 5400, 4500, 3750, 46656, 117649, 100842, 86436, 74088, 63504, 54432, 823543, 2097152, 1835008, 1605632, 1404928, 1229312, 1075648, 941192, 16777216, 43046721
COMMENTS
The coefficients of the partner polynomials are found in triangle A055864.
FORMULA
a(n, m)=0 if n < m; a(0, 0)=1, a(n, 0) = n^n, n >= 1, a(n, m) = n^(m-1)*(n+1)^(n-m+1), n >= m >= 1;
E.g.f. for column m: A(m, x); A(0, x) = 1/(1+W(-x)); A(1, x) = -1 - (d/dx)W(-x) = -1-W(-x)/((1+W(-x))*x); A(2, x) = A(1, x)-int(A(1, x), x)/x-(1/x+x); recursion: A(m, x) = A(m-1, x)-int(A(m-1, x), x)/x-((m-1)^(m-1))*(x^(m-1))/(m-1)!, m >= 3; W(x) principal branch of Lambert's function.
EXAMPLE
{1}; {1,2}; {4,9,6}; {27,64,48,36}; ...
Fourth row polynomial (n=3): p(3,x) = 27 + 64*x + 48*x^2 + 36*x^3.
MATHEMATICA
a[n_, m_] /; n < m = 0; a[0, 0] = 1; a[n_, 0] := n^n; a[n_, m_] := n^(m-1)*(n+1)^(n-m+1); Table[a[n, m], {n, 0, 8}, {m, 0, n}] // Flatten (* Jean-François Alcover, Jun 20 2013 *)
Birooted graphs: number of unlabeled connected graphs with n nodes rooted at 2 indistinguishable roots.
+10
10
0, 1, 3, 16, 98, 879, 11260, 230505, 7949596, 483572280, 53011686200, 10589943940654, 3880959679322754, 2623201177625659987, 3286005731275218388682, 7663042204550840483139108, 33407704152242477510352455230, 273327599183687887638526170380380
MATHEMATICA
(* See the links section. *)
Expansion of Sum_{n>=0} n^n*x^n/(1 - n*x)^n.
+10
9
1, 1, 5, 44, 548, 8808, 173352, 4036288, 108507968, 3307368320, 112703108480, 4245680193024, 175200825481728, 7859411394860032, 380810598813553664, 19819617775693512704, 1102737068471914938368, 65316500202537025634304, 4103422475123595857854464
COMMENTS
Compare g.f. to the identity (cf. A001710): Sum_{n>=0} n^n*x^n/(1 + n*x)^n = 1 + (1/2)*Sum_{n>=1} (n+1)!*x^n.
FORMULA
a(n) = Sum_{k=0..n} C(n-1,k)*(k+1)^n.
a(n) = (n+1)!/2 + 2*Sum_{k=0..[n/2]} C(n-1,n-2*k)*(n-2*k+1)^n for n>0 with a(0)=1.
a(n) ~ n^n * r^(n+3/2) / (exp(n) * (1-r)^n), where r = 1/(1+LambertW(exp(-1))) = 0.78218829428019990122... . - Vaclav Kotesovec, May 14 2014
EXAMPLE
G.f.: A(x) = 1 + x + 5*x^2 + 44*x^3 + 548*x^4 + 8808*x^5 + 173352*x^6 +...
where
A(x) = 1 + x/(1-x) + 2^2*x^2/(1-2*x)^2 + 3^3*x^3/(1-3*x)^3 + 4^4*x^4/(1-4*x)^4 +...
MATHEMATICA
a[n_] := Sum[Binomial[n - 1, k] (k + 1)^n, {k, 0, n}];
PROG
(PARI) {a(n)=polcoeff(sum(m=0, n, m^m*x^m/(1-m*x+x*O(x^n))^m), n)}
(PARI) {a(n)=sum(k=0, n, binomial(n-1, k)*(k+1)^n)}
(PARI) {a(n)=(n+1)!/2 + 2*sum(k=0, n\2, binomial(n-1, n-2*k)*(n-2*k+1)^n)}
Number of forests with two connected components in the complete graph K_{n}.
+10
7
0, 1, 3, 15, 110, 1080, 13377, 200704, 3542940, 72000000, 1656409535, 42568187904, 1208912928522, 37603105146880, 1271514111328125, 46443371157258240, 1822442358054692408, 76461926986744528896, 3415753581721829617275
COMMENTS
Note that the above sequence is dominated by the sequence n^{n-2} (n > 0), A000272, which enumerates the number of spanning trees in K_{n} : 1, 1, 3, 16, 125, 1296, 16807, 262144, ... This is a consequence of the result in [EKT] which shows that the sequence of independent set numbers of cycle matroid of K_{n} is (strictly) monotone increasing (when n > 3).
REFERENCES
W. Kook, Categories of acyclic graphs and automorphisms of free groups, Ph.D. thesis (G. Carlsson, advisor), Stanford University, 1996.
FORMULA
E.g.f.: T(x)^{2}/2!, where T(x) is the e.g.f. for the number of spanning trees in K_{n}, i.e., T(x) = Sum_{i>=1} i^(i-2)*x^i/i!.
E.g.f.: (1/8)*LambertW(-x)^2*(2+LambertW(-x))^2. - Vladeta Jovovic, Jul 08 2003
MAPLE
f:=n->(n-1)!*n^(n-4)*(n+6)/(2*(n-2)!); [seq(f(n), n=2..30)]; # N. J. A. Sloane, Apr 09 2014
MATHEMATICA
(* first 20 terms starting with n=1 *) T := Sum[i^(i - 2)*(x^i)/i!, {i, 1, 20}]; T2 := Expand[(T^{2})/2! ]; C2[i_] := Coefficient[T2, x^{i}]*i!; M := MatrixForm[Table[C2[i], {i, 20}]]; M
PROG
(PARI) for(n=1, 30, print1(n^(n-4)*(n-1)*(n+6)/2, ", ")) \\ G. C. Greubel, Nov 14 2017
AUTHOR
Woong Kook (andrewk(AT)math.uri.edu), Jun 08 2003
Search completed in 0.018 seconds
| 
