A344898 Number of equivalence classes of pairs of permutations on S2n where 2 pairs are equivalent if they generate similar maps on Dyck paths.

1, 3, 154, 8369, 711226, 90349957, 16012077362, 3768789527617, 1136241039871954, 426747190631335301, 195301450278484563322, 106968871128338892427537, 69076413764424335543681642, 51931946172675368683512111589, 44964793280161619728525791864226, 44419470206051792513510236597094657

Offset

1,2

Links

Table of n, a(n) for n=1..16.

Kevin Limanta, Hopein Christofen Tang, and Yozef Tjandra, Permutation-generated maps between Dyck paths, arXiv:2105.14439 [math.CO], 2021.

Formula

a(n) = 1 - n^2 + 2*Sum_{a=1, n-1} Sum_{b=1, n-1} n!^2*(binomial(2*n-2-a-b, n-2)+binomial(2*n-2-a-b, n-1-a))/(max(a,2)!*max(b,2)!) for n>=3. - clarified by Kevin Limanta, Dec 29 2022

a(n) ~ c * 2^(2*n + 1) * n^(2*n + 1/2) / exp(2*n), where c = sqrt(Pi) * (25/16 + exp(1) - 5*exp(1/2)/2) = 0.281782323432896188420860093697452373839427854773... - Vaclav Kotesovec, Dec 29 2022

Mathematica

Join[{1, 3}, Table[1 - n^2 + 2*Sum[Sum[n!^2*(Binomial[2*n - 2 - k - j, n - 2] + Binomial[2*n - 2 - k - j, n - 1 - k])/(Max[k, 2]! * Max[j, 2]!), {k, 1, n - 1}], {j, 1, n - 1}], {n, 3, 20}]] (* Vaclav Kotesovec, Dec 29 2022 *)

Prog

(PARI) a(n) = if (n==1, 1, if (n==2, 3, 1 - n^2 + 2*sum(a=1, n-1, sum(b=1, n-1, n!^2*(binomial(2*n-2-a-b, n-2)+binomial(2*n-2-a-b, n-1-a))/(max(a, 2)!*max(b, 2)!))))); \\ corrected by Michel Marcus, Dec 29 2022

Crossrefs

Sequence in context: A378683 A156990 A075514 * A327058 A087306 A278877

Adjacent sequences: A344895 A344896 A344897 * A344899 A344900 A344901

Keyword

nonn

Author

Michel Marcus, Jun 01 2021

Extensions

Offset 1 from Vaclav Kotesovec, Dec 29 2022

Status

approved