login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 9
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 (list; table; graph; refs; listen; history; text; internal format)
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.

Columns 1,2,3,4 yield A000225, A091344, A091347, A091348, respectively. Row sums yield A136127.

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.

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).

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

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

Cf. A000225, A028246, A091344, A091347, A091348, A092552, A136127, A152884, A255192, A329369.

Sequence in context: A108470 A328300 A157152 * A046802 A184173 A022166

Adjacent sequences:  A136123 A136124 A136125 * A136127 A136128 A136129

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 22:37 EDT 2022. Contains 353826 sequences. (Running on oeis4.)