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,5

Comments

Row sums of triangle in A189073.

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)

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

Example

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

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

Prog

(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 */

Crossrefs

Cf. A264082, A271370, A271372.

Cf. A189073.

Sequence in context: A347583 A124617 A124618 * A189426 A007076 A135483

Adjacent sequences: A189049 A189050 A189051 * A189053 A189054 A189055

Keyword

nonn,easy

Author

N. J. A. Sloane, Apr 16 2011

Status

approved