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,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

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

Column k=1 of A285439.

Sequence in context: A131965 A332851 A303563 * A226067 A104982 A306335

Adjacent sequences: A284813 A284814 A284815 * A284817 A284818 A284819

Keyword

nonn

Author

Alois P. Heinz, Apr 15 2017

Status

approved