|
%I #70 Sep 01 2022 10:31:18
%S 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,
%T 49,52,49,41,30,19,10,4,1,0,1,5,15,34,64,105,154,205,250,281,292,281,
%U 250,205,154,105,64,34,15,5,1,0
%N 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.
%C 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}.
%H María Merino, <a href="/A307429/b307429.txt">Table of n, a(n) for n = 1..20875 (rows n = 1..50, flattened)</a>
%H I. Unanue, M. Merino, and J. A. Lozano, <a href="https://doi.org/10.1007/s12293-022-00371-y">A Mathematical Analysis of EDAs with Distance-based Exponential Models</a>, Memetic Computing, 14 (2022), 305-334. Also on <a href="https://www.researchgate.net/publication/362049330_A_mathematical_analysis_of_EDAs_with_distance-based_exponential_models">ResearchGate</a>.
%F 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.
%e Triangle begins:
%e 1;
%e 1, 0;
%e 1, 1, 1, 0;
%e 1, 2, 3, 3, 2, 1, 0;
%e 1, 3, 6, 9, 11, 11, 9, 6, 3, 1, 0;
%e 1, 4, 10, 19, 30, 41, 49, 52, 49, 41, 30, 19, 10, 4, 1, 0;
%t 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}]]
%o (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
%o T(n, k) = sum(i=0, k, (-1)^(k-i)*S(n,i));
%o tabf(nn) = for (n=1, nn, for (k=0, n*(n-1)/2, print1(T(n, k), ", ")); print); \\ _Michel Marcus_, Apr 10 2019
%o (SageMath)
%o from sage.combinat.q_analogues import q_factorial
%o def A307429_row(n):
%o qf = q_factorial(n).list()
%o return [sum((-1)^(k-j)*qf[j] for j in range(k+1)) for k in range(n*(n-1)//2 + 1)]
%o for n in range(1, 7): print(A307429_row(n)) # _Peter Luschny_, Sep 01 2022
%Y Row sums give A001710.
%Y Cf. A008302.
%K nonn,tabf
%O 1,9
%A Imanol Unanue, _María Merino_, Jose A. Lozano, Apr 08 2019
|
