A136126 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.
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, 1, 511, 12355, 72955, 164731, 164731, 72955, 12355, 511, 1
Offset: 1
Examples
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, ...
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.
Crossrefs
Programs
-
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 *) -
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
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
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
Comments