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

Comments

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

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

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

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.

Example

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.

Mathematica

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

Prog

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

Crossrefs

Cf. A002627.

Sequence in context: A002807 A124610 A002683 * A362247 A126475 A274674

Adjacent sequences: A319010 A319011 A319012 * A319014 A319015 A319016

Keyword

nonn

Author

Peter Kagey, Sep 07 2018

Status

approved