[seqfan] Re: Basis in subsets of permutations described in A293783

[Vladimir Shevelev]

Dear Seq Fans,

I start with two remarks:
1) The previous message I began with
subsets a and b, corresponding to odd
and even positions of permutations of
{1..n}. So clearly that |a|=floor((n+1)/2),
|b|=floor(n/2) and the number of right
permutations equals 
|a|*|b|=floor((n+1)/2)*floor(n/2).
2) Further, clearly
sum_{i in a}i +sum_{j in b}j=1+....+n=
n*(n+1)/2. And we are free to consider an
arbitrary value for sum_{i in a}i -sum_{j in b}j.
So we would have a condition B on a and b.
3) Yesterday, Peter Moses sent me bases
in every case for n=11. In his form, in each
permutation of basis he firstly writes the set
of elements placing on the odd positions, and
then - on the even positions. Here his results
corresponding to even squares 36,16,4 and 0.
36: (1)
{{6,7,8,9,10,11},{1,2,3,4,5}}

16: (32)
{{1,3,7,9,10,11},{2,4,5,6,8}}
{{1,4,6,9,10,11},{2,3,5,7,8}}
{{1,4,7,8,10,11},{2,3,5,6,9}}
{{1,5,6,8,10,11},{2,3,4,7,9}}
{{1,5,7,8,9,11},{2,3,4,6,10}}
{{1,6,7,8,9,10},{2,3,4,5,11}}
{{1,2,8,9,10,11},{3,4,5,6,7}}
{{2,3,6,9,10,11},{1,4,5,7,8}}
{{2,3,7,8,10,11},{1,4,5,6,9}}
{{2,4,5,9,10,11},{1,3,6,7,8}}
{{2,4,6,8,10,11},{1,3,5,7,9}}
{{2,4,7,8,9,11},{1,3,5,6,10}}
{{2,5,6,7,10,11},{1,3,4,8,9}}
{{2,5,6,8,9,11},{1,3,4,7,10}}
{{2,5,7,8,9,10},{1,3,4,6,11}}
{{3,4,5,8,10,11},{1,2,6,7,9}}
{{3,4,6,7,10,11},{1,2,5,8,9}}
{{3,4,6,8,9,11},{1,2,5,7,10}}
{{3,4,7,8,9,10},{1,2,5,6,11}}
{{3,5,6,7,9,11},{1,2,4,8,10}}
{{3,5,6,8,9,10},{1,2,4,7,11}}
{{4,5,6,7,9,10},{1,2,3,8,11}}
{{4,5,6,7,8,11},{1,2,3,9,10}}

4: (23)
{{1,3,5,7,9,10},{2,4,6,8,11}}
{{1,3,5,7,8,11},{2,4,6,9,10}}
{{1,3,5,6,9,11},{2,4,7,8,10}}
{{1,3,6,7,8,10},{2,4,5,9,11}}
{{1,3,4,7,9,11},{2,5,6,8,10}}
{{1,3,4,8,9,10},{2,5,6,7,11}}
{{1,3,4,6,10,11},{2,5,7,8,9}}
{{1,4,5,7,8,10},{2,3,6,9,11}}
{{1,4,5,6,9,10},{2,3,7,8,11}}
{{1,4,5,6,8,11},{2,3,7,9,10}}
{{1,4,6,7,8,9},{2,3,5,10,11}}
{{1,2,5,7,9,11},{3,4,6,8,10}}
{{1,2,5,8,9,10},{3,4,6,7,11}}
{{1,2,5,6,10,11},{3,4,7,8,9}}
{{1,2,6,7,9,10},{3,4,5,8,11}}
{{1,2,6,7,8,11},{3,4,5,9,10}}
{{1,2,4,7,10,11},{3,5,6,8,9}}
{{1,2,4,8,9,11},{3,5,6,7,10}}
{{1,2,3,8,10,11},{4,5,6,7,9}}
{{2,3,5,7,8,10},{1,4,6,9,11}}
{{2,3,5,6,9,10},{1,4,7,8,11}}
{{2,3,5,6,8,11},{1,4,7,9,10}}
{{2,3,6,7,8,9},{1,4,5,10,11}}
{{2,3,4,7,9,10},{1,5,6,8,11}}
{{2,3,4,7,8,11},{1,5,6,9,10}}
{{2,3,4,6,9,11},{1,5,7,8,10}}
{{2,3,4,5,10,11},{1,6,7,8,9}}
{{2,4,5,7,8,9},{1,3,6,10,11}}
{{2,4,5,6,8,10},{1,3,7,9,11}}
{{2,4,5,6,7,11},{1,3,8,9,10}}
{{3,4,5,6,8,9},{1,2,7,10,11}}
{{3,4,5,6,7,10},{1,2,8,9,11}}

0: (29)
{{1,3,5,7,8,9},{2,4,6,10,11}}
{{1,3,5,6,8,10},{2,4,7,9,11}}
{{1,3,5,6,7,11},{2,4,8,9,10}}
{{1,3,4,7,8,10},{2,5,6,9,11}}
{{1,3,4,6,9,10},{2,5,7,8,11}}
{{1,3,4,6,8,11},{2,5,7,9,10}}
{{1,3,4,5,9,11},{2,6,7,8,10}}
{{1,4,5,6,8,9},{2,3,7,10,11}}
{{1,4,5,6,7,10},{2,3,8,9,11}}
{{1,2,5,7,8,10},{3,4,6,9,11}}
{{1,2,5,6,9,10},{3,4,7,8,11}}
{{1,2,5,6,8,11},{3,4,7,9,10}}
{{1,2,6,7,8,9},{3,4,5,10,11}}
{{1,2,4,7,9,10},{3,5,6,8,11}}
{{1,2,4,7,8,11},{3,5,6,9,10}}
{{1,2,4,6,9,11},{3,5,7,8,10}}
{{1,2,4,5,10,11},{3,6,7,8,9}}
{{1,2,3,7,9,11},{4,5,6,8,10}}
{{1,2,3,8,9,10},{4,5,6,7,11}}
{{1,2,3,6,10,11},{4,5,7,8,9}}
{{2,3,5,6,8,9},{1,4,7,10,11}}
{{2,3,5,6,7,10},{1,4,8,9,11}}
{{2,3,4,7,8,9},{1,5,6,10,11}}
{{2,3,4,6,8,10},{1,5,7,9,11}}
{{2,3,4,6,7,11},{1,5,8,9,10}}
{{2,3,4,5,9,10},{1,6,7,8,11}}
{{2,3,4,5,8,11},{1,6,7,9,10}}
{{2,4,5,6,7,9},{1,3,8,10,11}}
{{3,4,5,6,7,8},{1,2,9,10,11}}

Best regards,
Vladimir
 
________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Vladimir Shevelev [shevelev at exchange.bgu.ac.il]
Sent: 27 October 2017 13:22
To: seqfan at list.seqfan.eu
Subject: [seqfan] Basis in subsets of permutations described in A293783

Dear Seq Fans,

Consider a subset A of permutations
of {1..n} satisfying  a condition B
separately on the  elements on
odd positions (subset a) and the rest
elements (subset b) .
A permutation which contains two
permutations of elements of subsets
a and b only we call a right permutation.
So, we have |a|!*|b| ! right permutations.
For example, it is clear that |a|+|b|=
1+...+n=n*(n+1)/2 and we are free
to give the value of |a|-|b|. Then we
obtain a condition B on a and b in
the form of values |a| and |b|.
A subset S of permutations in A we
call a basis, if 1) there is no element
in S which is obtained by a right
permutation of another element in S;
2) any element in A\S is a right
permutation of an element from S .

The entries of triangle A293783 give
interesting examples.  Consider, say,
the seventh row
{576,0,720,0,144}. This means that
there are 576 permutations C={c_1..c_7}
of {1..7} for which d(C)=c_1-c_2+c_3-
c_4+c_5-c_6+c_7 = 0, there are
720 permutations for which d(C)=4
and there are 144 permutations with
d(C)=16. Of course, we consider
only even squares, since, evidently
d(C) always has the same parity as
1+...+7=28. I noted and David
Corneth proved (cf. comment in
A293984 with a similar proof) that every
entry of a row is divisible by the last entry
of this row.
 Dividing every entry of the 7th row by 144
we obtain (from the right to
the left): {1,0,5,0,4}. 1 means
that there exists only one permutation
which gives the maximal possible square 16
such that all other such permutations are
obtained from it by a right permutations
(separately terms with + and - in alternative
sum). For example, it is {7,1,6,2,5,3,4}
and 7-1+6-2+5-3+4=4^2 and clearly
it is the maximal possible square for n=7.
Thus here the basis contains 1 element.
Further, 5 means that there exists 5 distinct
permutations C with d(C)= 4
such that all other permutations for which
d(C)=4 are obtained from these
5 ones by right permutations.
 Of course, these 5 permutations
should not be obtained one from another
by a right permutation. So, here a basis contains 5
elements. For example, a basis is
{{7,6,5,4,3,2,1},{7,6,4,5,3,1,2},{7,5,6,4,2,3,1)
{6,7,5,3,4,2,1},{6,7,5,4,3,1,2}} .
Thus all entries of the second (compressed)
triangle in A293783 indicates the number of
elements in basis of the corresponding
subset.

Best regards,
Vladimir



--
Seqfan Mailing list - http://list.seqfan.eu/