The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #110 Apr 19 2024 02:01:10
%S 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,
%T 63,1,1,127,1267,3451,3451,1267,127,1,1,255,3991,16275,25231,16275,
%U 3991,255,1,1,511,12355,72955,164731,164731,72955,12355,511,1
%N Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,k+n} having excedance set {1,2,...,k} (the empty set for k=0), 0 <= k <= n-1.
%C The excedance set of a permutation p in S_n is the set of indices i such that p(i) > i.
%C Columns 1,2,3,4 yield A000225, A091344, A091347, A091348, respectively. Row sums yield A136127.
%C 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]
%C Comment from _Don Knuth_, Aug 25 2020, added by _N. J. A. Sloane_, Sep 07 2020: (Start)
%C 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.
%C 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.
%C For example, the seven 2 X 2 matrices satisfying (i) and (ii) are
%C 00 01 10 10 11 11 11
%C 11 11 01 11 00 01 11
%C and the seven permutations of {1, 2, 3, 4} satisfying the other definition are
%C 1423, 2413, 3412, 3421, 4213, 4312, 4321.
%C (End)
%H Paul D. Hanna, <a href="/A136126/b136126.txt">Rows n = 1..31, flattened.</a>
%H Tsuneo Arakawa and Masanobu Kaneko, <a href="https://projecteuclid.org/journals/nagoya-mathematical-journal/volume-153/issue-none/Multiple-zeta-values-poly-Bernoulli-numbers-and-relatedzeta-functions/nmj/1114630825.full">Multiple zeta values, poly-Bernoulli numbers, and related zeta functions</a>, Nagoya Math. J., 153:189-209, 1999.
%H Arvind Ayyer, Daniel Hathcock, and Prasad Tetali, <a href="https://arxiv.org/abs/2010.11236">Toppleable Permutations, Excedances and Acyclic Orientations</a>, arXiv:2010.11236 [math.CO], 2020. Mentions this sequence.
%H Arvind Ayyer and Beáta Bényi, <a href="https://arxiv.org/abs/2104.13654">Toppling on permutations with an extra chip</a>, arXiv:2104.13654 [math.CO], Apr. 2021. (See table 1.)
%H Beáta Bényi and Peter Hajnal, <a href="https://arxiv.org/abs/1602.08684">Combinatorial properties of poly-Bernoulli relatives</a>, arXiv preprint arXiv:1602.08684 [math.CO], 2016. See C_{n,k}.
%H Beáta Bényi and Matthieu Josuat-Vergès, <a href="https://arxiv.org/abs/2010.10060">Combinatorial proof of an identity on Genocchi numbers</a>, arXiv:2010.10060 [math.CO], 2020.
%H Taylor Brysiewicz and Aida Maraj, <a href="https://arxiv.org/abs/2310.13064">Lawrence Lifts, Matroids, and Maximum Likelihood Degrees</a>, arXiv:2310.13064 [math.CO], 2023. See p. 13.
%H E. Clark and R. Ehrenborg, <a href="http://dx.doi.org/10.1016/j.ejc.2008.11.014">Explicit expressions for the extremal excedance statistic</a>, European J. Combinatorics, 31, 2010, 270-279 (Theorem 3.1).
%H Bérénice Delcroix-Oger, Florent Hivert, Patxi Laborde-Zubieta, Jean-Christophe Aval, and Adrien Boussicault, <a href="https://arxiv.org/abs/2103.07294">Non-ambiguous trees: New results and generalisation (full version)</a>, arXiv:2103.07294 [cs.DM], 2021 (Proposition 1.8).
%H R. Ehrenborg and E. Steingrimsson, <a href="http://dx.doi.org/10.1006/aama.1999.0671">The excedance set of a permutation</a>, Advances in Appl. Math., 24, 284-299, 2000 (Proposition 6.5).
%H Anatol N. Kirillov, <a href="https://doi.org/10.3842/SIGMA.2016.002">On some quadratic algebras. I 1/2: Combinatorics of Dunkl and Gaudin elements, Schubert, Grothendieck, Fuss-Catalan, universal Tutte and reduced polynomials</a>, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 002, 172 p. (2016).
%H Don Knuth, <a href="http://cs.stanford.edu/~knuth/papers/poly-Bernoulli.pdf">Parades and poly-Bernoulli bijections</a>, Mar 31 2024 (see Eq. (16.1)).
%H Toshiki Matsusaka, <a href="https://arxiv.org/abs/2003.12378">Symmetrized poly-Bernoulli numbers and combinatorics</a>, arXiv:2003.12378 [math.NT], 2020. Table 1.
%H Einar Steingrímsson and Lauren K Williams, <a href="https://doi.org/10.1016/j.jcta.2006.04.001">Permutation tableaux and permutation patterns</a>, Journal of Combinatorial Theory, A 114 (2007), 211-234.
%H Julius Worpitzky, Studien über die Bernoullischen und Eulerschen Zahlen, Journal für die reine und angewandte Mathematik. 94:203-232, 1883.
%F 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).
%F 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
%F Central terms of triangle equals A092552. - _Paul D. Hanna_, Feb 01 2013
%F 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
%F E.g.f.: log(1/(1-(exp(x)-1)*(exp(y)-1))). - _Vladimir Kruchinin_, Apr 17 2015
%F 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
%F 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
%e 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}.
%e Triangle starts:
%e 1;
%e 1, 1;
%e 1, 3, 1;
%e 1, 7, 7, 1;
%e 1, 15, 31, 15, 1;
%e 1, 31, 115, 115, 31, 1;
%e 1, 63, 391, 675, 391, 63, 1;
%e 1, 127, 1267, 3451, 3451, 1267, 127, 1;
%e 1, 255, 3991, 16275, 25231, 16275, 3991, 255, 1;
%e ...
%e Formatted as a square array A(n,k) with 0 <= k <= n:
%e 1, 1, 1, 1, 1, 1, 1, 1, ... [A000012]
%e 1, 3, 7, 15, 31, 63, 127, 255, ... [A000225]
%e 1, 7, 31, 115, 391, 1267, 3991, 12355, ... [A091344]
%e 1, 15, 115, 675, 3451, 16275, 72955, 316275, ... [A091347]
%e 1, 31, 391, 3451, 25231, 164731, 999391, 5767051, ... [A091348]
%e 1, 63, 1267, 16275, 164731, 1441923, 11467387, 85314915, ...
%e 1, 127, 3991, 72955, 999391, 11467387, 116914351, 1096832395, ...
%p 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
%p # Alternatively as a square array:
%p A := (n, k) -> add((-1)^(k-j)*j!*Stirling2(k+1,j+1)*(j+1)^(n+1), j=0..k);
%p seq(print(seq(A(n, k), k=0..7)), n=0..6); # _Peter Luschny_, Mar 14 2018
%p # Using the exponential generating function as given by Arakawa & Kaneko:
%p gf := polylog(-t, 1-exp(-x))/(exp(x)-1):
%p ser := series(gf, x, 12): c := n -> n!*coeff(ser, x, n):
%p seq(lprint(seq(subs(t=k, c(n)), n=0..8)), k=0..8); # _Peter Luschny_, Apr 29 2021
%p # Using recurrence relations:
%p A := proc(n, k) option remember; local j; if n = 0 then return k^n fi;
%p add(binomial(k+1, j+1)*A(n-1, k-j), j = 0..k) end:
%p for n from 0 to 7 do lprint(seq(A(n, k), k=0..8)) od; # _Peter Luschny_, Apr 19 2024
%t T[n_, k_] := Sum[(-1)^(k + 1 - i)*i!*i^(n - 1 - k)*StirlingS2[k + 1, i], {i, 1, k + 1}];
%t Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* _Jean-François Alcover_, Nov 16 2017 *)
%o (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
%o for(n=1, 10,for(k=1,n, print1(T(n,k), ", "));print(""))
%o (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
%Y Cf. A000225, A028246, A091344, A091347, A091348, A092552, A136127, A152884, A255192, A329369, A371761.
%K nonn,tabl
%O 1,5
%A _Emeric Deutsch_, Jan 17 2008
%E 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