A319013 a(n) is the sum over each permutation of S_n of the least element of the descent set.

0, 1, 7, 37, 201, 1231, 8653, 69273, 623521, 6235291, 68588301, 823059733, 10699776673, 149796873591, 2246953104061, 35951249665201, 611171244308673, 11001082397556403, 209020565553571981, 4180411311071439981, 87788637532500240001, 1931350025715005280463

Offset: 1

Author

Peter Kagey, Sep 07 2018

Keywords

• nonn

Comments

a(1) = 0 since the descent set of the identity permutation is empty.

Lim_{n->infinity} a(n)/n! = e - 1.

Examples

			For n = 3, the least element of the descent set for each permutation in S_3 is given by the table:
+-------------+-------------+----------------------+
| permutation | descent set | least element (or 0) |
+-------------+-------------+----------------------+
| 123         | {}          | 0                    |
| 132         | {2}         | 2                    |
| 213         | {1}         | 1                    |
| 231         | {2}         | 2                    |
| 312         | {1}         | 1                    |
| 321         | {1,2}       | 1                    |
+-------------+-------------+----------------------+
Thus a(3) = 0 + 2 + 1 + 2 + 1 + 1 = 7.
		

References

• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 2011; see Section 1.4, pp. 38.

Links

• Peter Kagey, Table of n, a(n) for n = 1..400

Crossrefs

Cf. A002627.

Programs

Mathematica

Table[Sum[k^2*Binomial[n, k + 1]*(n - k - 1)!, {k, 1, n - 1}], {n, 1, 15}]

PARI

a(n) = sum(k=1, n-1, k^2*binomial(n, k+1)*(n-k-1)!); \\ Michel Marcus, Nov 28 2019

Formula

a(n) = Sum_{k=1..n-1} k^2*binomial(n, k+1)*(n - k - 1)!.

a(n+1) = (n+1)*a(n) + n^2, with a(1) = 0.

a(n) = A002627(n) - n.