A284816 Sum of entries in the first cycles of all permutations of [n].

1, 4, 21, 132, 960, 7920, 73080, 745920, 8346240, 101606400, 1337212800, 18920563200, 286442956800, 4620449433600, 79114299264000, 1433211107328000, 27387931963392000, 550604138692608000, 11617107089043456000, 256671161862635520000, 5926549291918295040000

Offset: 1

Author

Alois P. Heinz, Apr 15 2017

Keywords

• nonn

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

Examples

			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.
		

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.

Crossrefs

Cf. A006595, A180119, A185105, A285363, A285382.

Column k=1 of A285439.

Programs

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);

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