A307429 Triangle read by rows: T(n,k) is the number of permutations of {1..n} at Kendall tau distance k of permutation sigma1 and k+1 Kendall tau distance of permutation sigma2, where sigma1 and sigma2 are at Kendall tau distance 1.

1, 1, 0, 1, 1, 1, 0, 1, 2, 3, 3, 2, 1, 0, 1, 3, 6, 9, 11, 11, 9, 6, 3, 1, 0, 1, 4, 10, 19, 30, 41, 49, 52, 49, 41, 30, 19, 10, 4, 1, 0, 1, 5, 15, 34, 64, 105, 154, 205, 250, 281, 292, 281, 250, 205, 154, 105, 64, 34, 15, 5, 1, 0

Offset: 1

Author

Imanol Unanue, María Merino, Jose A. Lozano, Apr 08 2019

Keywords

• nonn
• tabf

Comments

The length of the n-th row is n(n-1)/2 + 1, where n(n-1)/2 is the maximum Kendall tau distance distance for permutations of {1..n}.

Examples

			Triangle begins:
  1;
  1, 0;
  1, 1,  1,  0;
  1, 2,  3,  3,  2,  1,  0;
  1, 3,  6,  9, 11, 11,  9,  6,  3,  1, 0;
  1, 4, 10, 19, 30, 41, 49, 52, 49, 41, 30, 19, 10, 4, 1, 0;
		

Links

• María Merino, Table of n, a(n) for n = 1..20875 (rows n = 1..50, flattened)
• I. Unanue, M. Merino, and J. A. Lozano, A Mathematical Analysis of EDAs with Distance-based Exponential Models, Memetic Computing, 14 (2022), 305-334. Also on ResearchGate.

Crossrefs

Row sums give A001710.

Cf. A008302.

Programs

Mathematica

T[n_] := Module[{polcoef, svalues = {}, si, j, k, c}, polcoef = CoefficientList[Series[QFactorial[n, c], {c, 0, n (n - 1)/2}], c]; For[j = 1, j <= Length[polcoef], j++, si = 0; For[k = 1, k <= j, k++, si = si + polcoef[[k]]*(-1)^(j - k)]; AppendTo[svalues, si]]; Return[svalues]]; Catenate[Table[T[n], {n, 1, 7}]]

PARI

S(n, k) = my(A=1+x); for(i=1, n, A = 1 + intformal(A - q*subst(A, x, q*x +x^2*O(x^n)))/(1-q)); polcoeff(n!*polcoeff(A, n, x), k, q); \\ A008302
T(n, k) = sum(i=0, k, (-1)^(k-i)*S(n,i));
tabf(nn) = for (n=1, nn, for (k=0, n*(n-1)/2, print1(T(n, k), ", ")); print); \\ Michel Marcus, Apr 10 2019

SageMath

from sage.combinat.q_analogues import q_factorial
def A307429_row(n):
    qf = q_factorial(n).list()
    return [sum((-1)^(k-j)*qf[j] for j in range(k+1)) for k in range(n*(n-1)//2 + 1)]
for n in range(1, 7): print(A307429_row(n)) # Peter Luschny, Sep 01 2022

Formula

T(n,k) = Sum_{j=0..k} (-1)^j * S(n,k-j), where S(n,k) = A008302(n,k) is the number of permutations of {1..n} with k inversions.