A350645 Number of permutations avoiding 132 of length 3n composed of only 3-cycles.

1, 2, 8, 36, 170, 824, 4060, 20232, 101664, 514140, 2613468, 13340496, 68335644, 351087128, 1808405600, 9335697424, 48289295226, 250213951992, 1298517484804, 6748250144600, 35114221973600, 182924946400680, 953931045159000, 4979398271047200, 26014703727203100

Offset

0,2

Comments

Also the number of permutations avoiding 213 of length 3n composed of only 3-cycles.

Links

Table of n, a(n) for n=0..24.

Kassie Archer and Christina Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.

Formula

G.f.: c(x*c(x))/(2-c(x*c(x))) where c(x) is the generating function for Catalan numbers. Notice c(x*c(x)) is given in A127632.

G.f.: (1+A(x))/(1-A(x)) where A(x) = (c(x)-1)*c(m(x)-1) where c(x) is the generating function for Catalan numbers and m(x) is the generating function for the Motzkin numbers.

Example

For n=2, the eight permutations (in one-line notation and cycle notation) are:
  [6, 5, 2, 1, 3, 4] (1,6,4)(2,5,3)
  [6, 4, 2, 3, 1, 5] (1,6,5)(2,4,3)
  [6, 3, 4, 2, 1, 5] (1,6,5)(2,3,4)
  [5, 6, 1, 2, 3, 4] (1,5,3)(2,6,4)
  [3, 4, 5, 6, 1, 2] (1,3,5)(2,4,6)
  [4, 3, 5, 6, 2, 1] (1,4,6)(2,3,5)
  [5, 3, 4, 2, 6, 1] (1,5,6)(2,3,4)
  [5, 4, 2, 3, 6, 1] (1,5,6)(2,4,3) .

Crossrefs

Cf. A000108, A001006, A127632.

Sequence in context: A206902 A275752 A084868 * A330793 A352862 A109980

Adjacent sequences: A350642 A350643 A350644 * A350646 A350647 A350648

Keyword

nonn

Author

Kassie Archer, Jan 09 2022

Status

approved