A189052 - OEIS

%I #56 Jul 03 2020 19:09:32

%S 0,0,0,1,4,14,42,118,314,806,2010,4902,11738,27686,64474,148518,

%T 338906,767014,1723354,3847206,8539098,18854950,41438170,90682406,

%U 197675994,429372454,929582042,2006430758,4318579674,9270965286,19854281690,42422744102,90452806618,192478164006

%N a(n) is the number of inversions in all compositions of n.

%C Row sums of triangle in A189073.

%H Nathaniel Johnston, <a href="/A189052/b189052.txt">Table of n, a(n) for n = 0..1000</a>

%H M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Archibald/arch3.html">Inversions and Parity in Compositions of Integers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.

%H S. Heubach, A. Knopfmacher, M. E. Mays and A. Munagi, <a href="https://www.researchgate.net/publication/228671252_Inversions_in_compositions_of_integers">Inversions in Compositions of Integers</a>, Quaest. Math. 34 (2011), no. 2, 187-202.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-6,-4,8)

%F a(n) = 2^(n-1)*(1/24*(n+2)*(n+1)-5/36*(n+1)-5/108)-2/27*(-1)^n for n>0.

%F a(n) = +5*a(n-1) -6*a(n-2) -4*a(n-3) +8*a(n-4).

%F G.f.: x^3*(1-x)/((1+x)*(1-2*x)^3).

%e a(4)=4. There are eight compositions of 4.  Five of these (the partitions of 4) have no inversions.  The remaining three: 3+1, 2+1+1, 1+2+1 have 1,2,1 inversions respectively. - _Geoffrey Critzer_, Mar 19 2014

%p with(PolynomialTools):n:=33:taypoly:=taylor(x^3*(1-x)/((1+x)*(1-2*x)^3),x=0,n+1):seq(coeff(taypoly,x,m),m=0..n); # _Nathaniel Johnston_, Apr 17 2011

%p # second Maple program:

%p a:= n-> `if`(n=0, 0, (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>,

%p              <8|-4|-6|5>>^n. <<-1/8, 0, 0, 1>>)[1, 1]):

%p seq(a(n), n=0..40);  # _Alois P. Heinz_, Apr 04 2016

%t nn=30;CoefficientList[Series[(1-x)*x^3/((1+x)*(1-x-x)^3),{x,0,nn}],x] (* _Geoffrey Critzer_, Mar 19 2014 *)

%t LinearRecurrence[{5,-6,-4,8},{0,0,0,1,4},40] (* _Harvey P. Dale_, May 25 2016 *)

%o (PARI)  A189052(n)=2^(n-1)*(1/24*(n+2)*(n+1)-5/36*(n+1)-5/108)-2/27*(-1)^n;

%o vector(33,n,A189052(n)) /* show terms */ /* _Joerg Arndt_, Apr 16 2011 */

%Y Cf. A264082, A271370, A271372.

%Y Cf. A189073.

%K nonn,easy

%O 0,5

%A _N. J. A. Sloane_, Apr 16 2011