OFFSET
1,2
COMMENTS
a(n) is also the number of functions f{1,2,...,n}->{1,2,...,n} with at least one element mapped to 1. - Geoffrey Critzer, Dec 10 2012
Equivalently, a(n) is the number of endofunctions with minimum 1. - Olivier Gérard, Aug 02 2016
Number of bargraphs of width n and height n. Equivalently: number of ordered n-tuples of positive integers such that the largest is n. Example: a(3) = 19 because we have 113, 123, 213, 223, 131, 132, 231, 232, 311, 312, 321, 322, 331, 332, 313, 323, 133, 233, and 333. - Emeric Deutsch, Jan 30 2017
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..100
A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, The height and width of bargraphs, Discrete Applied Math. 180, (2015), 36-44.
FORMULA
a(n) = n^n - (n-1)^n.
E.g.f.: (T - x)/(T-T^2), where T=T(x) is Euler's tree function (see A000169).
With interpolated zeros, ceiling(n/2)^ceiling(n/2) - floor(n/2)^ceiling(n/2). - Paul Barry, Jul 13 2005
a(n) = A047969(n,n). - Alford Arnold, May 07 2005
a(n) = Sum_{i=1..n} binomial(n,i)*(i-1)^(i-1)*(n-i)^(n-i) = Sum_{i=1..n} binomial(n,i)*A000312(i-1)*A000312(n-i). - Vladimir Shevelev, Sep 30 2010
a(n) = Sum_{k=1..n} k!*binomial(n-1,k-1)*Stirling2(n,k). - Vladimir Kruchinin, Mar 01 2014
a(n) = A350454(n+1, 1) / (n+1). - Mélika Tebni, Dec 20 2022
Limit_{n->oo} a(n)/n^n = 1 - 1/e = A068996. - Luc Rousseau, Jan 20 2023
MATHEMATICA
Table[Sum[Binomial[n, i] (n - 1)^(n - i), {i, 1, n}], {n, 1, 20}]
PROG
(Magma) [n^n-(n-1)^n: n in [1..20] ]; // Vincenzo Librandi, May 07 2011
(PARI) a(n)=n^n-(n-1)^n; \\ Charles R Greathouse IV, May 08 2011
(Maxima) a(n) := sum(k!*binomial(n-1, k-1)*stirling2(n, k), k, 1, n); /* Vladimir Kruchinin, Mar 01 2014 */
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
STATUS
approved