login
A294789
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.
1
2, 6, 0, 8, 0, 16, 20, 0, 100, 0, 12, 60, 288, 288, 72, 42, 0, 1764, 882, 2352, 0, 32, 96, 3584, 10112, 18816, 6912, 768, 54, 162, 12744, 39366, 156978, 105948, 47628, 0, 40, 760, 18000, 188400, 826400, 1420400, 966000, 194400, 14400, 110, 0, 73810, 589270, 4633090, 11845900, 14895100, 6446880, 1432640, 0
OFFSET
2,1
COMMENTS
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.
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.
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).
Among the n! different permutations on n elements, T(n,k) is the number with D(perm) = k.
LINKS
Giovanni Resta, Table of n, a(n) for n = 2..106 (up to 15th row)
Vsevolod F. Lev, Sums and Differences Along Hamiltonian Cycles, arXiv:math/0601633 [math.CO], 2006.
EXAMPLE
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.
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.
The triangle begins:
2,
6, 0,
8, 0, 16,
20, 0, 100, 0,
12, 60, 288, 288, 72,
...
The row sums are n!.
The first column appears to be A002618.
MATHEMATICA
<< Combinatorica`;
For[n = 3, n <= 12, n++,
perm = Range[n];
For[i = 1, i <= n - 1, i++, d[i] = 0];
set = {};
Print[]; Print[n];
For[index = 1, index <= n!, index++,
perm = NextPermutation[perm];
(*Print[perm[[index]]]; *)
set = {};
For[i = 1, i <= n - 1, i++, diff = perm[[i + 1]] - perm[[i]];
If[diff < 0, diff = diff + n];
set = Union[set, {diff}]];
diff = perm[[1]] - perm[[n]];
If[diff < 0, diff = diff + n];
set = Union[set, {diff}];
L = Length[set];
d[L]++];
Print[Table[d[i], {i, 1, n - 1}]]]
CROSSREFS
Sequence in context: A241810 A156991 A229586 * A197035 A227805 A267314
KEYWORD
nonn,tabl
AUTHOR
David S. Newman, Nov 08 2017
EXTENSIONS
Edited by N. J. A. Sloane, Nov 11 2017
Row 11 from Jinyuan Wang, Feb 17 2020
STATUS
approved