A045531 Number of sticky functions: endofunctions of [n] having a fixed point.

1, 3, 19, 175, 2101, 31031, 543607, 11012415, 253202761, 6513215599, 185311670611, 5777672071535, 195881901213181, 7174630439858727, 282325794823047151, 11878335717996660991, 532092356706983938321, 25283323623228812584415, 1270184310304975912766347

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

Column |a(n, 2)| of A039621. Row sums of triangle A055858.

Cf. A000312, A066274, A066275, A047969.

Column k=1 of A246049.

Cf. A068996, A350454.

Sequence in context: A349768 A083071 A305459 * A129481 A276371 A156131

Adjacent sequences: A045528 A045529 A045530 * A045532 A045533 A045534

Keyword

easy,nonn

Author

Len Smiley

Status

approved