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

Author

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

Keywords

• nonn

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.

Examples

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

Links

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

Crossrefs

Cf. A003319.

Programs

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

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