A192722 -id:A192722 - cp's OEIS frontend

A102221 Column 0 of triangular matrix A102220, which equals [2*I - A008459]^(-1).

1, 1, 5, 55, 1077, 32951, 1451723, 87054773, 6818444405, 675900963271, 82717196780955, 12248810651651333, 2158585005685222491, 446445657799551807541, 107087164031952038620481, 29487141797206760561836055, 9238158011747884080353808245

Offset: 0

Paul D. Hanna, Dec 31 2004

nonn

a(n) is the number of ways to form an ordered pair of n-permutations and then choose a subset of its common descent set. Cf. A192721. - Geoffrey Critzer, Apr 29 2023

Alois P. Heinz, Table of n, a(n) for n = 0..248

Cf. A000275, A008459, A102220, A102222, A192721.
Row sums of A192722.
Column k=2 of A326322.

b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-i)*binomial(n, i)/i!, i=1..n))
    end:
a:= n-> b(n)*n!:
seq(a(n), n=0..20);  # Alois P. Heinz, May 11 2016

Rest[CoefficientList[Series[1/(2-BesselJ[0, 2*I*Sqrt[x]]), {x, 0, 20}], x] * Range[0, 20]!^2] (* Vaclav Kotesovec, Mar 02 2014 *)
m = 20; CoefficientList[1/(2 - BesselI[0, 2 Sqrt[x]]) + O[x]^m, x] Range[0, m - 1]!^2 (* Jean-François Alcover, Jun 11 2019, after Vladeta Jovovic *)
b[n_] := b[n] = If[n==0, 1, Sum[b[n-i] Binomial[n, i]/i!, {i, 1, n}]];
a[n_] := b[n] n!;
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2020, after Alois P. Heinz *)

a(n)=if(n==0,1,sum(k=0,n-1,binomial(n,k)^2*a(k)))

L = taylor(1/(1-x*hypergeometric((1,),(2,2),x)),x,0,14).list()
[factorial(i)^2*c for (i,c) in enumerate(L)] # Peter Luschny, Jul 28 2015

a(n) = Sum_{k=0..n-1} C(n, k)^2*a(k) for n>0, with a(0)=1.
a(n) = A102220(n+k, k)/C(n+k, k)^2 for k>=0.
Sum_{n>=0} a(n)*x^n/n!^2 = 1/(2-BesselI(0,2*sqrt(x))). - Vladeta Jovovic, Jul 17 2006
a(n) ~ c * (n!)^2 / r^n, where r = 0.81712266563155429332453954757369795... is the root of the equation BesselJ(0, 2*I*sqrt(x))=2, and c = 0.833570458821600548332410448635741072476086046022299770387... = 1/(sqrt(r) * BesselI(1, 2*sqrt(r))). - Vaclav Kotesovec, Mar 02 2014, updated Apr 01 2018
From Geoffrey Critzer, Apr 29 2023: (Start)
Sum_{n>=0} a(n)*z^n/(n!)^2 = 1/(2-E(z)) where E(z) = Sum_{n>=0} z^n/(n!)^2.
a(n) = Sum_{k=0..n-1} A192721(n,k)*2^k. (End)

Content moved from A192723 to this sequence by Alois P. Heinz, Sep 11 2019

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.

Original entry on oeis.org

1, 3, 1, 19, 16, 1, 211, 299, 65, 1, 3651, 7346, 3156, 246, 1, 90921, 237517, 160322, 28722, 917, 1, 3081513, 9903776, 9302567, 2864912, 245407, 3424, 1, 136407699, 520507423, 632274183, 288196659, 46261609, 2041965, 12861, 1

Offset: 1

Peter Bala, Jul 11 2011

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.

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

Alois P. Heinz, Rows n = 1..45, flattened
L. Carlitz, R. Scoville and T. Vaughan, Enumeration of pairs of permutations and sequences, Bull. Amer. Math. Soc., 80 (1974), 881-884.
L. Carlitz, R. Scoville, T. Vaughan, Enumeration of pairs of permutations, Discrete Math. 14, (1976) 215-239.
J-Marc Fedou and D. 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.
R. P. Stanley, Binomial posets, Möbius inversion and permutation enumeration, J. Combinat. Theory, A 20 (1976), 336-356.

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

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

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

A061691 Triangle of generalized Stirling numbers.

Original entry on oeis.org

1, 1, 2, 1, 9, 6, 1, 34, 72, 24, 1, 125, 650, 600, 120, 1, 461, 5400, 10500, 5400, 720, 1, 1715, 43757, 161700, 161700, 52920, 5040, 1, 6434, 353192, 2361016, 4116000, 2493120, 564480, 40320, 1, 24309, 2862330, 33731208, 96960024, 97161120, 39372480, 6531840, 362880

Offset: 1

N. J. A. Sloane, Jun 18 2001

The Eulerian-type number triangle associated with this triangle of generalized Stirling numbers is A192721. The table entry T(n,k) gives the number of uniform block permutations of the set {1,2,...,n} partitioned into k blocks. An example is given below. T(n,k) also gives the number of games of simple patience with n cards resulting in k piles (adapt Algorithm 1.1.22 of Lankham). [Peter Bala, Jul 14 2011]

			Triangle begins:
  1;
  1,2;
  1,9,6;
  1,34,72,24;
  1,125,650,600,120;
  ...
T(4,2) = 34:
There are 7 partitions of the set {1,2,3,4} into 2 blocks. The four partitions {1,2,3}{4}, {1,2,4}{3}, {1,3,4}{2} and {2,3,4}{1} give rise to 4*4 = 16 uniform block permutations while the remaining 3 partitions {1,2}{3,4}, {1,3}{2,4} and {1,4}{2,3} give 2!*3*3 = 18 uniform block permutations : thus in total there are 16+18 = 34 block permutations between the set partitions of {1,2,3,4} into 2 blocks.

Alois P. Heinz, Rows n = 1..141, flattened
M. Aguiar and R. C. Orellana, The Hopf algebra of uniform block permutations, 17th International Conference on Formal Power Series and Algebraic Combinatorics, Taormina, July 2005.
D. Aldous and P. Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. 36 (1999), 413-432.
D. G. Fitzgerald, A presentation for the monoid of uniform block permutations, Bull. Austral. Math. Soc. 68 (2003), 317-324.
A. T. Irish, F. Quitin, U. Madhow, and M. Rodwell, Achieving multiple degrees of freedom in long-range mm-wave MIMO channels using randomly distributed relays, 2014.
I. P. Lankham, Patience Sorting and Its Generalizations, arXiv:0705.4524 [math.CO], 2007.
J.-M. Sixdeniers, K. A. Penson and A. I. Solomon, Extended Bell and Stirling Numbers From Hypergeometric Exponentiation, J. Integer Seqs. Vol. 4 (2001), #01.1.4.

Diagonals give A010763, A061690, A000142, A001809, A061689. Cf. A061692. A023998 (row sums), A192721, A192722.

#A061691
#J = sum {n>=0} z^n/n!^2
J := BesselJ(0, 2*i*sqrt(z)):
G := exp(x*(J(z)-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 = 1..n) od;
# yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1,
      add(x*b(n-i)*binomial(n, i)/i!, i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i)/i!, i=1..n))(b(n)*n!):
seq(T(n), n=1..12);  # Alois P. Heinz, Sep 10 2019

max = 9; g := Exp[x*(BesselI[0, 2*Sqrt[z]] - 1)]; gser = Series[g, {z, 0, max}, {x, 0, max}]; t[n_, k_] := n!^2*SeriesCoefficient[ gser // Normal, {z, 0, n}, {x, 0, k}]; Flatten[ Table[ t[n, k], {n, 1, max}, {k, 1, n}]] (* Jean-François Alcover, Apr 04 2012, after Maple *)

T(n, k) = 1/k!*Sum multinomial(n, n_1, n_2, ..n_k)^2, where the sum extends over all compositions (n_1, n_2, .., n_k) of n into exactly k nonnegative parts. - Vladeta Jovovic, Apr 23 2003
From Peter Bala, Jul 14 2011: (Start)
The table entry T(n,k) may also be expressed as a sum over (unordered) partitions of n into k parts:
T(n,k) = sum {partitions m_1*1+...+m_n*n = n, m_1+...+m_n = k} 1/(m_1!*...*m_n!)*{n!/(1!^(m_1)*...*n!^(m_n))}^2.
Generating function:
Let J(z) = sum {n>=0} z^n/n!^2. Then
exp(x*(J(z)-1)) = 1 + x*z + (x + 2*x^2)*z^2/2!^2 + (x + 9*x^2 + 6*x^3)*z^3/3!^2 + ....
Relations with other sequences:
T(n,k) = 1/k!*A192722(n,k).
Row sums [1,3,16,131,...] = A023998. (End)
The row polynomials R(n,x) satisfy the recurrence equation R(n,x) = x*( sum {k = 0..n-1} binomial(n,k)*binomial(n-1,k)*R(k,x) ) with R(0,x) = 1. Also R(n,x + y) = sum {k = 0..n} binomial(n,k)^2*R(k,x)*R(n-k,y). - Peter Bala, Sep 17 2013

More terms from Vladeta Jovovic, Apr 23 2003

cp's OEIS Frontend

A102221 Column 0 of triangular matrix A102220, which equals [2*I - A008459]^(-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A061691 Triangle of generalized Stirling numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions