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

Author

Lily Yen, Nov 23 2012

Keywords

• nonn
• easy

Comments

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

Examples

			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.
		

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).

Programs

PARI

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

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

Extensions

Name modified by Lily Yen, Apr 23 2013