A396787 Number of compositions of n having exactly n inversions.

1, 0, 0, 0, 0, 0, 0, 0, 1, 3, 8, 20, 51, 114, 262, 572, 1238, 2603, 5435, 11114, 22539, 45018, 89119, 174435, 338651, 651073, 1242310, 2351079, 4418372, 8243887, 15283377, 28151746, 51549950, 93846286, 169917456, 306013788, 548341288, 977736530, 1735212109, 3065483507

Offset

0,10

Links

Alois P. Heinz, Table of n, a(n) for n = 0..62

Wikipedia, Composition (combinatorics)

Wikipedia, Inversion

Formula

a(n) = A189074(n,n).

Example

a(0) = 1: the empty composition.
a(8) = 1: 221111.
a(9) = 3: 2121111, 222111, 321111.
a(10) = 8: 12211111, 21121111, 2122111, 2211211, 2311111, 3121111, 232111, 321211.
a(11) = 20: 121211111, 211121111, 12212111, 21122111, 21211211, 22111121, 2221211, 13211111, 21311111, 31121111, 1322111, 2132111, 2213111, 2311211, 3121211, 3211121, 322211, 332111, 4211111, 422111.

Maple

b:= proc(n, p) option remember; `if`(n=0, 1, add(expand(
      b(n-j, p+x^j)*x^add(coeff(p, x, i), i=1..j-1)), j=1..n))
    end:
a:= n-> coeff(b(n, 0), x, n):
seq(a(n), n=0..30);

Crossrefs

Main diagonal of A189074.

Cf. A128566, A214086.

Sequence in context: A101893 A140662 A174198 * A384176 A077997 A294407

Adjacent sequences: A396784 A396785 A396786 * A396788 A396789 A396790

Keyword

nonn

Author

Alois P. Heinz, Jun 05 2026

Status

approved