|
|
A136127
|
|
Number of permutations of {1,2,...,n} having excedance set {1,2,...,k} for some k=0...n-1 (for k=0 we have the empty set). The excedance set of a permutation p in S_n is the set of indices i such that p(i)>i.
|
|
7
|
|
|
1, 1, 2, 5, 16, 63, 294, 1585, 9692, 66275, 501106, 4150965, 37383528, 363674407, 3800501438, 42460229945, 505029329524, 6371454458859, 84981113118090, 1194793819467325, 17660505018471680, 273788611235722031, 4442085091233531862, 75276072393821203905
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum(Sum (-1)^(k+1-i)*i!*i^(n-1-k) * Stirling2(k+1,i), i=1..k+1), k=0..n).
G.f.: x*Sum_{n>=0} n! * x^n * Product_{k=1..n} (2 + k*x)/(1 + 2*k*x + k^2*x^2). - Paul D. Hanna, Feb 01 2013
a(n) ~ Pi * n^(n+1) / (exp(n) * 2^(n+1) * (log(2))^(n+3/2)). - Vaclav Kotesovec, Sep 11 2014
|
|
EXAMPLE
|
a(3) = 5 because we have 123, 312, 213, 321 and 231 with excedance sets empty, {1}, {1}, {1} and {1,2}, respectively.
|
|
MAPLE
|
a:= proc(n) add(add((-1)^(k+1-i) *factorial(i)*i^(n-1-k)*Stirling2(k+1, i), i=1..k+1), k=0..n) end proc: seq(a(n), n=0..30);
|
|
MATHEMATICA
|
a[n_] := Sum[(-1)^(k+1-i)*i!*i^(n-1-k)*StirlingS2[k+1, i], {k, 0, n}, {i, 1, k+1}];
|
|
PROG
|
(PARI) a(n)=polcoeff( x*sum(m=0, n, m!*x^m*prod(k=1, m, (2+k*x)/ (1+2*k*x+k^2*x^2 +x*O(x^n))) ), n)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|