|
%I #27 Feb 17 2020 10:42:14
%S 2,6,0,8,0,16,20,0,100,0,12,60,288,288,72,42,0,1764,882,2352,0,32,96,
%T 3584,10112,18816,6912,768,54,162,12744,39366,156978,105948,47628,0,
%U 40,760,18000,188400,826400,1420400,966000,194400,14400,110,0,73810,589270,4633090,11845900,14895100,6446880,1432640,0
%N Triangle read by rows: T(n,k), n>=2, 1 <= k <= n-1, is the number of permutations in S_n in which there are k different values for the values mod n of the differences between adjacent elements when written in row notation.
%C Take a permutation perm on the numbers 1 through n, think of it as a sequence: perm = (x1, x2, ... xn) where each of the x's is a number between 1 and n.
%C Now take the sequence of differences, read cyclically: Diff(perm) = (x2 - x1, x3 - x2, ... xn - x(n-1), x1 - xn) but take the differences mod n, so that we have no negative numbers, only numbers between 1 and n-1.
%C Now consider Diff(perm) as a set, ignoring repetitions, and count how many different elements there are in it. Let that be called D(perm).
%C Among the n! different permutations on n elements, T(n,k) is the number with D(perm) = k.
%H Giovanni Resta, <a href="/A294789/b294789.txt">Table of n, a(n) for n = 2..106</a> (up to 15th row)
%H Vsevolod F. Lev, <a href="https://arxiv.org/abs/math/0601633">Sums and Differences Along Hamiltonian Cycles</a>, arXiv:math/0601633 [math.CO], 2006.
%e For n=2 there are two permutations: {1,2} and {2,1} in each case there is but 1 difference, namely 1. This gives the first value of the sequence T(2,1)=2.
%e For n=3 there are six permutations and once again the only difference between successive member of the permutation is one. There are no successive members whose difference is two. This gives T(3,1)=6, T(3,2)=0.
%e The triangle begins:
%e 2,
%e 6, 0,
%e 8, 0, 16,
%e 20, 0, 100, 0,
%e 12, 60, 288, 288, 72,
%e ...
%e The row sums are n!.
%e The first column appears to be A002618.
%t << Combinatorica`;
%t For[n = 3, n <= 12, n++,
%t perm = Range[n];
%t For[i = 1, i <= n - 1, i++, d[i] = 0];
%t set = {};
%t Print[]; Print[n];
%t For[index = 1, index <= n!, index++,
%t perm = NextPermutation[perm];
%t (*Print[perm[[index]]];*)
%t set = {};
%t For[i = 1, i <= n - 1, i++, diff = perm[[i + 1]] - perm[[i]];
%t If[diff < 0, diff = diff + n];
%t set = Union[set, {diff}]];
%t diff = perm[[1]] - perm[[n]];
%t If[diff < 0, diff = diff + n];
%t set = Union[set, {diff}];
%t L = Length[set];
%t d[L]++];
%t Print[Table[d[i], {i, 1, n - 1}]]]
%Y Cf. A000142, A002618.
%K nonn,tabl
%O 2,1
%A _David S. Newman_, Nov 08 2017
%E Edited by _N. J. A. Sloane_, Nov 11 2017
%E Row 11 from _Jinyuan Wang_, Feb 17 2020
|
