login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

Needs a b-file.

LINKS

Table of n, a(n) for n=2..46.

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 28 22:35 EST 2020. Contains 331328 sequences. (Running on oeis4.)