OFFSET
1,5
COMMENTS
The excedance set of a permutation p in S_n is the set of indices i such that p(i) > i.
T(a+b-1,b-1)*(-1)^(a+b-1) = Sum_{k=0..} F(a,b,k)*(-1)^k where F(a,b,k) is the number of connected subgraphs of K(a,b) (the complete bipartite graph) with k edges. F(n,n,k) is A255192(n,k). - Thomas Dybdahl Ahle, Feb 18 2015 [The sum starts with k=0, and F(n,n,k) is A255192(n,k), but there seems to be no A255192(n,0). Is there no upper k-summation limit? - Wolfdieter Lang, Mar 15 2015]
Comment from Don Knuth, Aug 25 2020, added by N. J. A. Sloane, Sep 07 2020: (Start)
This array also arises from a problem about {0,1}-matrices. Symmetric array read by antidiagonals: A(n,k) (n >= 1, k >= 0) = number of n X k matrices of 0's and 1's satisfying two conditions: (i) no column is entirely 0; (ii) no 0 has simultaneously a 1 above it and another 1 to its left.
Equivalently (see the Steingrímsson-Williams reference) A(n,k) is the number of permutations p_1...p_{n+k} on {1,...,n+k} for which p_1 >= 1, ..., p_n >= n, p_{n+1} < n+1,..., p_{n+k} < n+k. Then A(n,k) = A(k+1,n-1), for n >= 1 and k >= 0.
For example, the seven 2 X 2 matrices satisfying (i) and (ii) are
00 01 10 10 11 11 11
11 11 01 11 00 01 11
and the seven permutations of {1, 2, 3, 4} satisfying the other definition are
1423, 2413, 3412, 3421, 4213, 4312, 4321.
(End)
LINKS
Paul D. Hanna, Rows n = 1..31, flattened.
Tsuneo Arakawa and Masanobu Kaneko, Multiple zeta values, poly-Bernoulli numbers, and related zeta functions, Nagoya Math. J., 153:189-209, 1999.
Arvind Ayyer, Daniel Hathcock, and Prasad Tetali, Toppleable Permutations, Excedances and Acyclic Orientations, arXiv:2010.11236 [math.CO], 2020. Mentions this sequence.
Arvind Ayyer and Beáta Bényi, Toppling on permutations with an extra chip, arXiv:2104.13654 [math.CO], Apr. 2021. (See table 1.)
Beáta Bényi and Peter Hajnal, Combinatorial properties of poly-Bernoulli relatives, arXiv preprint arXiv:1602.08684 [math.CO], 2016. See C_{n,k}.
Beáta Bényi and Matthieu Josuat-Vergès, Combinatorial proof of an identity on Genocchi numbers, arXiv:2010.10060 [math.CO], 2020.
Taylor Brysiewicz and Aida Maraj, Lawrence Lifts, Matroids, and Maximum Likelihood Degrees, arXiv:2310.13064 [math.CO], 2023. See p. 13.
E. Clark and R. Ehrenborg, Explicit expressions for the extremal excedance statistic, European J. Combinatorics, 31, 2010, 270-279 (Theorem 3.1).
Bérénice Delcroix-Oger, Florent Hivert, Patxi Laborde-Zubieta, Jean-Christophe Aval, and Adrien Boussicault, Non-ambiguous trees: New results and generalisation (full version), arXiv:2103.07294 [cs.DM], 2021 (Proposition 1.8).
R. Ehrenborg and E. Steingrimsson, The excedance set of a permutation, Advances in Appl. Math., 24, 284-299, 2000 (Proposition 6.5).
Anatol N. Kirillov, On some quadratic algebras. I 1/2: Combinatorics of Dunkl and Gaudin elements, Schubert, Grothendieck, Fuss-Catalan, universal Tutte and reduced polynomials, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 002, 172 p. (2016).
Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024 (see Eq. (16.1)).
Toshiki Matsusaka, Symmetrized poly-Bernoulli numbers and combinatorics, arXiv:2003.12378 [math.NT], 2020. Table 1.
Einar Steingrímsson and Lauren K Williams, Permutation tableaux and permutation patterns, Journal of Combinatorial Theory, A 114 (2007), 211-234.
Julius Worpitzky, Studien über die Bernoullischen und Eulerschen Zahlen, Journal für die reine und angewandte Mathematik. 94:203-232, 1883.
FORMULA
T(n,k) = Sum_{i=1..k+1} (-1)^(k+1-i)*i!*i^(n-1-k)*Stirling2(k+1,i) (0 <= k <= n-1).
G.f.: A(x,y) = x*y*Sum_{n>=1} n! * x^n*Product_{k=1..n} (1 + y + k*x*y) / (1 + (1+y)*k*x + k^2*x^2*y). - Paul D. Hanna, Feb 01 2013
Central terms of triangle equals A092552. - Paul D. Hanna, Feb 01 2013
T(n,k-1) = Sum_{i=0..k, m=0..i} binomial(i,m)*(-1)^(k-m)*i^(n-k)*m^k (1 <= k <= n). - Thomas Dybdahl Ahle, Feb 18 2015
E.g.f.: log(1/(1-(exp(x)-1)*(exp(y)-1))). - Vladimir Kruchinin, Apr 17 2015
Let W(n,k) = k!*Stirling2(n+1, k+1) denote the Worpitzky numbers, then A(n,k) = Sum_{j=0..k} (-1)^(k-j)*W(k,j)*(j+1)^(n+1) enumerates the square array. - Peter Luschny, Mar 14 2018
Assume the missing first row (1,0,0,...) of the array which Ayyer and Bényi call the 'poly-Bernoulli numbers of type C'. Then T(n, k) = p_{n}(k) where p_{n}(x) = Sum_{k=0..n} (-1)^(n-k)*(k+1)^x*Sum_{j=0..n} E1(n,j)*binomial(n-j, n-k), and E1(n, k) are the Eulerian numbers of first order. This reflects the Worpitzky approach to the Bernoulli numbers. This formula can alternatively be written as: T(n, k) = Sum_{j=0..k} (-1)^(k-j)*(j+1)^n*A028246(k+1, j+1). - Peter Luschny, Apr 29 2021
EXAMPLE
T(4,2) = 7 because 3412, 4312, 2413, 2314, 2431, 3421 and 4321 are the only permutations of {1,2,3,4} with excedance set {1,2}.
Triangle starts:
1;
1, 1;
1, 3, 1;
1, 7, 7, 1;
1, 15, 31, 15, 1;
1, 31, 115, 115, 31, 1;
1, 63, 391, 675, 391, 63, 1;
1, 127, 1267, 3451, 3451, 1267, 127, 1;
1, 255, 3991, 16275, 25231, 16275, 3991, 255, 1;
...
Formatted as a square array A(n,k) with 0 <= k <= n:
1, 1, 1, 1, 1, 1, 1, 1, ... [A000012]
1, 3, 7, 15, 31, 63, 127, 255, ... [A000225]
1, 7, 31, 115, 391, 1267, 3991, 12355, ... [A091344]
1, 15, 115, 675, 3451, 16275, 72955, 316275, ... [A091347]
1, 31, 391, 3451, 25231, 164731, 999391, 5767051, ... [A091348]
1, 63, 1267, 16275, 164731, 1441923, 11467387, 85314915, ...
1, 127, 3991, 72955, 999391, 11467387, 116914351, 1096832395, ...
MAPLE
with(combinat): T:=proc(n, k) if k < n then add((-1)^(k+1-i)*factorial(i)*i^(n-1-k)* stirling2(k+1, i), i=1..k+1) else 0 end if end proc: for n to 10 do seq(T(n, k), k=0..n-1) end do; # yields sequence in triangular form
# Alternatively as a square array:
A := (n, k) -> add((-1)^(k-j)*j!*Stirling2(k+1, j+1)*(j+1)^(n+1), j=0..k);
seq(print(seq(A(n, k), k=0..7)), n=0..6); # Peter Luschny, Mar 14 2018
# Using the exponential generating function as given by Arakawa & Kaneko:
gf := polylog(-t, 1-exp(-x))/(exp(x)-1):
ser := series(gf, x, 12): c := n -> n!*coeff(ser, x, n):
seq(lprint(seq(subs(t=k, c(n)), n=0..8)), k=0..8); # Peter Luschny, Apr 29 2021
# Using recurrence relations:
A := proc(n, k) option remember; local j; if n = 0 then return k^n fi;
add(binomial(k+1, j+1)*A(n-1, k-j), j = 0..k) end:
for n from 0 to 7 do lprint(seq(A(n, k), k=0..8)) od; # Peter Luschny, Apr 19 2024
MATHEMATICA
T[n_, k_] := Sum[(-1)^(k + 1 - i)*i!*i^(n - 1 - k)*StirlingS2[k + 1, i], {i, 1, k + 1}];
Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, Nov 16 2017 *)
PROG
(PARI) {T(n, k)=polcoeff(polcoeff( x*y*sum(m=0, n, m!*x^m*prod(k=1, m, (1+y+k*x*y)/(1+(1+y)*k*x+k^2*x^2*y +x*O(x^n))) ), n, x), k, y)} \\ Paul D. Hanna, Feb 01 2013
for(n=1, 10, for(k=1, n, print1(T(n, k), ", ")); print(""))
(PARI) tabl(nn) = {default(seriesprecision, nn+1); pol = log(1/(1-(exp(x)-1)*(exp(y)-1))) + O(x^nn); for (n=1, nn-1, poly = n!*polcoeff(pol, n, x); for (k=1, n, print1(k!*polcoeff(poly, k, y), ", "); ); print(); ); } \\ Michel Marcus, Apr 17 2015
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jan 17 2008
EXTENSIONS
Definition corrected. Changed "T(n,k) is the number of permutations of {1,2,...,n}..." to "T(n,k) is the number of permutations of {1,2,...,k+n}..." - Karel Casteels (kcasteel(AT)sfu.ca), Feb 17 2010
STATUS
approved