login
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
OFFSET
0,3
COMMENTS
Row sums of A136126.
LINKS
J.-C. Aval, A. Boussicault, M. Bouvel and M. Silimbani, Combinatorics of non-ambiguous trees, arXiv:1305.3716 [PDF], 2012. - From N. J. A. Sloane, Jan 03 2013
Beata Bényi, Peter Hajnal, Combinatorial properties of poly-Bernoulli relatives, arXiv preprint arXiv:1602.08684 [math.CO], 2016.
R. F. de Andrade, E. Lundberg, B, Nagle, Asymptotics of the Extremal Excedance Set Statistic, arXiv preprint arXiv:1403.0691 [math.CO], 2014.
R. Ehrenborg and E. Steingrimsson, The excedance set of a permutation, Advances in Appl. Math., 24, 284-299, 2000 (Proposition 6.5).
Toshiki Matsusaka, Symmetrized poly-Bernoulli numbers and combinatorics, arXiv:2003.12378 [math.NT], 2020. Remark 1.2.
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}];
Array[a, 30] (* Jean-François Alcover, Mar 29 2017 *)
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)
for(n=1, 30, print1(a(n), ", "))\\ Paul D. Hanna, Feb 01 2013
CROSSREFS
Cf. A136126.
Sequence in context: A124470 A105072 A022494 * A111004 A344640 A345673
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jan 17 2008
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Oct 30 2023
STATUS
approved