OFFSET
0,3
COMMENTS
Number of sequences of length n in [n] (endofunctions) whose first run has length equal to the maximum of the sequence.
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..500
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) = n + Sum_{i = 0..n} (n-i-1)^2 * (n-i)^i. (End)
EXAMPLE
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
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Alford Arnold, Sep 10 2005
EXTENSIONS
Corrected by D. S. McNeil, Aug 20 2010
Combinatorial interpretation and examples by Olivier Gérard, Jan 29 2023
STATUS
approved