cp's OEIS Frontend

A192721 The number of pairs of permutations in the product group S_n X S_n with k common descents, n >= 1 and 0 <= k <= n-1.

%I A192721 #26 Jan 05 2025 19:51:39
%S A192721 1,3,1,19,16,1,211,299,65,1,3651,7346,3156,246,1,90921,237517,160322,
%T A192721 28722,917,1,3081513,9903776,9302567,2864912,245407,3424,1,136407699,
%U A192721 520507423,632274183,288196659,46261609,2041965,12861,1
%N A192721 The number of pairs of permutations in the product group S_n X S_n with k common descents, n >= 1 and 0 <= k <= n-1.
%C A192721 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.
%C A192721 The generalized Stirling numbers associated with this triangle is A061691. See also A192722.
%H A192721 Alois P. Heinz, <a href="/A192721/b192721.txt">Rows n = 1..45, flattened</a>
%H A192721 L. Carlitz, R. Scoville and T. Vaughan, <a href="https://doi.org/10.1090/S0002-9904-1974-13554-8">Enumeration of pairs of permutations and sequences</a>, Bull. Amer. Math. Soc., 80 (1974), 881-884.
%H A192721 L. Carlitz, R. Scoville, T. Vaughan, <a href="http://dx.doi.org/10.1016/0012-365X(76)90035-2">Enumeration of pairs of permutations</a>, Discrete Math. 14, (1976) 215-239.
%H A192721 J-Marc Fedou and D. Rawlings, <a href="http://www.combinatorics.org/Volume_1/volume1.html#R11"> More statistics on permutation pairs</a>, The Electronic Journal of Combinatorics, 1 (1994) #R11.
%H A192721 M. V. Koutras, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/32-1/koutras.pdf">Eulerian numbers associated with sequences of polynomials</a>, Fibonacci Quart. 32 (1994) 44-57.
%H A192721 T. Mendes, J. Remmel, A. Riehl, <a href="http://www-circa.mcs.st-and.ac.uk/PermutationPatterns2007/abstracts/riehl.pdf">A Generalization of the Generating Functions for Descent Statistic.</a>
%H A192721 R. P. Stanley, <a href="http://dx.doi.org/10.1016/0097-3165(76)90028-5">Binomial posets, Möbius inversion and permutation enumeration</a>, J. Combinat. Theory, A 20 (1976), 336-356.
%F A192721 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).
%F A192721 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.
%F A192721 Row n sum = n!^2 = A001044(n).
%F A192721 First column [1,3,19,211,3651,...] = A000275 (apart from initial term).
%e A192721 The triangle begins
%e A192721 n/k|.....0.......1.......2......3....4.....5
%e A192721 ============================================
%e A192721 ..1|.....1
%e A192721 ..2|.....3.......1
%e A192721 ..3|....19......16.......1
%e A192721 ..4|...211.....299......65......1
%e A192721 ..5|..3651....7346....3156....246....1
%e A192721 ..6|.90921..237517..160322..28722..917.....1
%e A192721 ..
%e A192721 Row 3 entries T(3,0) = 19, T(3,1) = 16 and T(3,2) = 1 can be read from the following table:
%e A192721 ============================================
%e A192721 Number of common descents in S_3 x S_3
%e A192721 ============================================
%e A192721 .
%e A192721 ...|.123...132...213...231...312...321
%e A192721 ======================================
%e A192721 123|..0.....0.....0.....0.....0.....0
%e A192721 132|..0.....1.....0.....1.....0.....1
%e A192721 213|..0.....0.....1.....0.....1.....1
%e A192721 231|..0.....1.....0.....1.....0.....1
%e A192721 312|..0.....0.....1.....0.....1.....1
%e A192721 321|..0.....1.....1.....1.....1.....2
%e A192721 Matrix identity A192721 * A007318 = row reverse of A192722:
%e A192721 /...1................\ /..1..............\
%e A192721 |...3.....1...........||..1....1..........|
%e A192721 |..19....16.....1.....||..1....2....1.....|
%e A192721 |.211...299....65....1||..1....3....3....1|
%e A192721 |.....................||..................|
%e A192721 =
%e A192721 /...1...................\
%e A192721 |...4......1.............|
%e A192721 |..36.....18......1......|
%e A192721 |.576....432.....68.....1|
%e A192721 |........................|
%p A192721 #A192721
%p A192721 #J = sum {n>=0} z^n/n!^2
%p A192721 J := unapply(BesselJ(0, 2*I*sqrt(z)),z):
%p A192721 G := (1-x)/(-x + J(z*(x-1))):
%p A192721 Gser := simplify(series(G, z = 0, 12)):
%p A192721 for n from 1 to 10 do
%p A192721 P[n] := n!^2*sort(coeff(Gser, z, n)) od:
%p A192721 for n from 1 to 10 do seq(coeff(P[n],x,k), k = 0..n-1) od;
%p A192721 # gives sequence in triangular form
%t A192721 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 *)
%Y A192721 Cf. A000275 (first column), A001044 (row sums), A008292, A008459, A061691, A192722.
%K A192721 nonn,easy,tabl
%O A192721 1,2
%A A192721 _Peter Bala_, Jul 11 2011