A178217 Number of unsigned permutations in S_{3n-1} whose breakpoint graph contains only cycles of length 3.

1, 12, 464, 38720, 5678400, 1294720000, 423809075200, 188422340198400, 109244157102080000, 80068011114291200000, 72384558633074688000000, 79125533869852634644480000, 102879028406438808699535360000, 156917389218035568246207283200000, 277479100225377558605912342528000000

Offset

1,2

Comments

The number of permutations in S_{n} whose breakpoint graph contains only cycles of length 3 is nonzero only for n=3*k-1 (see references for definitions).

Links

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

J.-P. Doignon and A. Labarre, On Hultman Numbers, J. Integer Seq., 10 (2007), 13 pages.

A. Labarre, Combinatorial aspects of genome rearrangements and haplotype networks (2008), Ph. D. thesis.

Formula

a(n) = (3*n)!/(n!*12^n)*Sum_{i=0..n} binomial(n,i)*3^i/(2*i+1). (See references for a proof.)

Example

See references for examples (nongraphical explanations do not help much).

Prog

(Maxima) a(p) := ((3*p)!/(p!*12^p))*sum(binomial(p, i)*(3^i)/(2*i+1), i, 0, p);
(PARI) a(n) = (3*n)!/(n!*12^n) * sum(i = 0, n, binomial(n, i)*3^i/(2*i+1)); \\ Michel Marcus, Sep 05 2013

Crossrefs

Sequence in context: A221496 A302945 A089956 * A262584 A350154 A241226

Adjacent sequences: A178214 A178215 A178216 * A178218 A178219 A178220

Keyword

nonn

Author

Anthony Labarre, Dec 25 2010

Extensions

More terms from Michel Marcus, Oct 14 2024

Status

approved