1,2

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

N. Hobson, Home page (listed in lieu of email address)

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

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

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

Cf. A000169, A000142.

Sequence in context: A139397 A081343 A163048 this_sequence A123766 A005332 A132546

Adjacent sequences: A126127 A126128 A126129 this_sequence A126131 A126132 A126133

easy,nonn

Nick Hobson (nickh(AT)qbyte.org), Dec 18 2006