login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A046739 Triangle read by rows, related to number of permutations of [n] with 0 successions and k rises. 14
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

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

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]

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, Magdalena Zajaczkowska. Specht Polytopes and Specht Matroids. arXiv:1701.05277 [math.CO], 2017. [See Conjecture 6.2]

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

EXAMPLE

Triangle starts:

  0;

  1;

  1,   1;

  1,   7,   1;

  1,  21,  21,   1;

  1,  51, 161,  51,   1;

  ...

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

CROSSREFS

Cf. A046740. Row sums give A000166. Diagonals give A070313, A070315.

Cf. A000274. - Emeric Deutsch, May 25 2009

Sequence in context: A119727 A157272 A176200 * A056752 A053714 A168290

Adjacent sequences:  A046736 A046737 A046738 * A046740 A046741 A046742

KEYWORD

nonn,easy,nice,tabf

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 16 11:12 EDT 2019. Contains 324152 sequences. (Running on oeis4.)