cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-7 of 7 results.

A000169 Number of labeled rooted trees with n nodes: n^(n-1).

Original entry on oeis.org

1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000, 25937424601, 743008370688, 23298085122481, 793714773254144, 29192926025390625, 1152921504606846976, 48661191875666868481, 2185911559738696531968, 104127350297911241532841, 5242880000000000000000000
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Also the number of connected transitive subtree acyclic digraphs on n vertices. - Robert Castelo, 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
All rational solutions to the equation x^y = y^x, with x < y, are given by x = A000169(n+1)/A000312(n), y = A000312(n+1)/A007778(n), where n = 1, 2, 3, ... . - Nick Hobson, Nov 30 2006
a(n+1) is also the number of partial functions on n labeled objects. - Franklin T. Adams-Watters, Dec 25 2006
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
This is the fourth member of a set of which the other members are the symmetric group, full transformation semigroup, and symmetric inverse semigroup. For the first three, see A000142, A000312, A002720. - Peter J. Cameron, Nov 03 2024.
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
Numerator of (1+1/(n-1))^(n-1) for n>1. - Jean-François Alcover, Jan 14 2013
Right edge of triangle A075513. - Michel Marcus, May 17 2013
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
Central terms of triangle A051129: a(n) = A051129(2*n-1,n). - Reinhard Zumkeller, Sep 14 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

Examples

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

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

Crossrefs

Cf. A000055, A000081, A000142, A000272, A000312, A002720, A007778, A007830, A008785-A008791, A055860, A002061, A052746, A052756, A052764, A052789, A051129, A098686, A247363, A055302, A248120, A130293, A053506-A053509, A262974.
Other classes of endofunctions: A275549-A275558.

Programs

  • Haskell
    a000169 n = n ^ (n - 1)  -- Reinhard Zumkeller, Sep 14 2014
  • Magma
    [n^(n-1): n in [1..20]]; // Vincenzo Librandi, Jul 17 2015
  • Maple
    A000169 := n -> n^(n-1);
# 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):
seq(A000169(n), n = 1 .. 23);  # Mélika Tebni, May 07 2023
  • Mathematica
    Table[n^(n - 1), {n, 1, 20}] (* Stefan Steinerberger, Apr 01 2006 *)
Range[0, 18]! CoefficientList[ Series[ -LambertW[-x], {x, 0, 18}], x] // Rest (* Robert G. Wilson v, updated by Jean-François Alcover, Oct 14 2019 *)
(* 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}]
1/%  (* A203421 *)
Table[v[n]/v[n + 1], {n, 1, z - 1}]  (* A000169 signed *)
(* Clark Kimberling, Jan 02 2012 *)
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 *)
  • MuPAD
    n^(n-1) $ n=1..20 /* Zerinvary Lajos, Apr 01 2007 */
  • PARI
    a(n) = n^(n-1)
  • Python
    def a(n): return n**(n-1)
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Sep 19 2021
  • 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

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.
a(n) = A000312(n-1)*A128434(n,1)/A128433(n,1). - Reinhard Zumkeller, Mar 03 2007
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
Limit_{n->oo} a(n)/A000312(n-1) = e. - Daniel Suteu, Jul 23 2016
From Amiram Eldar, Nov 20 2020: (Start)
Sum_{n>=1} 1/a(n) = A098686.
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

A055858 Coefficient triangle for certain polynomials.

Original entry on oeis.org

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
Offset: 0

Views

Author

Wolfdieter Lang, Jun 20 2000

Keywords

Comments

The coefficients of the partner polynomials are found in triangle A055864.

Examples

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

Crossrefs

Column sequences are A000312(n), n >= 1, A055860 (A000169), A055861 (A053506), A055862-3 for m=0..4, row sums: A045531(n+1)= |A039621(n+1, 2)|, n >= 0.

Programs

  • 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 *)

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.

A055861 Essentially A053506 but with leading 0 (instead of 1) and offset 0.

Original entry on oeis.org

0, 0, 6, 48, 500, 6480, 100842, 1835008, 38263752, 900000000, 23579476910, 681091006464, 21505924728444, 737020860878848, 27246730957031250, 1080863910568919040, 45798768824157052688, 2064472028642102280192
Offset: 0

Views

Author

Wolfdieter Lang, Jun 20 2000

Keywords

Crossrefs

Third column of triangle A055858.
Cf. A053506, A000312, A000169, A055860.

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.

A055862 Fourth column of triangle A055858.

Original entry on oeis.org

0, 0, 0, 36, 400, 5400, 86436, 1605632, 34012224, 810000000, 21435888100, 624333422592, 19851622826256, 684376513673216, 25430282226562500, 1013309916158361600, 43104723599206637824, 1949779138161985486848
Offset: 0

Views

Author

Wolfdieter Lang Jun 20 2000

Keywords

Crossrefs

a(n)=A055858(n, 3). Cf. A000312, A000169, A055860, A055861.

Formula

a(i)=0, i=0, 1, 2; a(n)= (n^2)*(n+1)^(n-2), n >= 3.
E.g.f.: -x*(1+4*x)/2 + (W(-x)^2)*(1-W(-x))/((1+W(-x))*x*2), W(x) principal branch of Lambert's function.

A105819 Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices, on N labeled nodes.

Original entry on oeis.org

0, 2, 0, 9, 0, 0, 64, 12, 0, 0, 625, 180, 0, 0, 0, 7776, 2730, 120, 0, 0, 0, 117649, 46410, 3780, 0, 0, 0, 0, 2097152, 893816, 99120, 1680, 0, 0, 0, 0, 43046721, 19389384, 2600640, 90720, 0, 0, 0, 0, 0, 1000000000, 469532790, 71734320, 3654000, 30240, 0
Offset: 1

Views

Author

Washington Bomfim, Apr 21 2005

Keywords

Comments

Forests of order N with m components, m > floor(N/2) must contain an isolated vertex since it is impossible to partition N vertices in floor(N/2) + 1 or more trees without giving only one vertex to a tree.
Also the Bell transform of A055860. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

Examples

			a(8) = 12 because 4 vertices can be partitioned in two trees only in one way: both trees receiving 2 vertices. Two trees on 2 vertices can be labeled in binomial(4,2) ways and to each one of the 2*binomial(4,2) = 12 possibilities there are more 2 possible trees of order 2 in a forest. But since we have 2 trees of the same order, i.e., 2, we must divide 2*binomial(4,2)*2 by 2!.
Triangle T(n,k) begins:
:       0;
:       2,      0;
:       9,      0,     0;
:      64,     12,     0,    0;
:     625,    180,     0,    0, 0;
:    7776,   2730,   120,    0, 0, 0;
:  117649,  46410,  3780,    0, 0, 0, 0;
: 2097152, 893816, 99120, 1680, 0, 0, 0, 0;

Links

Crossrefs

Cf. A033185, A055860, A105599, A354794, A360193.
Row sums give A105785.

Programs

  • Maple
    # The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> `if`(n=0,0,(n+1)^n), 9); # Peter Luschny, Jan 27 2016
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
       binomial(n-1, j-1)*j^(j-1)*x*b(n-j), j=2..n)))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Aug 13 2017
  • Mathematica
    BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
B = BellMatrix[Function[n, If[n == 0, 0, (n+1)^n]], rows];
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)

Formula

a(n)= 0, if m > floor(N/2) (see comments), or can be calculated by the sum Num/D over the partitions of N: 1K1 + 2K2 + ... + nKN, with exactly m parts and smallest part = 2, where Num = N!*Product_{i=1..N}i^((i-1)Ki) and D = Product_{i=1..N}(Ki!(i!)^Ki).
From Mélika Tebni, Apr 23 2023: (Start)
E.g.f. of column k: (-x - LambertW(-x))^k / k!, k > 0.
Sum_{k=1..n} (-1)^(n-k)*T(n+k,k) = n+1.
Sum_{k=1..n} (-1)^(k+1)*T(n,k) = A360193(n), for n > 0.
Sum_{k=1..n} (-1)^(k+1)*T(n+k,k)/(n+k-1) = 1/n, for n > 1.
T(n,k) = Sum_{j=k..n} j!*abs(Stirling1(j-k,k))*A354794(n,j)/(j-k)!. (End)

A365108 a(n) is the smallest integer value of (p^n - q^n)/n for all choices of integers p > q >= 0.

Original entry on oeis.org

1, 2, 9, 4, 625, 672, 117649, 32, 2187, 5941760, 25937424601, 1397760, 23298085122481, 308548739072, 29192926025390625, 4096, 48661191875666868481, 3817734144, 104127350297911241532841, 174339220, 209430786243, 24639156314201655345152, 907846434775996175406740561329
Offset: 1

Views

Author

Felix Huber, Aug 21 2023

Keywords

Comments

(p^n - q^n)/n has the integer value n^(n - 1) for p = n and q = 0. For p = n + k + 1 (k: nonnegative integer) the term has its minimum for q = n + k. With the binomial theorem follows ((n + k + 1)^n - (n + k)^n)/n >= ((n + k)^n - n*(n + k)^(n - 1) - (n + k)^n)/n = (n + k)^(n - 1) >= n^(n - 1). Therefore, for p > n, there is no smaller value of (p^n - q^n)/n than n^(n - 1). Thus a(n) <= n^(n - 1) exists with 1 <= p <= n and 0 <= q <= p - 1.
a(n) is also the smallest integer value that the integral over f(x) = x^(n - 1) between the nonnegative integer integration limits q and p (p > q) can have.

Examples

			For n = 5, a(5) = 672 with p = 4 and q = 2.

Links

Crossrefs

Cf. A000169, A055860, A020725.

Programs

  • Maple
    A365108 := proc(n) local q, p, s, a_n; a_n := n^(n - 1); for p to n do for q from 0 to p - 1 do s := (p^n - q^n)/n; if s = floor(s) and s < a_n then a_n := s; end if; end do; end do; return a_n; end proc;
seq(A365108(n), n = 1 .. 23);
  • Python
    from sympy.ntheory.residue_ntheory import nthroot_mod
def A365108(n):
    c, qdict = n**(n-1), {}
    for p in range(1,n+1):
        r, m = pow(p,n,n), p**n
        if r not in qdict:
            qdict[r] = tuple(nthroot_mod(r,n,n,all_roots=True))
        c = min(c,min(((m-q**n)//n for q in qdict[r] if qChai Wah Wu, Sep 23 2023

Formula

a(n) is the integer minimum of (p^n - q^n)/n for 1 <= p <= n and 0 <= q <= p - 1.

A055863 Fifth column of triangle A055858.

Original entry on oeis.org

0, 0, 0, 0, 320, 4500, 74088, 1404928, 30233088, 729000000, 19487171000, 572305637376, 18324574916544, 635492476982272, 23734930078125000, 949978046398464000, 40569151622782717952, 1841458074930764070912
Offset: 0

Views

Author

Wolfdieter Lang Jun 20 2000

Keywords

Crossrefs

a(n)=A055858(n, 4). Cf. A000312, A000169, A055860-A055862.

Formula

a(i)=0, i=0..3; a(n)= (n^3)*(n+1)^(n-3), n >= 4.
E.g.f.: -x*(3+16*x+54*x^2)/12+(W(-x)^2)*(3-7*W(-x)+2*W(-x)^2)/ (12*(1+W(-x))*x), W(x) principal branch of Lambert's function.
Showing 1-7 of 7 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.