login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 5 03:48 EST 2023. Contains 360082 sequences. (Running on oeis4.)