disapointment by counterexample

[Wouter Meeussen]

re: Michael Reid's A070735

ID Number: A070735 Sequence:
1,6,18,44,89,162,271,428,642,930,1304,1781,2377,3111,4002 Name: Let r, s, t
be three permutations of the set { 1, 2, 3, ... , n }; a(n) = minimal value
of Sum_{i=1..n} r(i) s(i) t(i). See also: Cf. A000292 (for two
permutations), A070736 (for four). Keywords: nice,nonn,more,new Offset: 1
Author(s): Michael Reid (mreid at math.umass.edu), May 15 2002

for some time, I thought all minimal triplets of permutations r, s, t,
corresponded to triplets of integers according to the following:

    if permutations r, s, t of {1,2,3,...,n} generate a minimal Reid-product
(not really a dot-product heh?), then the triplets of integers ('allowed
triplets') from each permutation (integers that get multiplied), are
nescessary and sufficient for generation of the full set of "Reid-minimal"
permutations .

Example:

n=7
allowed[[7]]
{{1, 5, 7}, {1, 6, 6}, {1, 6, 7}, {2, 3, 6}, {2, 3, 7}, {2, 4, 5}, {3, 3,
4}}

So, my idea was that *any* set of seven triplets choosen from the above,
with the proviso that every integer must occur exactly three times, yields a
Reid-minimal set of three permutations of Range[7]. And stronger, yields all
of them and only them.

this works up to n=11.
Fails on n=12 in a somewhat 'elegant' way:
allowed[[12]]
{{1, 11, 12}, {2, 7, 10}, {2, 8, 9}, {2, 8, 10}, {3, 6, 9}, {3, 7, 7}, {4,
4, 10}, {4, 5, 8}, {5, 5, 6}}

these are 24 permutions built from the above set (*), that have Reid-product
1781

{{{11, 7, 6, 8, 5, 9, 3, 10, 2, 4, 12, 1}, {12, 10, 9, 5, 6, 3, 7, 2, 8, 4,
1,
       11}}, {{11, 7, 6, 10, 5, 9, 3, 4, 2, 8, 12, 1}, {12, 10, 9, 4, 6, 3,
7,
       5, 8, 2, 1, 11}}, {{11, 7, 6, 10, 5, 9, 3, 4, 8, 2, 12, 1}, {12, 10,
9,
       4, 6, 3, 7, 5, 2, 8, 1, 11}}, {{11, 7, 9, 10, 4, 5, 3, 2, 6, 8, 12,
      1}, {12, 10, 6, 4, 8, 5, 7, 9, 3, 2, 1, 11}}, {{11, 8, 6, 10, 4, 5, 7,
      9, 3, 2, 12, 1}, {12, 10, 9, 4, 8, 5, 3, 2, 6, 7, 1, 11}}, {{11, 8, 6,
      10, 5, 9, 3, 4, 2, 7, 12, 1}, {12, 10, 9, 4, 6, 3, 7, 5, 8, 2, 1,
      11}}, {{11, 8, 7, 4, 6, 9, 10, 5, 3, 2, 12, 1}, {12, 9, 7, 10, 5, 3,
2,
      4, 6, 8, 1, 11}}, {{11, 8, 7, 5, 6, 9, 2, 10, 3, 4, 12, 1}, {12, 9, 7,
      8, 5, 3, 10, 2, 6, 4, 1, 11}}, {{11, 8, 7, 5, 6, 9, 10, 2, 3, 4, 12,
      1}, {12, 9, 7, 8, 5, 3, 2, 10, 6, 4, 1, 11}}, {{11, 8, 7, 5, 6, 9, 10,
      2, 3, 4, 12, 1}, {12, 10, 7, 8, 5, 3, 2, 9, 6, 4, 1, 11}}, {{11, 8, 9,
      10, 4, 5, 3, 2, 6, 7, 12, 1}, {12, 9, 6, 4, 8, 5, 7, 10, 3, 2, 1,
      11}}, {{11, 8, 9, 10, 4, 5, 3, 2, 6, 7, 12, 1}, {12, 10, 6, 4, 8, 5,
7,
      9, 3, 2, 1, 11}}, {{11, 9, 6, 4, 8, 5, 7, 10, 3, 2, 12, 1}, {12, 8, 9,
      10, 4, 5, 3, 2, 6, 7, 1, 11}}, {{11, 9, 7, 8, 5, 3, 2, 10, 6, 4, 12,
      1}, {12, 8, 7, 5, 6, 9, 10, 2, 3, 4, 1, 11}}, {{11, 9, 7, 8, 5, 3, 10,
      2, 6, 4, 12, 1}, {12, 8, 7, 5, 6, 9, 2, 10, 3, 4, 1, 11}}, {{11, 9, 7,
      10, 5, 3, 2, 4, 6, 8, 12, 1}, {12, 8, 7, 4, 6, 9, 10, 5, 3, 2, 1,
      11}}, {{11, 10, 6, 4, 8, 5, 7, 9, 3, 2, 12, 1}, {12, 7, 9, 10, 4, 5,
3,
      2, 6, 8, 1, 11}}, {{11, 10, 6, 4, 8, 5, 7, 9, 3, 2, 12, 1}, {12, 8, 9,
      10, 4, 5, 3, 2, 6, 7, 1, 11}}, {{11, 10, 7, 8, 5, 3, 2, 9, 6, 4, 12,
      1}, {12, 8, 7, 5, 6, 9, 10, 2, 3, 4, 1, 11}}, {{11, 10, 9, 4, 6, 3, 7,
      5, 2, 8, 12, 1}, {12, 7, 6, 10, 5, 9, 3, 4, 8, 2, 1, 11}}, {{11, 10,
9,
      4, 6, 3, 7, 5, 8, 2, 12, 1}, {12, 7, 6, 10, 5, 9, 3, 4, 2, 8, 1,
      11}}, {{11, 10, 9, 4, 6, 3, 7, 5, 8, 2, 12, 1}, {12, 8, 6, 10, 5, 9,
3,
      4, 2, 7, 1, 11}}, {{11, 10, 9, 4, 8, 5, 3, 2, 6, 7, 12, 1}, {12, 8, 6,
      10, 4, 5, 7, 9, 3, 2, 1, 11}}, {{11, 10, 9, 5, 6, 3, 7, 2, 8, 4, 12,
      1}, {12, 7, 6, 8, 5, 9, 3, 10, 2, 4, 1, 11}}}

but the following are counter-examples : they produce 1782  ::

{{{11, 7, 6, 5, 8, 9, 10, 4, 3, 2, 12, 1}, {12, 10, 9, 8, 4, 3, 2, 5, 6, 7,
1,
       11}}, {{11, 7, 6, 8, 4, 9, 10, 5, 3, 2, 12, 1}, {12, 10, 9, 5, 8, 3,
2,
       4, 6, 7, 1, 11}}, {{11, 7, 9, 5, 8, 3, 10, 4, 6, 2, 12, 1}, {12, 10,
6,
       8, 4, 9, 2, 5, 3, 7, 1, 11}}, {{11, 7, 9, 8, 4, 3, 10, 5, 6, 2, 12,
      1}, {12, 10, 6, 5, 8, 9, 2, 4, 3, 7, 1, 11}}, {{11, 10, 6, 5, 8, 9, 2,
      4, 3, 7, 12, 1}, {12, 7, 9, 8, 4, 3, 10, 5, 6, 2, 1, 11}}, {{11, 10,
6,
      8, 4, 9, 2, 5, 3, 7, 12, 1}, {12, 7, 9, 5, 8, 3, 10, 4, 6, 2, 1,
      11}}, {{11, 10, 9, 5, 8, 3, 2, 4, 6, 7, 12, 1}, {12, 7, 6, 8, 4, 9,
10,
      5, 3, 2, 1, 11}}, {{11, 10, 9, 8, 4, 3, 2, 5, 6, 7, 12, 1}, {12, 7, 6,
      5, 8, 9, 10, 4, 3, 2, 1, 11}}}

close, but no cigar.


Wouter Meeussen
wouter.meeussen at pandora.be

see for yourself : (Backtrack needs DiscreteMath`Combinatorica`)


allowed = {{{1,1,1}},{{1, 1, 2}, {1, 2, 2}}, {{1, 2, 3}}, {{1, 2, 4}, {1, 3,
4}, {2, 2, 2}, {2, 2, 3}}, {{1, 3, 5}, {1, 4, 4}, {1, 4, 5}, {2, 2, 4}, {2,
2, 5}, {2, 3, 3}}, {{1, 4, 6}, {1, 5, 5}, {1, 5, 6}, {2, 2, 6}, {2, 3, 4},
{2, 3, 5}, {2, 4, 4}, {3, 3, 3}}, {{1, 5, 7}, {1, 6, 6}, {1, 6, 7}, {2, 3,
6}, {2, 3, 7}, {2, 4, 5}, {3, 3, 4}}, {{1, 6, 8}, {1, 7, 8}, {2, 4, 6}, {2,
4, 7}, {2, 5, 5}, {2, 5, 6}, {3, 3, 6}, {3, 4, 4}, {3, 4, 5}}, {{1, 8, 9},
{2, 5, 7}, {3, 4, 6}}, {{1, 9, 10}, {2, 6, 7}, {2, 6, 8}, {2, 7, 7}, {3, 4,
7}, {3, 4, 8}, {3, 5, 6}, {4, 5, 5}}, {{1, 10, 11}, {2, 6, 9}, {2, 7, 9},
{2, 8, 8}, {3, 4, 9}, {3, 5, 8}, {3, 6, 6}, {3, 6, 7}, {4, 4, 8}, {4, 5,
6}}};

the sets of "3" permutations show only the last 2, the first being implied
as a plain {1,2,3...,n}.

in Mathematica lingo, you build permutations from these triples by:

Table[it=allowed[[n]];
a=(Cases[it,q_/;(!FreeQ[q,#])]/. {i___,#,j___}:>{i,j})&/@Range[n];
b=a/. {i_Integer,j_}/;(j=!=i):>Sequence[{i,j},{j,i}];
res=Backtrack[b,(UnsameQ@@@Transpose[#])==={True,True}&,True&,All];
{n,Length[res],Union[Sort/@(Transpose/@res)]//Length,Union[z[Range[n],#1,#2]
&@@@Transpose/@res]},{n,2,11}]//ColumnForm

{2, 3, 2, {6}}
{3, 2, 1, {18}}
{4, 8, 4, {44}}
{5, 18, 9, {89}}
{6, 44, 22, {162}}
{7, 36, 18, {271}}
{8, 96, 48, {428}}
{9, 8, 4, {642}}
{10, 72, 36, {930}}
{11, 96, 48, {1304}}