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.

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

Cf. A000142, A002618.

Sequence in context: A241810 A156991 A229586 * A197035 A227805 A267314

Adjacent sequences: A294786 A294787 A294788 * A294790 A294791 A294792

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