A126130 a(n) = (n+1)^n - n!.

1, 7, 58, 601, 7656, 116929, 2092112, 43006401, 999637120, 25933795801, 742968453888, 23297606120881, 793708546233344, 29192838847099425, 1152920196932478976, 48661170952876980481, 2185911204051268435968, 104127343895537535804841, 5242879878354899591168000

Offset: 1

Author

Nick Hobson, Dec 18 2006

Keywords

• easy
• nonn

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

Examples

			The quadratic that fits (1,1), (2,8) and (3,27) is f(n) = 6n^2-11n+6. Then a(3) = f(4) = 58.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..386

Crossrefs

Cf. A000169, A000142.

Programs

Magma

[(n+1)^n - Factorial(n): n in [1..20]]; // Altug Alkan, Mar 19 2018

Mathematica

Table[(n+1)^n-n!,{n,30 }] (* Harvey P. Dale, Jun 06 2015 *)

PARI

vector(18, n, (n+1)^n-n!)

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

a(n) = Sum_{k=1..n} k^n*(-1)^(n-k)*binomial(n,k-1). - Vladimir Kruchinin, Aug 15 2025