A177267 -id:A177267 - cp's OEIS frontend

A060593 a(n) is the number of ways that a cycle of length 2n+1 in the symmetric group S_(2n+1) can be decomposed as the product of two cycles of length 2n+1.

1, 1, 8, 180, 8064, 604800, 68428800, 10897286400, 2324754432000, 640237370572800, 221172909834240000, 93666727314800640000, 47726800133326110720000, 28806532937614688256000000, 20325889640780924033433600000, 16578303738261941164769280000000

Offset: 0

Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001

The sequence deals only with S_m for odd m because for even m the number of representations of an m-cycle in S_m as a product of two m-cycles is zero.
a(n) = product of first 2n-1 numbers divided by their sum. E.g., a(3) = (1*2*3*4*5)/(1+2+3+4+5) = 120/15 = 8. - Amarnath Murthy, Jun 03 2004
a(n) is also the number of permutations in Sym(2n) whose "cycle graph" (or "breakpoint graph") contains exactly one alternating cycle, for n>=1 (see Doignon and Labarre). - Anthony Labarre, Jun 19 2007

			a(1) = 1 because in S_3 the only way to write the cycle (123) as a product of two 3-cycles is: (123) = (132)(132).

Harry J. Smith, Table of n, a(n) for n = 0..100
G. Boccara, Nombre de représentations d'une permutation comme produit de deux cycles de longueurs données, Discrete Math., Vol. 29, No. 2 (1980), pp. 105-134.
Jean-Paul Doignon and Anthony Labarre, On Hultman Numbers, J. Integer Seq., Vol. 10 (2007), Article 07.6.2, 13 pages.
Ivan V. Morozov, On Quotients of a More General Theorem of Wilson, arXiv:2505.16201 [math.NT], 2025. See Z p. 9. Z(2*n+1)=1+a(n), Z(2n)=1.
Karol A. Penson and J.-M. Sixdeniers, Integral Representations of Catalan and Related Numbers, J. Integer Sequences, Vol. 4 (2001), Article 01.2.5.
Karol A. Penson and Allan I. Solomon, Coherent states from combinatorial sequences, arXiv:quant-ph/0111151, 2001.

Cf. A090586, A177267.

for n from 0 to 25 do printf(`%d,`,(2*n)!/(n+1)) od:

Table[(2*n)!/(n + 1), {n, 0, 13}] (* Amiram Eldar, Feb 08 2022 *)

a(n) = (2*n)! / (n + 1); \\ Harry J. Smith, Jul 07 2009

a(n) = (2n)! / (n+1).
Integral representation as n-th moment of a positive function on positive half-axis, in Maple notation: a(n)=int(x^n*(exp(-sqrt(x))/sqrt(x)+Ei(-sqrt(x))), x=0..infinity), n=0, 1, 2, ..., where Ei(y) is the exponential integral. This representation is unique. - Karol A. Penson, Aug 27 2001
a(n) = n!^2*binomial(2*n,n)/(n+1). - Zerinvary Lajos, Jun 06 2006
a(n) = A090586(2*n + 1). - Gregory Gerard Wojnar, Jun 10 2021
From Amiram Eldar, Feb 08 2022: (Start)
Sum_{n>=0} 1/a(n) = cosh(1) + sinh(1)/2.
Sum_{n>=0} (-1)^n/a(n) = cos(1) - sin(1)/2. (End)
From Wolfdieter Lang, Feb 02 2024: (Start)
O.g.f.: hypergeometric([1,1,1,1/2],[2],4*x).
E.g.f.: hypergeometric([1,1,1/2],[2],4*x). (End)
a(n) = A177267(2n+1,n). - Alois P. Heinz, Feb 16 2024
D-finite with recurrence (n+1)*a(n) -2*n^2*(2*n-1)*a(n-1)=0. - R. J. Mathar, May 26 2025

More terms from James Sellers, Apr 13 2001

A178514 Triangle read by rows: T(n,k) is the number of derangements of {1,2,...,n} having genus k (see first comment for definition of genus).

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 3, 6, 0, 0, 6, 30, 8, 0, 0, 15, 130, 120, 0, 0, 0, 36, 525, 1113, 180, 0, 0, 0, 91, 2016, 8078, 4648, 0, 0, 0, 0, 232, 7476, 50316, 67408, 8064, 0, 0, 0, 0, 603, 27000, 281862, 719640, 305856, 0, 0, 0, 0, 0, 1585, 95535, 1459920, 6298930, 6223800, 604800, 0

Offset: 1

Emeric Deutsch, May 29 2010

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p) = (1/2)(n + 1 - z(p) - z(cp')), where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
The sum of the entries in row n is A000166(n) (the derangement numbers).
The number of entries in row n is ceiling(n/2).
T(n,0) = A005043(n) (the Riordan numbers).

			T(3,1)=1 because 312 is the only derangement of {1,2,3} with genus 1. Indeed, we have p=312=(132), cp'=231*231=312=(132) and so g(p) = (1/2)*(3+1-1-1) = 1, while for the other derangement of {1,2,3}, q=231=(123), we have cq'=231*312=123=(1)(2)(3) and so g(q) = (1/2)*(3+1-1-3) = 0.
Triangle starts:
[ 1]    0,
[ 2]    1,      0,
[ 3]    1,      1,       0,
[ 4]    3,      6,       0,        0,
[ 5]    6,     30,       8,        0,        0,
[ 6]   15,    130,     120,        0,        0,        0,
[ 7]   36,    525,    1113,      180,        0,        0, 0,
[ 8]   91,   2016,    8078,     4648,        0,        0, 0, 0,
[ 9]  232,   7476,   50316,    67408,     8064,        0, 0, 0, 0,
[10]  603,  27000,  281862,   719640,   305856,        0, 0, 0, 0, 0,
[11] 1585,  95535, 1459920,  6298930,  6223800,   604800, 0, 0, 0, 0, 0,
[12] 4213, 332530, 7117902, 47851540, 90052336, 30856320, 0, 0, 0, 0, 0, 0,
...

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.

Cf. A177267.

Cf. A000166, A005043.

n := 7: with(combinat): P := permute(n): inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc: nrcyc := proc (p) local pc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc: DER := {}: for i to factorial(n) do if nrfp(P[i]) = 0 then DER := `union`(DER, {P[i]}) else end if end do: f[n] := sort(add(t^gen(DER[j]), j = 1 .. nops(DER))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries of the specified row n

Terms beyond row 7 from Joerg Arndt, Nov 01 2012

A178515 Triangle read by rows: T(n,k) is the number of involutions of {1,2,...,n} having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 2, 0, 4, 0, 0, 9, 1, 0, 0, 21, 5, 0, 0, 0, 51, 25, 0, 0, 0, 0, 127, 105, 0, 0, 0, 0, 0, 323, 420, 21, 0, 0, 0, 0, 0, 835, 1596, 189, 0, 0, 0, 0, 0, 0, 2188, 5880, 1428, 0, 0, 0, 0, 0, 0, 0, 5798, 21120, 8778, 0, 0, 0, 0, 0, 0, 0, 0, 15511, 74415, 48741, 1485, 0, 0, 0, 0, 0, 0, 0, 0, 41835, 258115, 249249, 19305, 0

Offset: 1

Emeric Deutsch, May 29 2010

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
The sum of the entries in row n is A000085(n).
T(n,0)=A001006(n) (the Motzkin numbers).

			T(4,1)=1 because p=3412 is the only involution of {1,2,3,4} with genus 1. This follows easily from the fact that a permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference). [Also, for p=3412=(13)(24) we have cp'=2341*3412=4123=(1432) and so g(p)=(1/2)(4+1-2-1)=1.]
Triangle starts:
[ 1]  1,
[ 2]  2, 0,
[ 3]  4, 0, 0,
[ 4]  9, 1, 0, 0,
[ 5]  21, 5, 0, 0, 0,
[ 6]  51, 25, 0, 0, 0, 0,
[ 7]  127, 105, 0, 0, 0, 0, 0,
[ 8]  323, 420, 21, 0, 0, 0, 0, 0,
[ 9]  835, 1596, 189, 0, 0, 0, 0, 0, 0,
[10]  2188, 5880, 1428, 0, 0, 0, 0, 0, 0, 0,
[11]  5798, 21120, 8778, 0, 0, 0, 0, 0, 0, 0, 0,
[12]  15511, 74415, 48741, 1485, 0, 0, 0, 0, 0, 0, 0, 0,
[13]  41835, 258115, 249249, 19305, 0, 0, 0, 0, 0, 0, 0, 0, 0,
[14]  113634, 883883, 1201200, 191763, 0, 0, 0, 0, 0, 0, 0, ...,
[15]  310572, 2994355, 5519514, 1525095, 0, 0, 0, 0, 0, 0, 0, ...,
[16]  853467, 10051860, 24408384, 10667800, 225225, 0, 0, 0, ...,
[17]  2356779, 33479460, 104552448, 67581800, 3828825, 0, 0, ...,
...

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.

Cf. A177267.

Cf. A000085, A001006.

n := 8: with(combinat): P := permute(n): inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc: nrcyc := proc (p) local pc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc; INV := {}: for i to factorial(n) do if inv(P[i]) = P[i] then INV := `union`(INV, {P[i]}) else end if end do: f[n] := sort(add(t^gen(INV[j]), j = 1 .. nops(INV))): seq(coeff(f[n], t, j), j = 0 .. degree(f[n])); # yields the entries of the specified row n

Terms beyond row 7 from Joerg Arndt, Nov 01 2012.

A370235 Table read by rows. Number of set partitions of [n] with respect to genus g.

Original entry on oeis.org

1, 1, 2, 5, 14, 1, 42, 10, 132, 70, 1, 429, 420, 28, 1430, 2310, 399, 1, 4862, 12012, 4179, 94, 16796, 60060, 36498, 2620, 1, 58786, 291720, 282282, 45430, 352, 208012, 1385670, 1999998, 600655, 19261, 1, 742900, 6466460, 13258674, 6633484, 541541, 1378

Offset: 0

Peter Luschny, Feb 15 2024

The table shows the number of partitions of [n] = {1, 2, 3, ..., n} with genus g.
The set of noncrossing partitions is exactly the set of genus zero partitions. The numbers corresponding to this case are the Catalan numbers.
This is essentially table 2.1 in Martha Yip's thesis (p. 12).
From Robert Coquereaux, Feb 16 2024: (Start)
The two-dimensional array is called triangle of genus-dependent Bell numbers B(n, g); if n >= 1, n even, nonzero values are obtained for 0 <= g <= floor((n-1)/2); if n >= 1, odd, nonzero values are obtained for 0 <= g < (n-1)/2.
The two-dimensional array B(n, g) can be obtained from a three-dimensional array S2(n, k, g), by summation over the number k of blocks. The numbers S2(n, k, g) are genus-dependent Stirling numbers of the second kind. They give the number of genus g partitions of the n-set which are partitions into k nonempty subsets (blocks). The numbers S2(n, k, g) are discussed in A370420.
(End)

			[n\g]     0        1        2      3      4     5
-------------------------------------------------
[ 0]      1;
[ 1]      1;
[ 2]      2;
[ 3]      5;
[ 4]     14,       1;
[ 5]     42,      10;
[ 6]    132,      70,        1;
[ 7]    429,     420,       28;
[ 8]   1430,    2310,      399,       1;
[ 9]   4862,   12012,     4179,      94;
[10]  16796,   60060,    36498,    2620,      1;
[11]  58786,  291720,   282282,   45430,    352;
[12] 208012, 1385670,  1999998,  600655,  19261,    1;
[13] 742900, 6466460, 13258674, 6633484, 541541, 1378;

Robert Coquereaux, Table of n, a(n) for n = 0..57 (rows 0..15)
Martha Yip, Genus one partitions, Master Thesis, University of Waterloo, 2006. [Typos in Table 2.1 in positions T(8, 0) and T(10, 0)].
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 4, 5, 22. Also in JIS, Journal of Integer Sequences, Vol. 27 (2024), Article 24.2.6. See p. 8, 9, 10, 32.

Columns: A000108 (g=0), A002802 (g=1), A297179 (g=2), A370237 (g=3).
Cf. A000110 (row sums), A177267 (permutations by genus).
Cf. A001263, A370236, A297178.
Cf. A370420 (S2(n,k,g)).

A178516 Triangle read by rows: T(n,k) is the number of up-down permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 1, 0, 2, 0, 0, 2, 3, 0, 0, 6, 10, 0, 0, 0, 6, 38, 17, 0, 0, 0, 22, 142, 104, 4, 0, 0, 0, 22, 351, 778, 234, 0, 0, 0, 0, 90, 1419, 4086, 2235, 106, 0, 0, 0, 0, 90, 2856, 17402, 24357, 5816, 0, 0, 0, 0, 0, 394, 12208, 87434, 171305, 78705, 3746, 0, 0, 0, 0, 0, 394, 21676, 278062, 1053425, 1120648, 228560, 0

Offset: 1

Emeric Deutsch, May 29 2010

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p) = (1/2)*(n + 1 - z(p) - z(cp')), where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
The sum of the entries in row n is A000111(n) (Euler or up-down numbers).
Apparently, row n contains ceiling(n/2) nonzero entries.
T(2n-1,0) = T(2n,0) = A006318(n-1) (the large Schroeder numbers).

			T(4,0)=2. From the fact that a permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference), it follows that the up-down permutations 2314 = (123)(4) and 1324 = (1)(23)(4) have genus 0, while 2413 = (1243), 3412 = (13)(24), and 1423 = (1)(243) do not.
Triangle starts:
[ 1]   1,
[ 2]   1,     0,
[ 3]   2,     0,      0,
[ 4]   2,     3,      0,       0,
[ 5]   6,    10,      0,       0,       0,
[ 6]   6,    38,     17,       0,       0,      0,
[ 7]  22,   142,    104,       4,       0,      0, 0,
[ 8]  22,   351,    778,     234,       0,      0, 0, 0,
[ 9]  90,  1419,   4086,    2235,     106,      0, 0, 0, 0,
[10]  90,  2856,  17402,   24357,    5816,      0, 0, 0, 0, 0,
[11] 394, 12208,  87434,  171305,   78705,   3746, 0, 0, 0, 0, 0,
[12] 394, 21676, 278062, 1053425, 1120648, 228560, 0, 0, 0, 0, 0, 0,
...

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.

Cf. A177267.

Cf. A000111, A006318, A169816.

n := 7: with(combinat): descents := proc (p) local A, i: A := {}: for i to nops(p)-1 do if p[i+1] < p[i] then A := `union`(A, {i}) else end if end do: A end proc; UD := proc (n) local ud, P, j: ud := {}: P := permute(n): for j to factorial(n) do if descents(P[j]) = {seq(2*k, k = 1 .. ceil((1/2)*n)-1)} then ud := `union`(ud, {P[j]}) else end if end do: ud end proc; inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc:
pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc: f[n] := sort(add(t^gen(UD(n)[j]), j = 1 .. nops(UD(n)))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries in the specified row n

Terms beyond row 7 from Joerg Arndt, Nov 01 2012

A178517 Triangle read by rows: T(n,k) is the number of non-derangement permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 1, 0, 4, 0, 0, 11, 4, 0, 0, 36, 40, 0, 0, 0, 117, 290, 48, 0, 0, 0, 393, 1785, 1008, 0, 0, 0, 0, 1339, 9996, 12712, 1440, 0, 0, 0, 0, 4630, 52584, 123858, 48312, 0, 0, 0, 0, 0, 16193, 264720, 1027446, 904840, 80640, 0, 0, 0, 0, 0, 57201, 1290135, 7627158, 12449800, 3807936, 0

Offset: 1

Emeric Deutsch, May 30 2010

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
The sum of the entries in row n is A002467(n).
The number of entries in row n is floor(n/2).
T(n,0) = A106640(n-1) .

			T(3,0)=4 because all non-derangements of {1,2,3}, namely 123=(1)(2)(3), 132=(1)(23), 213=(12)(3), and 321=(13)(2) have genus 0. This follows easily from the fact that a permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference).
Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  4, 0, 0,
[ 4]  11, 4, 0, 0,
[ 5]  36, 40, 0, 0, 0,
[ 6]  117, 290, 48, 0, 0, 0,
[ 7]  393, 1785, 1008, 0, 0, 0, 0,
[ 8]  1339, 9996, 12712, 1440, 0, 0, 0, 0,
[ 9]  4630, 52584, 123858, 48312, 0, 0, 0, 0, 0,
[10]  16193, 264720, 1027446, 904840, 80640, 0, 0, 0, 0, 0,
[11]  57201, 1290135, 7627158, 12449800, 3807936, 0, 0, 0, 0, 0, 0,
[12]  203799, 6133930, 52188774, 140356480, 96646176, 7257600, 0, ...,
[13]  731602, 28603718, 335517468, 1373691176, 1749377344, 448306560, 0, ...,
...

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8 (1998), 169-191.

Cf. A177267 (genus of all permutations).
Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations).
Cf. A002467, A106640.

n := 7: with(combinat): P := permute(n): inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc: nrcyc := proc (p) local pc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc: NDER := {}: for i to factorial(n) do if nrfp(P[i]) > 0 then NDER := `union`(NDER, {P[i]}) else end if end do: f[n] := sort(add(t^gen(NDER[j]), j = 1 .. nops(NDER))): seq(coeff(f[n], t, j), j = 0 .. floor((1/2)*n)-1); # yields the entries in the specified row n

Terms beyond row 7 from Joerg Arndt, Nov 01 2012.

A185209 Triangle read by rows: T(n,k) is the number of indecomposable (connected) permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 5, 8, 0, 0, 14, 49, 8, 0, 0, 42, 268, 151, 0, 0, 0, 132, 1375, 1760, 180, 0, 0, 0, 429, 6768, 16184, 5712, 0, 0, 0, 0, 1430, 32354, 128578, 102917, 8064, 0, 0, 0, 0, 4862, 151336, 923799, 1379384, 369944, 0, 0, 0, 0, 0, 16796, 696027, 6164460, 15283308, 9233512, 604800, 0

Offset: 1

Joerg Arndt, Nov 01 2012

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
Row sums are A003319.
First column is A000108.

			Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  2, 1, 0,
[ 4]  5, 8, 0, 0,
[ 5]  14, 49, 8, 0, 0,
[ 6]  42, 268, 151, 0, 0, 0,
[ 7]  132, 1375, 1760, 180, 0, 0, 0,
[ 8]  429, 6768, 16184, 5712, 0, 0, 0, 0,
[ 9]  1430, 32354, 128578, 102917, 8064, 0, 0, 0, 0,
[10]  4862, 151336, 923799, 1379384, 369944, 0, 0, 0, 0, 0,
[11]  16796, 696027, 6164460, 15283308, 9233512, 604800, 0, 0, 0, 0, 0,
[12]  58786, 3158280, 38863188, 147930256, 165848135, 36885312, 0, 0, ...,
[13]  208012, 14173566, 234193764, 1293232525, 2397551416, 1193273372, 68428800, 0, ...,
...

Cf. A177267 (genus of all permutations).

Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178517 (genus of non-derangement permutations), A178518 (permutations of [n] having genus 0 and p(1)=k).

A218538 Triangle read by rows: T(n,k) is the number of permutations of{1,2,...,n} avoiding [x,x+1] having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 1, 0, 3, 0, 0, 7, 4, 0, 0, 19, 29, 5, 0, 0, 53, 180, 76, 0, 0, 0, 153, 1004, 901, 61, 0, 0, 0, 453, 5035, 8884, 2315, 0, 0, 0, 0, 1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0, 4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0, 13015, 463740, 3658723, 7777935, 3896494, 209624, 0

Offset: 1

Joerg Arndt, Nov 01 2012

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
Row sums are A000255 (permutations with no substring [x,x+1]).
First column is A078481.

			Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  3, 0, 0,
[ 4]  7, 4, 0, 0,
[ 5]  19, 29, 5, 0, 0,
[ 6]  53, 180, 76, 0, 0, 0,
[ 7]  153, 1004, 901, 61, 0, 0, 0,
[ 8]  453, 5035, 8884, 2315, 0, 0, 0, 0,
[ 9]  1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0,
[10]  4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0,
[11]  13015, 463740, 3658723, 7777935, 3896494, 209624, 0, 0, 0, 0, 0,
[12]  40857, 1972339, 22712736, 77535694, 74678363, 13959422, 0, 0, ...,
[13]  129441, 8228981, 132804891, 685673340, 1131199122, 485204757, 23767241, 0, ...,
...

Cf. A177267 (genus of all permutations).

Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178517 (genus of non-derangement permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations).

cp's OEIS Frontend

A060593 a(n) is the number of ways that a cycle of length 2n+1 in the symmetric group S_(2n+1) can be decomposed as the product of two cycles of length 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A178514 Triangle read by rows: T(n,k) is the number of derangements of {1,2,...,n} having genus k (see first comment for definition of genus).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A178515 Triangle read by rows: T(n,k) is the number of involutions of {1,2,...,n} having genus k (see first comment for definition of genus).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Extensions

A370235 Table read by rows. Number of set partitions of [n] with respect to genus g.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A178516 Triangle read by rows: T(n,k) is the number of up-down permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A178517 Triangle read by rows: T(n,k) is the number of non-derangement permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Extensions

A185209 Triangle read by rows: T(n,k) is the number of indecomposable (connected) permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Views

Author

Keywords

Comments

Examples

Crossrefs

A218538 Triangle read by rows: T(n,k) is the number of permutations of{1,2,...,n} avoiding [x,x+1] having genus k (see first comment for definition of genus).

Views

Author

Keywords

Comments

Examples