cp's OEIS Frontend

A161125 Number of descents in all involutions of {1,2,...,n}.

%I A161125 #22 Dec 03 2018 08:37:22
%S A161125 0,0,1,4,15,52,190,696,2674,10480,42732,178480,770836,3411024,
%T A161125 15538120,72446752,346550520,1694394496,8477167504,43287312960,
%U A161125 225707308912,1199526928960,6498288708576,35836282708864,201160191642400,1148165325126912,6662315102507200,39268797697682176
%N A161125 Number of descents in all involutions of {1,2,...,n}.
%C A161125 Also total number of descents in all tableaux of size n (see Stanley ref.).
%C A161125 A descent in a standard Young tableau is a entry i such that i+1 lies strictly below and weakly left of i. [_Joerg Arndt_, Feb 18 2014]
%D A161125 R. P. Stanley, Enumerative Combinatorics Vol 2., Lemma 7.19.6, p. 361
%H A161125 Alois P. Heinz, <a href="/A161125/b161125.txt">Table of n, a(n) for n = 0..500</a>
%H A161125 J. Désarménien and D. Foata, <a href="http://www.numdam.org/item?id=BSMF_1985__113__3_0">Fonctions symétriques et séries hypergéométriques basiques multivariées</a>, Bull. Soc. Math. France, 113, 1985, 3-22.
%H A161125 I. M. Gessel and C. Reutenauer, <a href="http://dx.doi.org/10.1016/0097-3165(93)90095-P">Counting permutations with given cycle structure and descent set</a>, J. Combin. Theory, Ser. A, 64, 1993, 189-215.
%H A161125 V. J. W. Guo and J. Zeng, <a href="http://dx.doi.org/10.1016/j.jcta.2005.10.002">The Eulerian distribution on involutions is indeed unimodal</a>, J. Combin. Theory, Ser. A, 113, 2006, 1061-1071.
%F A161125 a(n) = (n-1)*A000085(n)/2.
%F A161125 a(n) = Sum(k*A161126(n,k), k=0..n-1).
%F A161125 Rec. rel.: a(n)/(n-1) = a(n-1)/(n-2) + (n-1)*a(n-2)/(n-3) for n>=4 (see 1st Maple program).
%F A161125 E.g.f.: (1/2)*(1 - (1 - z - z^2)*exp(z + z^2/2)).
%e A161125 a(3)=4 because in the involutions 123, 132, 213, and 321 we have 0 + 1 + 1 + 2 descents.
%p A161125 a[0] := 0: a[1] := 0: a[2] := 1: a[3] := 4: for n from 4 to 27 do a[n] := (n-1)*(a[n-1]/(n-2)+(n-1)*a[n-2]/(n-3)) end do: seq(a[n], n = 0 .. 27); # end of program
%p A161125 g := (1-(1-z-z^2)*exp(z+(1/2)*z^2))*1/2: gser := series(g, z = 0, 30): seq(factorial(n)*coeff(gser, z, n), n = 0 .. 27); # end of program
%t A161125 CoefficientList[Series[(1-(1-z-z^2)*Exp[z+(1/2)*z^2])/2,{z,0,24}],z] Range[0,24]!; (* _Emeric Deutsch_, Jun 09 2009 *)
%t A161125 descentset[t_?TableauQ]:=Sort[Cases[t,i_Integer /; Position[t,i+1][[1,1]] > Position[t,i][[1,1]], {2}]]; Table[Tr[Length[descentset[#]]& /@Tableaux[n]], {n,1,12}] (* _Wouter Meeussen_, Aug 04 2013 *)
%o A161125 (PARI) x='x+O('x^66);  concat([0,0],Vec(serlaplace((1/2)*(1-(1-x-x^2)*exp(x+x^2/2))))) \\ _Joerg Arndt_, Aug 04 2013
%Y A161125 Cf. A000085, A161126.
%K A161125 nonn
%O A161125 0,4
%A A161125 _Emeric Deutsch_, Jun 09 2009