A224992 Non-crossing, non-nesting, 3-colored permutations on {1,2,...,n}.

1, 3, 18, 144, 1368, 14400, 160992, 1861632, 21919104, 260508672, 3110985216, 37241118720, 446349219840, 5352925446144, 64215514275840, 770468624990208, 9244918222258176, 110934787001942016, 1331192054033547264, 15974152308466384896, 191688913661984243712

Offset

0,2

Links

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

Wei Chen, Enumeration of Set Partitions Refined by Crossing and Nesting Numbers, MS Thesis, Department of Mathematics. Simon Fraser University, Fall 2014. Table 5.2, r=3.

Lily Yen, Crossings and Nestings for Arc-Coloured Permutations and Arc-coloured permutations, PSAC 2013, Paris, France, June 24-28, Proc. DMTCS (2013) 743-754.

Index entries for linear recurrences with constant coefficients, signature (20,-108,144).

Formula

G.f.: (1-17*x+66*x^2-36*x^3)/((1-2*x)*(1-6*x)*(1-12*x)).

a(n) = 9*2^n/20 +6^n/4 +12^n/20, n>0. - R. J. Mathar, Jun 11 2019

Example

For n=3, a(3)= 144, the number of ways to color arcs of a permutation on {1,2,3} in 3 colors such that the arcs neither cross nor nest.

Mathematica

Join[{1}, LinearRecurrence[{20, -108, 144}, {3, 18, 144}, 20]] (* Jean-François Alcover, Jul 22 2018 *)

Prog

(PARI) Vec((1-17*x+66*x^2-36*x^3)/((1-2*x)*(1-6*x)*(1-12*x))+O(x^66)) \\ Joerg Arndt, Apr 24 2013

Crossrefs

Sequence in context: A212030 A259904 A107708 * A289428 A123308 A177383

Adjacent sequences: A224989 A224990 A224991 * A224993 A224994 A224995

Keyword

nonn,easy

Author

Lily Yen, Apr 24 2013

Status

approved