A219587 Noncrossing, nonnesting, 2-arc-colored permutations on the set {1..n} where lower arcs even of different colors do not cross.

1, 2, 8, 40, 224, 1296, 7568, 44304, 259536, 1520656, 8910160, 52209040, 305919696, 1792542992, 10503446608, 61545189520, 360625475024, 2113093401616, 12381720203088, 72550979111824, 425114158957776, 2490966357221136, 14595875630354000, 85524874633320080

Offset

0,2

Comments

The sequence is generated by a rational function, in particular, a quotient of two determinants.

Links

Lily Yen, Table of n, a(n) for n = 0..1000

Lily Yen, Crossings and Nestings for Arc-Coloured Permutations, arXiv:1211.3472 [math.CO], 2012-2013.

Index entries for linear recurrences with constant coefficients, signature (7,-6,-4).

Formula

G.f.: (1 - 5*x)/(1 - 7*x + 6*x^2 + 4*x^3).

a(n) = 7*a(n-1) - 6*a(n-2) - 4*a(n-3) for n>2. - Colin Barker, Jun 22 2019

Example

For n=4, the a(4) = 224 solutions are 24 permutations, 8 of which can be colored in 4 ways each, 8 in 8 ways each, and 8 in 16 ways each, thus resulting in 8 * (4+8+16) = 224.

Prog

(PARI) Vec((1 - 5*x) / (1 - 7*x + 6*x^2 + 4*x^3) + O(x^40)) \\ Colin Barker, Jun 22 2019

Crossrefs

Sequence in context: A027282 A006195 A214763 * A092807 A074601 A214760

Adjacent sequences: A219584 A219585 A219586 * A219588 A219589 A219590

Keyword

nonn,easy

Author

Lily Yen, Nov 23 2012

Extensions

Name modified by Lily Yen, Apr 23 2013

Status

approved