OFFSET
1,2
COMMENTS
Fit a polynomial f of degree n-1 to the first n n-th powers of positive integers. Then a(n) = f(n+1). It is not necessary to actually determine the polynomial f; a(n) can be found by considering differences.
a(n-1) is also the number of labeled rooted trees on n objects that are not increasing; i.e., at least one node has a label smaller than its parent's label. a(n) is the number of partial functions on n labeled objects that are not permutations. - Franklin T. Adams-Watters, Dec 25 2006
Equal to the number of partial functions [n]->[n] which are not permutations (equivalently, the number of non-surjective partial functions [n]->[n]); i.e. equal to the cardinality of the complement PT_n\S_n where PT_n and S_n denote the partial transformation semigroup and symmetric group on [n]. - James East, May 03 2007
Given a set of n+1 unique items, a(n)/(n+1)^n is the probability that at least one item will not be selected in n+1 random drawings (with replacement) from the set. - Bob Selcoe, Aug 30 2019
LINKS
Seiichi Manyama, Table of n, a(n) for n = 1..386
FORMULA
The polynomial f is equal to Sum_{k=1}^n -s(n+1,k) x^{k-1}, where the s(n,k) are the Stirling numbers of the first kind (A008275). - Franklin T. Adams-Watters, Dec 25 2006
E.g.f.: -1/(1 - x) - LambertW(-x)/(x*(1 + LambertW(-x))), where LambertW() is the Lambert W-function. - Ilya Gutkovskiy, Aug 22 2018
EXAMPLE
The quadratic that fits (1,1), (2,8) and (3,27) is f(n) = 6n^2-11n+6. Then a(3) = f(4) = 58.
MATHEMATICA
Table[(n+1)^n-n!, {n, 30 }] (* Harvey P. Dale, Jun 06 2015 *)
PROG
(PARI) vector(18, n, (n+1)^n-n!)
(Magma) [(n+1)^n - Factorial(n): n in [1..20]]; // Altug Alkan, Mar 19 2018
CROSSREFS
KEYWORD
easy,nonn,changed
AUTHOR
Nick Hobson, Dec 18 2006
STATUS
approved