A112532 First differences of [0, A047970].

1, 1, 3, 9, 29, 101, 379, 1525, 6549, 29889, 144419, 736241, 3947725, 22201549, 130624587, 802180701, 5131183301, 34121977865, 235486915507, 1683925343929, 12458499203901, 95237603403381, 751291094637083, 6108883628141189, 51144808472958709, 440444879385258001

Offset: 0

Author

Alford Arnold, Sep 10 2005

Keywords

• nonn

Comments

Number of sequences of length n in [n] (endofunctions) whose first run has length equal to the maximum of the sequence.

Examples

			The 9 sequences for n=4 (sorted by maximum)
1121,1122,2211,2212, 1113,2223,3331,3332, 4444
The 29 sequences for n=5 (sorted by maximum)
11211,11212,11221,11222, 22111,22112,22121,22122, 11123,11131,11132,11133, 22213,22231,22232,22233, 33311,33312,33313,33321,33322,33323, 11114, 22224, 33334, 44441,44442,44443, 55555
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..500

Crossrefs

Cf. A047970, A112531, A229046.

First differences of column 0 of triangle A089246 (beginning at row 1). With offset 1, first differences of column 0 of triangle A242431. Second differences of column 0 of triangle A101494.

Programs

Mathematica

a[n_]:= If[n==0, 1, n + Sum[(i-1)^2*i^(n-i), {i,0,n}]];
Table[a[n], {n, 0, 30}] (* G. C. Greubel, Jan 12 2022 *)

PARI

a(n) = n + sum(i = 0, n, (n-i-1)^2 * (n-i)^i); \\ Michel Marcus, Mar 01 2021

Sage

[n +sum((j-1)^2*j^(n-j) for j in (0..n)) for n in (0..30)] # G. C. Greubel, Jan 12 2022

Formula

G.f.: (1-x)^2*( Sum_{n >= 0} x^n/(1 - (n+2)*x) ). - Peter Bala, Jul 09 2014

From Mathew Englander, Feb 28 2021: (Start)

a(n) = A089246(n+2,0) - A089246(n+1,0).

a(n) = n + Sum_{i = 0..n} (n-i-1)^2 * (n-i)^i. (End)

Extensions

Corrected by D. S. McNeil, Aug 20 2010

Combinatorial interpretation and examples by Olivier Gérard, Jan 29 2023