|
%I #37 Feb 11 2024 12:40:11
%S 1,7,58,601,7656,116929,2092112,43006401,999637120,25933795801,
%T 742968453888,23297606120881,793708546233344,29192838847099425,
%U 1152920196932478976,48661170952876980481,2185911204051268435968
%N a(n) = (n+1)^n - n!.
%C 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.
%C 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
%C 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
%C 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
%H Seiichi Manyama, <a href="/A126130/b126130.txt">Table of n, a(n) for n = 1..386</a>
%F 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
%F E.g.f.: -1/(1 - x) - LambertW(-x)/(x*(1 + LambertW(-x))), where LambertW() is the Lambert W-function. - _Ilya Gutkovskiy_, Aug 22 2018
%e The quadratic that fits (1,1), (2,8) and (3,27) is f(n) = 6n^2-11n+6. Then a(3) = f(4) = 58.
%t Table[(n+1)^n-n!,{n,30 }] (* _Harvey P. Dale_, Jun 06 2015 *)
%o (PARI) vector(18, n, (n+1)^n-n!)
%o (Magma) [(n+1)^n - n!: n in [1..20]]; // _Altug Alkan_, Mar 19 2018
%Y Cf. A000169, A000142.
%K easy,nonn
%O 1,2
%A _Nick Hobson_, Dec 18 2006
| 