A136127 -id:A136127 - cp's OEIS frontend

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

Emeric Deutsch, Jan 17 2008

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)

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

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.

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

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

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

{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(""))

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

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

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

A208237 G.f.: Sum_{n>=0} n! * x^n * Product_{k=1..n} (1 + kx) / (1 + kx + k^2*x^2).

Original entry on oeis.org

1, 1, 2, 5, 15, 54, 223, 1045, 5474, 31685, 200895, 1384470, 10304431, 82376101, 703949762, 6403761365, 61784985615, 630180031734, 6775001385343, 76572619018165, 907658144193314, 11259399965148005, 145879271404693215, 1970471655222795990, 27702625497930064591

Offset: 0

Paul D. Hanna, Jan 11 2013

nonn

Compare to the identity:
Sum_{n>=0} n! * x^n * Product_{k=1..n} (1 + x) / (1 + k*x + k*x^2) = 1/(1-x-x^2).
Compare also to the g.f. of A136127:
x*Sum_{n>=0} n! * x^n * Product_{k=1..n} (2 + k*x) / (1 + 2*k*x + k^2*x^2).

			G.f.: A(x) = 1 + x + 2*x^2 + 5*x^3 + 15*x^4 + 54*x^5 + 223*x^6 + 1045*x^7 +...
where
A(x) = 1 + x*(1+x)/(1+x+x^2) + 2!*x^2*(1+x)*(1+2*x)/((1+x+x^2)*(1+2*x+4*x^2)) + 3!*x^3*(1+x)*(1+2*x)*(1+3*x)/((1+x+x^2)*(1+2*x+4*x^2)*(1+3*x+9*x^2)) + 4!*x^4*(1+x)*(1+2*x)*(1+3*x)*(1+4*x)/((1+x+x^2)*(1+2*x+4*x^2)*(1+3*x+9*x^2)*(1+4*x+16*x^2)) +...

Vaclav Kotesovec, Table of n, a(n) for n = 0..270

Cf. A221370, A204064, A204066, A208236, A136127.

{a(n)=polcoeff( sum(m=0, n, m!*x^m*prod(k=1, m, (1+k*x)/(1+k*x+k^2*x^2 +x*O(x^n))) ), n)}
for(n=0, 30, print1(a(n), ", "))

a(n) ~ 2 * 3^(n/2 + 5/4) * n^(n+2) / (exp(n) * Pi^(n+3/2)). - Vaclav Kotesovec, Nov 02 2014

A216121 Irregular triangle read by rows: T(n,k) is the number of permutations in C_n (= the 1-cycles in S_n) having k stretching pairs.

Original entry on oeis.org

1, 1, 2, 5, 1, 16, 6, 2, 63, 31, 20, 5, 1, 294, 168, 150, 70, 30, 6, 2, 1585, 997, 1072, 691, 423, 171, 75, 20, 5, 1, 9692, 6522, 7882, 6176, 4744, 2612, 1598, 656, 300, 100, 30, 6, 2, 66275, 46891, 61356, 54561, 49013, 32689, 24285, 13429, 7812, 3795, 1759, 651, 263, 75, 20, 5, 1

Offset: 1

Emeric Deutsch, Feb 26 2013

A stretching pair of a permutation p in S_n is a pair (i,j) (1 <= i < j <= n) satisfying p(i) < i < j < p(j). For example, for the permutation 31254 in S_5 the pair (2,4) is stretching because p(2) = 1 < 2 < 4 < p(4) = 5.
Sum of entries in row n is (n-1)! = A000142(n-1).
T(n,0) = A136127(n-1).
Sum_{k>=1} k*T(n,k) = n!*(n-3)/24 = A061206(n-3).

			T(4,1) = 1 because 3142 has 1 stretching pair (2,3); the other five 1-cycles in S_4 have no stretching pairs.
Triangle starts:
    1;
    1;
    2;
    5,   1;
   16,   6,   2;
   63,  31,  20,  5,  1;
  294, 168, 150, 70, 30, 6, 2;
  ...

E. Lundberg and B. Nagle, A permutation statistic arising in dynamics of internal maps. (submitted)

E. Clark and R. Ehrenborg, Explicit expressions for the extremal excedance statistic, European J. Combinatorics, 31, 2010, 270-279.
J. Cooper, E. Lundberg, and B. Nagle, Generalized pattern frequency in large permutations, Electron. J. Combin. 20, 2013, #P28.

Cf. A136127, A000142, A061206, A216120.

n := 7: with(combinat): nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else  end if end do: ct end proc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else  end if end do: ct end proc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: sp := proc (p) local ct, i, j: ct := 0: for i from 2 to nops(p)-2 do for j from i+1 to nops(p)-1 do if p[i] < i and i < j and j < p[j] then ct := ct+1 else  end if end do end do: ct end proc: P[n] := permute(n): C[n] := {}: for j to factorial(n) do if nrcyc(P[n][j]) = 1 then C[n] := `union`(C[n], {P[n][j]}) else  end if end do: sort(add(t^sp(C[n][j]), j = 1 .. factorial(n-1)));

The values of T(n,k) have been found by straightforward counting (with Maple). The Maple program (improvable!) yields the generating polynomial of the specified row n. Within the program, sp(p) is the number of stretching pairs of the permutation p.

More terms from Alois P. Heinz, Apr 15 2017

A221973 G.f.: Sum_{n>=0} n! * x^n * Product_{k=1..n} (3 + kx)/(1 + 3kx + k^2x^2).

Original entry on oeis.org

1, 3, 10, 39, 183, 1026, 6695, 49623, 411050, 3763599, 37757055, 411894882, 4854301087, 61459583007, 831926801290, 11989221944871, 183273754945959, 2961997167865410, 50462267599637975, 903853088211536295, 16980055625062979306, 333846342195447641343

Offset: 0

Paul D. Hanna, Feb 01 2013

nonn

			G.f.: A(x) = 1 + 3*x + 10*x^2 + 39*x^3 + 183*x^4 + 1026*x^5 + 6695*x^6 +...
where
A(x) = 1 + x*(3+x)/(1+3*x+x^2) + 2!*x^2*(3+x)*(3+2*x)/((1+3*x+x^2)*(1+6*x+4*x^2)) + 3!*x^3*(3+x)*(3+2*x)*(3+3*x)/((1+3*x+x^2)*(1+6*x+4*x^2)*(1+9*x+9*x^2)) + 4!*x^4*(3+x)*(3+2*x)*(3+3*x)*(3+4*x)/((1+3*x+x^2)*(1+6*x+4*x^2)*(1+9*x+9*x^2)*(1+12*x+16*x^2)) +...

Cf. A208237, A136127.

{a(n)=polcoeff( sum(m=0, n, m!*x^m*prod(k=1, m, (3+k*x)/(1+3*k*x+k^2*x^2 +x*O(x^n))) ), n)}
for(n=0, 30, print1(a(n), ", "))

A221988 G.f.: Sum_{n>=0} n! * (2x)^n Product_{k=1..n} (1 + kx)/(1 + 2k*x + 2k^2x^2).

Original entry on oeis.org

1, 2, 6, 24, 116, 664, 4392, 32928, 276016, 2557856, 25965408, 286538112, 3415359296, 43727878528, 598510015104, 8720853182976, 134778021389056, 2202055694727680, 37923940767905280, 686639853639505920, 13038833241899856896, 259119925532534413312

Offset: 0

Paul D. Hanna, Feb 02 2013

nonn

			G.f.: A(x) = 1 + 2*x + 6*x^2 + 24*x^3 + 116*x^4 + 664*x^5 + 4392*x^6 +...
where
A(x) = 1 + (2*x)*(1+x)/(1+2*x+2*x^2) + 2!*(2*x)^2*(1+x)*(1+2*x)/((1+2*x+2*x^2)*(1+4*x+8*x^2)) + 3!*(2*x)^3*(1+x)*(1+2*x)*(1+3*x)/((1+2*x+2*x^2)*(1+4*x+8*x^2)*(1+6*x+18*x^2)) + 4!*(2*x)^4*(1+x)*(1+2*x)*(1+3*x)*(1+4*x)/((1+2*x+2*x^2)*(1+4*x+8*x^2)*(1+6*x+18*x^2)*(1+8*x+32*x^2)) +...

Cf. A221987, A208237, A136127, A221973.

{a(n)=polcoeff( sum(m=0, n, m!*(2*x)^m*prod(k=1, m, (1+k*x)/(1+2*k*x+2*k^2*x^2 +x*O(x^n))) ), n)}
for(n=0, 25, print1(a(n), ", "))

A222033 G.f.: Sum_{n>=0} Product_{k=1..n} (1 - 1/(1+k*x)^3).

Original entry on oeis.org

1, 3, 12, 64, 429, 3459, 32578, 350928, 4254819, 57339343, 850210608, 13755324192, 241123857361, 4552433489355, 92097902228022, 1987543508858416, 45576279808372215, 1106640757105043895, 28364428977533987380, 765303225207132783360, 21681823874743612308981

Offset: 0

Paul D. Hanna, Feb 06 2013

nonn

Compare to the g.f. of A136127: Sum_{n>=0} Product_{k=1..n} (1 - 1/(1+k*x)^2), where A136127(n) equals the number of permutations of {1,2,...,n} having excedance set {1,2,...,k} for some k=0...n-1.

			G.f.: A(x) = 1 + 3*x + 12*x^2 + 64*x^3 + 429*x^4 + 3459*x^5 + 32578*x^6 +...
where
A(x) = 1 + (1 - 1/(1+x)^3) + (1 - 1/(1+x)^3)*(1 - 1/(1+2*x)^3) + (1 - 1/(1+x)^3)*(1 - 1/(1+2*x)^3)*(1 - 1/(1+3*x)^3) + (1 - 1/(1+x)^3)*(1 - 1/(1+2*x)^3)*(1 - 1/(1+3*x)^3)*(1 - 1/(1+4*x)^3) +...

Cf. A136127.

CoefficientList[Series[Sum[Product[1-1/(1+k x)^3,{k,n}],{n,0,20}],{x,0,20}],x] (* Harvey P. Dale, Sep 24 2021 *)

{a(n)=polcoeff(sum(m=0, n, prod(k=1, m,1-1/(1+k*x +x*O(x^n))^3)),n)}
for(n=0, 25, print1(a(n), ", "))

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A208237 G.f.: Sum_{n>=0} n! * x^n * Product_{k=1..n} (1 + k*x) / (1 + k*x + k^2*x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A216121 Irregular triangle read by rows: T(n,k) is the number of permutations in C_n (= the 1-cycles in S_n) having k stretching pairs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

Extensions

A221973 G.f.: Sum_{n>=0} n! * x^n * Product_{k=1..n} (3 + k*x)/(1 + 3*k*x + k^2*x^2).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A221988 G.f.: Sum_{n>=0} n! * (2*x)^n * Product_{k=1..n} (1 + k*x)/(1 + 2*k*x + 2*k^2*x^2).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A222033 G.f.: Sum_{n>=0} Product_{k=1..n} (1 - 1/(1+k*x)^3).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A208237 G.f.: Sum_{n>=0} n! * x^n * Product_{k=1..n} (1 + kx) / (1 + kx + k^2*x^2).

A221973 G.f.: Sum_{n>=0} n! * x^n * Product_{k=1..n} (3 + kx)/(1 + 3kx + k^2x^2).

A221988 G.f.: Sum_{n>=0} n! * (2x)^n Product_{k=1..n} (1 + kx)/(1 + 2k*x + 2k^2x^2).