OFFSET
1,2
COMMENTS
Each cycle is written with the smallest element first and cycles are arranged in increasing order of their first elements.
Also, the number of colorings of n+1 given balls, two thereof identical, using n given colors (each color is used). - Ivaylo Kortezov, Jan 27 2024
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..448
Ivaylo Kortezov, Winter Math Contest Yambol 2024, Bulgaria (in Bulgarian), Problem 8.3.
Wikipedia, Permutation.
FORMULA
a(n) = n!*(n*(n+1) - (n-1)*(n+2)/2)/2.
E.g.f.: -x*(x^2-2*x+2)/(2*(x-1)^3).
a(n) = (n^2+n+2)*n*a(n-1)/(n^2-n+2) for n > 1, a(n) = n for n < 2.
a(n) = n*A006595(n-1). - Ivaylo Kortezov, Feb 02 2024
EXAMPLE
a(3) = 21 because the sum of the entries in the first cycles of all permutations of [3] ((123), (132), (12)(3), (13)(2), (1)(23), (1)(2)(3)) is 6+6+3+4+1+1 = 21.
MAPLE
a:= n-> n!*(n*(n+1)-(n-1)*(n+2)/2)/2:
seq(a(n), n=1..25);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n,
(n^2+n+2)*n*a(n-1)/(n^2-n+2))
end:
seq(a(n), n=1..25);
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Apr 15 2017
STATUS
approved