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

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

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.

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.

Example

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;

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}]]

Prog

(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

Crossrefs

Row sums give A001710.

Cf. A008302.

Sequence in context: A291196 A279316 A074989 * A261283 A123548 A131838

Adjacent sequences: A307426 A307427 A307428 * A307430 A307431 A307432

Keyword

nonn,tabf

Author

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

Status

approved