1,2

Let S_n denote the symmetric group on {1,2,...,n}. A permutation p_1p_2...p_n in S_n has a descent at position i (1 <= i <= n-1) if p_i > p_(i+1). The Eulerian numbers A008292 (with an offset of 0 in the column indexing) enumerate permutations by descents. We define a pair of permutations p_1p_2...p_n and q_1q_2...q_n to have a common descent at position i (1 <= i <= n-1) if both p_i > p_(i+1) and q_i > q_(i+1). For example, the permutations (3241) and (4231) in S_4 have common descents at positions i = 1 and i = 3. The table entry T(n,k) gives the number of pairs of permutations in the Cartesian product S_n x S_n with k common descents.

The generalized Stirling numbers associated with this triangle is A061691. See also A192722.

Alois P. Heinz, Rows n = 1..45, flattened

L. Carlitz, Richard Scoville, and Theresa Vaughan, Enumeration of pairs of permutations and sequences, Bull. Amer. Math. Soc., 80 (1974), 881-884.

L. Carlitz, Richard Scoville, and Theresa Vaughan, Enumeration of pairs of permutations, Discrete Math. 14 (1976), 215-239.

Jean-Marc Fedou and Don Rawlings, More statistics on permutation pairs, The Electronic Journal of Combinatorics, 1 (1994) #R11.

M. V. Koutras, Eulerian numbers associated with sequences of polynomials, Fibonacci Quart. 32 (1994) 44-57.

T. Mendes, J. Remmel, A. Riehl, A Generalization of the Generating Functions for Descent Statistic. [broken link]

Richard P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinat. Theory, A 20 (1976), 336-356.

Generating function (Carlitz et al. 1976): Let J(z) = Sum_{n >= 0} z^n/n!^2. Then (1 - x)/(J(z*(x - 1)) - x) = 1 + Sum_{n >= 1} (Sum_{k = 0..n-1} T(n,k)*x^k)*z^n/n!^2 = 1 + z + (3 + x)*z^2/2!^2 + (19 + 16*x + x^2)*z^3/3!^2 + ....

Define a polynomial sequence {p(n,x)}n>=0 by means of the generating function J(z)^x = Sum_{n>=0} p(n,x)*z^n/n!^2. The generalized Eulerian polynomials associated with the sequence {p(n,x)} as defined by [Koutras, 1994] are the polynomials Sum_{k = 0..n-1} T(n,k)*x^(n-k).

Relations with other sequences: The first column of the array (x*I - A008459)^(-1) (I the identity matrix) is a sequence of rational functions whose numerator polynomials are the row generating polynomials for the present triangle. The change of variable x -> (x + 1)/x followed by z -> x*z transforms the above bivariate generating function (1 - x)/(J(z*(x - 1)) - x) into 1/(1 + x - x*J(z)), which is the generating function for A192722. Equivalently, if we postmultiply the present triangle by Pascal's triangle A007318 we obtain the row reversed form of A192722: A192721 * A007318 = row reverse of A192722.

Row n sum = n!^2 = A001044(n).

First column [1, 3, 19, 211, 3651, ...] = A000275 (apart from initial term).

The triangle begins

n/k|.....0.......1.......2......3....4.....5

============================================

..1|.....1

..2|.....3.......1

..3|....19......16.......1

..4|...211.....299......65......1

..5|..3651....7346....3156....246....1

..6|.90921..237517..160322..28722..917.....1

..

Row 3 entries T(3,0) = 19, T(3,1) = 16 and T(3,2) = 1 can be read from the following table:

============================================

Number of common descents in S_3 x S_3

============================================

.

...|.123...132...213...231...312...321

======================================

123|..0.....0.....0.....0.....0.....0

132|..0.....1.....0.....1.....0.....1

213|..0.....0.....1.....0.....1.....1

231|..0.....1.....0.....1.....0.....1

312|..0.....0.....1.....0.....1.....1

321|..0.....1.....1.....1.....1.....2

Matrix identity A192721 * A007318 = row reverse of A192722:

/...1................\ /..1..............\

|...3.....1...........||..1....1..........|

|..19....16.....1.....||..1....2....1.....|

|.211...299....65....1||..1....3....3....1|

|.....................||..................|

=

/...1...................\

|...4......1.............|

|..36.....18......1......|

|.576....432.....68.....1|

|........................|

#A192721

#J = sum {n>=0} z^n/n!^2

J := unapply(BesselJ(0, 2*I*sqrt(z)), z):

G := (1-x)/(-x + J(z*(x-1))):

Gser := simplify(series(G, z = 0, 12)):

for n from 1 to 10 do

P[n] := n!^2*sort(coeff(Gser, z, n)) od:

for n from 1 to 10 do seq(coeff(P[n], x, k), k = 0..n-1) od;

# gives sequence in triangular form

max = 9; j[z_] := BesselJ[0, 2 I*Sqrt[z]]; g = (1 - x)/(-x + j[z*(x - 1)]); gser = Series[g, {z, 0, max}]; p[n_] := n!^2 Coefficient[ gser, z, n]; a[n_, k_] := Coefficient[ p[n], x, k]; Flatten[ Table[ a[n, k], {n, 1, max-1}, {k, 0, n-1}]] (* Jean-François Alcover, Dec 13 2011, after Maple *)

Cf. A000275 (first column), A001044 (row sums), A008292, A008459, A061691, A192722.

Sequence in context: A147076 A372175 A027537 * A370949 A002380 A274075

Adjacent sequences: A192718 A192719 A192720 * A192722 A192723 A192724

nonn,easy,tabl

Peter Bala, Jul 11 2011

approved