A396787 - OEIS

%I #21 Jun 06 2026 19:46:17

%S 1,0,0,0,0,0,0,0,1,3,8,20,51,114,262,572,1238,2603,5435,11114,22539,

%T 45018,89119,174435,338651,651073,1242310,2351079,4418372,8243887,

%U 15283377,28151746,51549950,93846286,169917456,306013788,548341288,977736530,1735212109,3065483507

%N Number of compositions of n having exactly n inversions.

%H Alois P. Heinz, <a href="/A396787/b396787.txt">Table of n, a(n) for n = 0..62</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Composition_(combinatorics)">Composition (combinatorics)</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)">Inversion</a>

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

%e a(0) = 1: the empty composition.

%e a(8) = 1: 221111.

%e a(9) = 3: 2121111, 222111, 321111.

%e a(10) = 8: 12211111, 21121111, 2122111, 2211211, 2311111, 3121111, 232111, 321211.

%e a(11) = 20: 121211111, 211121111, 12212111, 21122111, 21211211, 22111121, 2221211, 13211111, 21311111, 31121111, 1322111, 2132111, 2213111, 2311211, 3121211, 3211121, 322211, 332111, 4211111, 422111.

%p b:= proc(n, p) option remember; `if`(n=0, 1, add(expand(

%p       b(n-j, p+x^j)*x^add(coeff(p, x, i), i=1..j-1)), j=1..n))

%p     end:

%p a:= n-> coeff(b(n, 0), x, n):

%p seq(a(n), n=0..30);

%Y Main diagonal of A189074.

%Y Cf. A128566, A214086.

%K nonn

%O 0,10

%A _Alois P. Heinz_, Jun 05 2026