A224993 Non-crossing, non-nesting, 4-colored permutations on {1,2,...,n}.

1, 4, 32, 352, 4736, 72832, 1226240, 21948928, 409192448, 7833143296, 152494727168, 3000118779904, 59406517698560, 1180988766453760, 23534128521936896, 469655122210324480, 9380774946206646272, 187467580232576794624, 3747576648059504820224

Offset

0,2

Comments

A225029-A225033 are sequences counting non-crossing, non-nesting, r-colored set partitions for r=3..7. Set partitions only have upper arcs, whereas permutations have upper and lower arcs in their annotated arc diagram representations.

Links

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

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 (40,-508,2304,-2880).

Formula

G.f.: (1-36*x+380*x^2-1200*x^3+576*x^4)/((1-2*x)*(1-6*x)*(1-12*x)*(1-20*x)).

a(n) = 2^(n-1)*(20*3^n+7*6^n+10^n+28)/35 for n>0, a(0)=1. [Bruno Berselli, Apr 26 2013]

Example

For n=3, a(3)=352, the number of ways to color arcs of a permutation on 3 elements in 4 colors so that arcs of the same color do not cross nor nest.

Mathematica

Join[{1}, LinearRecurrence[{40, -508, 2304, -2880}, {4, 32, 352, 4736}, 20]] (* Jean-François Alcover, Jul 22 2018 *)

Prog

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

Crossrefs

Sequence in context: A137432 A177750 A304911 * A357407 A319220 A347021

Adjacent sequences: A224990 A224991 A224992 * A224994 A224995 A224996

Keyword

nonn,easy

Author

Lily Yen, Apr 24 2013

Status

approved