A141307 Number of bicolored connected permutations.

2, 4, 24, 208, 2272, 29504, 441216, 7447808, 139951616, 2897228800, 65533753344, 1608679247872, 42607095439360, 1211489065582592, 36818002833014784, 1191230067009978368, 40888060455008731136, 1484180363633916903424, 56809679459301490950144, 2287045885619374501396480, 96608773951155028111654912

Offset

1,1

Comments

Number of generators of degree n of the Hopf algebra of free quasi-symmetric functions of level 2. For level r, this would be r^n*c(n), where c(n) is the number of connected permutations (A003319).

These are also the dimensions of the graded components of the primitive Lie algebra of the same Hopf algebra.

Links

Table of n, a(n) for n=1..21.

J.-C. Novelli and J.-Y. Thibon, Free quasi-symmetric functions and descent algebras for wreath products and noncommutative multi-symmetric functions, arXiv:0806.3682 [math.CO], 2008.

Formula

a(n) = 2^n * A003319(n).

G.f.: 1/x - Q(0)/x where Q(k) = 1 - 2*x*(k+1)/(1 - 2*x*(k+1)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Apr 02 2013

G.f.: 1/x - (1 + x)/x/(x*Q(0) + 1) where Q(k)= 1 + (2*k+2)/(1 - x/(x + 1/Q(k+1) )); (continued fraction ). - Sergei N. Gladkovskii, Apr 11 2013

G.f.: 1/x - G(0)/(2*x), where G(k)= 1 + 1/(1 - 1/(1 - 1/(2*x*(2*k+2)) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 29 2013

Example

a(1)=2 because there are two colorings of the permutation (1).

Maple

2^n*op(n, INVERTi([seq(k!, k=1..n)]))

Mathematica

a3319[0] = 0; a3319[n_] := a3319[n] = n! - Sum[k! a3319[n-k], {k, 1, n-1}];
a[n_] := 2^n a3319[n];
Array[a, 21] (* Jean-François Alcover, Dec 10 2018 *)

Crossrefs

Cf. A003319.

Sequence in context: A121892 A032107 A378581 * A190655 A038049 A151817

Adjacent sequences: A141304 A141305 A141306 * A141308 A141309 A141310

Keyword

nonn

Author

Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Jun 26 2008

Status

approved