|
| |
|
|
A126130
|
|
a(n) = (n+1)^n - n!.
|
|
1
| |
|
|
1, 7, 58, 601, 7656, 116929, 2092112, 43006401, 999637120, 25933795801, 742968453888, 23297606120881, 793708546233344, 29192838847099425, 1152920196932478976, 48661170952876980481, 2185911204051268435968
(list; graph; refs; listen; history; internal format)
|
|
|
|
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 (FrankTAW(AT)Netscape.net), 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 (james.east(AT)latrobe.edu.au), May 03 2007
|
|
|
LINKS
| N. Hobson, Home page (listed in lieu of email address)
|
|
|
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 (FrankTAW(AT)Netscape.net), Dec 25 2006
|
|
|
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.
|
|
|
PROG
| (PARI) vector(18, n, (n+1)^n-n!)
|
|
|
CROSSREFS
| Cf. A000169, A000142.
Sequence in context: A081343 A163048 A192940 * A123766 A005332 A132546
Adjacent sequences: A126127 A126128 A126129 * A126131 A126132 A126133
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Nick Hobson (nickh(AT)qbyte.org), Dec 18 2006
|
| |
|
|
