A046739 Triangle read by rows, related to number of permutations of [n] with 0 successions and k rises.

0, 1, 1, 1, 1, 7, 1, 1, 21, 21, 1, 1, 51, 161, 51, 1, 1, 113, 813, 813, 113, 1, 1, 239, 3361, 7631, 3361, 239, 1, 1, 493, 12421, 53833, 53833, 12421, 493, 1, 1, 1003, 42865, 320107, 607009, 320107, 42865, 1003, 1, 1, 2025, 141549, 1704693, 5494017

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• tabf

Comments

From Emeric Deutsch, May 25 2009: (Start)

T(n,k) is the number of derangements of [n] having k excedances. Example: T(4,2)=7 because we have 3*14*2, 3*4*12, 4*3*12, 2*14*3, 2*4*13, 3*4*21, 4*3*21, each with two excedances (marked). An excedance of a permutation p is a position i such that p(i) > i.

Sum_{k>=1} k*T(n,k) = A000274(n+1). (End)

The triangle 1;1,1;1,7,1;... has general term T(n,k) = Sum_{j=0..n+2} (-1)^(n-j)*C(n+2,j)*A123125(j,k+2) and bivariate g.f. ((1-y)*(y*exp(2*x*y) + exp(x*(y+1))(y^2 - 4*y + 1) + y*exp(2*x)))/(exp(x*y) - y*exp(x))^3. - Paul Barry, May 10 2011

The n-th row is the local h-vector of the barycentric subdivision of a simplex, i.e., the Coxeter complex of type A. See Proposition 2.4 of Stanley's paper below. - Kyle Petersen, Aug 20 2012

T(n,k) is the k-th coefficient of the local h^*-polynomial, or box polynomial, of the s-lecture hall n-simplex with s=(2,3,...,n+1). See Theorem 4.1 of the paper by N. Gustafsson and L. Solus below. - Liam Solus, Aug 23 2018

Examples

			Triangle starts:
  0;
  1;
  1,   1;
  1,   7,   1;
  1,  21,  21,   1;
  1,  51, 161,  51,   1;
  1, 113, 813, 813, 113, 1;
  ...
From _Peter Luschny_, Sep 17 2021: (Start)
The triangle shows the coefficients of the following bivariate polynomials:
  [1] 0;
  [2] x*y;
  [3] x^2*y +     x*y^2;
  [4] x^3*y +   7*x^2*y^2 +     x*y^3;
  [5] x^4*y +  21*x^3*y^2 +  21*x^2*y^3 +     x*y^4;
  [6] x^5*y +  51*x^4*y^2 + 161*x^3*y^3 +  51*x^2*y^4 +     x*y^5;
  [7] x^6*y + 113*x^5*y^2 + 813*x^4*y^3 + 813*x^3*y^4 + 113*x^2*y^5 + x*y^6;
  ...
These polynomials are the permanents of the n X n matrices with all entries above the main antidiagonal set to 'x' and all entries below the main antidiagonal set to 'y'. The main antidiagonals consist only of zeros. Substituting x <- 1 and y <- -1 generates the Euler secant numbers A122045. (Compare with A081658.)
(End)
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10012 (rows 0 to 142, flattened)
• L. Carlitz, Richard Scoville, and Theresa Vaughan, Enumeration of pairs of permutations and sequences, Bulletin of the American Mathematical Society 80.5 (1974): 881-884. [Annotated scanned copy]
• L. Carlitz, N. J. A. Sloane, and C. L. Mallows, Correspondence, 1975
• N. Gustafsson and L. Solus. Derangements, Ehrhart theory, and local h-polynomials, arXiv:1807.05246 [math.CO], 2018.
• R. Mantaci and F. Rakotondrajao, Exceedingly deranging!, Advances in Appl. Math., 30 (2003), 177-188. [_Emeric Deutsch_, May 25 2009]
• Lili Mu and Volkmar Welker, On a question about real rooted polynomials and f-polynomials of simplicial complexes, arXiv:2503.24076 [math.CO], 2025. See p. 8.
• D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 8-16. [Annotated scanned copy]
• D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 20 (1968), 8-16.
• R. P. Stanley, Subdivisions and local h-vectors, J. Amer. Math. Soc., 5 (1992), 805-851.
• John D. Wiltshire-Gordon, Alexander Woo, and Magdalena Zajaczkowska, Specht Polytopes and Specht Matroids, arXiv:1701.05277 [math.CO], 2017. [See Conjecture 6.2]

Crossrefs

Cf. A046740.

Row sums give A000166.

Diagonals give A070313, A070315.

T(2n,n) gives A320337.

Cf. A000274, A081658, A122045, A271697.

Programs

Maple

G := (1-t)*exp(-t*z)/(1-t*exp((1-t)*z)): Gser := simplify(series(G, z = 0, 15)): for n to 13 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: 0; for n to 11 do seq(coeff(P[n], t, j), j = 1 .. n-1) end do; # yields sequence in triangular form # Emeric Deutsch, May 25 2009

Mathematica

max = 12; f[t_, z_] := (1-t)*(Exp[-t*z]/(1 - t*Exp[(1-t)*z])); se = Series[f[t, z], {t, 0, max}, {z, 0, max}];
coes = Transpose[ #*Range[0, max]! & /@ CoefficientList[se, {t, z}]]; Join[{0}, Flatten[ Table[ coes[[n, k]], {n, 2, max}, {k, 2, n-1}]]] (* Jean-François Alcover, Oct 24 2011, after g.f. *)
E1[n_ /; n >= 0, 0] = 1; (* E1(n,k) are the Eulerian numbers *)
E1[n_, k_] /; k < 0 || k > n = 0;
E1[n_, k_] := E1[n, k] = (n-k) E1[n-1, k-1] + (k+1) E1[n-1, k];
T[n_, k_] := Sum[Binomial[-j-1, -n-1] E1[j, k], {j, 0, n}];
Table[T[n, k], {n, 1, 100}, {k, 1, n-1}] /. {} -> {0} // Flatten (* Jean-François Alcover, Oct 31 2020, after Peter Luschny in A271697 *)
Table[Expand[n!Factor[SeriesCoefficient[(x-y)/(x Exp[y t]-y Exp[x t]),{t,0,n}]]],{n,0,12}]//TableForm (* Mamuka Jibladze, Nov 26 2024 *)

PARI

T(n)={my(x='x+O('x^(n+1))); concat([[0]], [Vecrev(p/y) | p<-Vec(-1+serlaplace((y-1)/(y*exp(x)-exp(x*y))))])}
{ my(A=T(10));for(i=1,#A,print(A[i])) } \\ Andrew Howroyd, Nov 13 2024

Formula

a(n+1, r) = r*a(n, r) + (n+1-r)*a(n, r-1) + n*a(n-1, r-1).

exp(-t)/(1 - exp((x-1)t)/(x-1)) = 1 + x*t^2/2! + (x+x^2)*t^3/3! + (x+7x^2+x^3)*t^4/4! + (x+21x^2+21x^3+x^4)*t^5/5! + ... - Philippe Deléham, Jun 11 2004

E.g.f.: (y-1)/(y*exp(x) - exp(x*y)). - Mamuka Jibladze, Nov 08 2024

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000