A214086 -id:A214086 - cp's OEIS frontend

A128566 Number of permutations of {1..n} with n inversions.

1, 0, 0, 1, 5, 22, 90, 359, 1415, 5545, 21670, 84591, 330121, 1288587, 5032235, 19664205, 76893687, 300895513, 1178290263, 4617369760, 18106447251, 71048746505, 278966179936, 1095987764828, 4308300939450, 16944940572831, 66680029591816, 262519664110588

Offset: 0

Paul D. Hanna, Mar 12 2007

nonn

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

Diagonal of A008302 (Mahonian numbers).
Column 2 of A128564.
Cf. A128565 (column 1), A214086, A048651.

a:= n-> coeff(series(mul((1-q^j)/(1-q), j=1..n), q, n+1), q, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 05 2013

Table[SeriesCoefficient[QPochhammer[x, x, n]/(1-x)^n, {x, 0, n}], {n, 0, 25}] (* Vaclav Kotesovec, May 13 2016 *)

{a(n)=polcoeff(prod(j=1, n, (1-q^j)/(1-q)),n,q)}

a(n) = A008302(n,n) = coefficient of q^n in the q-factorial of n.
a(n) = T(n,n) with T(n,k) = T(n-1,k) + Sum_{j=1..n-1} T(n-1,k-j) for n>=0, k>0; T(n,k) = 0 for n<0; T(n,0) = 1 for n>=0. - Alois P. Heinz, Mar 07 2013
a(n) ~ c * 2^(2*n-1) / sqrt(Pi*n), where c = A048651 = QPochhammer[1/2] = 0.28878809508660242127889972192923... . - Vaclav Kotesovec, Sep 07 2014

Edited by Alois P. Heinz, Mar 05 2013

A213910 Irregular triangle read by rows: T(n,k) is the number of involutions of length n that have exactly k inversions; n>=0, 0<=k<=binomial(n,2).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 0, 1, 1, 3, 1, 2, 1, 1, 1, 1, 4, 3, 3, 4, 2, 4, 1, 3, 0, 1, 1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1, 1, 6, 10, 9, 16, 13, 19, 17, 19, 19, 17, 19, 13, 17, 7, 13, 3, 8, 1, 4, 0, 1, 1, 7, 15, 16, 26, 29, 34, 43, 39, 54, 41, 61, 40, 62, 36, 58, 28, 47, 21, 34, 15, 21, 10, 11, 6, 4, 3, 1, 1

Offset: 0

Geoffrey Critzer, Mar 04 2013

			T(4,3) = 2 because we have: (3,2,1,4), (1,4,3,2).
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2, 0, 1;
  1, 3, 1, 2, 1, 1,  1;
  1, 4, 3, 3, 4, 2,  4, 1, 3, 0, 1;
  1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..40, flattened

Cf. A008302 (permutations of [n] with k inversions).

Cf. A000085 (row sums), A211606, A214086 (diagonal).

T:= proc(n) option remember; local f, g, j; if n<2 then 1 else
      f, g:= [T(n-1)], [T(n-2)]; for j to 2*n-3 by 2 do
      f:= zip((x, y)->x+y, f, [0$j, g[]], 0) od; f[] fi
    end:
seq(T(n), n=0..10);  # Alois P. Heinz, Mar 05 2013

Needs["Combinatorica`"];
Table[Distribution[Map[Inversions,Involutions[n]],Range[0,Binomial[n,2]]],{n,0,9}]//Flatten
(* Second program: *)
zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]];
T[n_] := T[n] = Module[{f, g, j}, If[n < 2, Return@{1}, f = T[n-1]; g = T[n-2]; For[j = 1, j <= 2*n - 3, j += 2, f = zip[Plus, f, Join[Table[0, {j}], g], 0]]]; f];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 04 2023, after Alois P. Heinz *)

Sum_{k>=0} T(n,k)*k = A211606(n).

T(n,k) = T(n-1,k) + Sum_{j=1..n-1} T(n-2,k-2*(n-j)+1) for n>=0, k>0; T(n,k) = 0 for n<0 or k<0; T(n,0) = 1 for n>=0. - Alois P. Heinz, Mar 07 2013

cp's OEIS Frontend

A128566 Number of permutations of {1..n} with n inversions.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions