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

0, 0, 0, 1, 4, 14, 42, 118, 314, 806, 2010, 4902, 11738, 27686, 64474, 148518, 338906, 767014, 1723354, 3847206, 8539098, 18854950, 41438170, 90682406, 197675994, 429372454, 929582042, 2006430758, 4318579674, 9270965286, 19854281690, 42422744102, 90452806618, 192478164006

Offset: 0

Author

N. J. A. Sloane, Apr 16 2011

Keywords

• nonn
• easy

Comments

Row sums of triangle in A189073.

Examples

			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
		

Links

• Nathaniel Johnston, Table of n, a(n) for n = 0..1000
• M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
• S. Heubach, A. Knopfmacher, M. E. Mays and A. Munagi, Inversions in Compositions of Integers, Quaest. Math. 34 (2011), no. 2, 187-202.
• Index entries for linear recurrences with constant coefficients, signature (5,-6,-4,8)

Crossrefs

Cf. A264082, A271370, A271372.

Cf. A189073.

Programs

Maple

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
# second Maple program:
a:= n-> `if`(n=0, 0, (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>,
             <8|-4|-6|5>>^n. <<-1/8, 0, 0, 1>>)[1, 1]):
seq(a(n), n=0..40);  # Alois P. Heinz, Apr 04 2016

Mathematica

nn=30;CoefficientList[Series[(1-x)*x^3/((1+x)*(1-x-x)^3),{x,0,nn}],x] (* Geoffrey Critzer, Mar 19 2014 *)
LinearRecurrence[{5,-6,-4,8},{0,0,0,1,4},40] (* Harvey P. Dale, May 25 2016 *)

PARI

A189052(n)=2^(n-1)*(1/24*(n+2)*(n+1)-5/36*(n+1)-5/108)-2/27*(-1)^n;
vector(33,n,A189052(n)) /* show terms */ /* Joerg Arndt, Apr 16 2011 */

Formula

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

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

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