login
Number of bicolored connected permutations.
3

%I #25 Dec 10 2018 12:19:22

%S 2,4,24,208,2272,29504,441216,7447808,139951616,2897228800,

%T 65533753344,1608679247872,42607095439360,1211489065582592,

%U 36818002833014784,1191230067009978368,40888060455008731136,1484180363633916903424,56809679459301490950144,2287045885619374501396480,96608773951155028111654912

%N Number of bicolored connected permutations.

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

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

%H J.-C. Novelli and J.-Y. Thibon, <a href="https://arxiv.org/abs/0806.3682">Free quasi-symmetric functions and descent algebras for wreath products and noncommutative multi-symmetric functions</a>, arXiv:0806.3682 [math.CO], 2008.

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

%F 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

%F 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

%F 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

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

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

%t a3319[0] = 0; a3319[n_] := a3319[n] = n! - Sum[k! a3319[n-k], {k, 1, n-1}];

%t a[n_] := 2^n a3319[n];

%t Array[a, 21] (* _Jean-François Alcover_, Dec 10 2018 *)

%Y Cf. A003319.

%K nonn

%O 1,1

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