|
|
A309283
|
|
Number of equivalence classes of X-based filling of diagonals in a diagonal Latin square of order n.
|
|
6
|
|
|
1, 1, 0, 0, 2, 2, 3, 3, 20, 20, 67, 67, 596, 596
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Used for getting strong canonical forms (SCFs) of the diagonal Latin squares and for fast enumerating of the diagonal Latin squares based on equivalence classes.
K1 = |C[1]|*f[1] + |C[2]|*f[2] + ... + |C[m]|*f[m],
K2 = K1 * n!,
where m = a(n), number of equivalence classes for X-based filling of diagonals in a diagonal Latin square of order n;
C[i], corresponding equivalence classes with cardinalities |C[i]|, 1 <= i <= m;
f[i], the number of diagonal Latin squares corresponds to the each item from equivalence class C[i], 1 <= i <= m;
K1 = A274171(n), number of diagonal Latin squares of order n with fixed first row;
K2 = A274806(n), number of diagonal Latin squares of order n.
The number of solutions in an equivalence class with the main diagonal in ascending order is at most 4*2^r*r! where r = floor(n/2). This maximum is achieved for orders n >= 10. - Andrew Howroyd, Mar 27 2023
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For order n=4 there are a(4)=2 equivalence classes. First of them C[1] includes two X-based fillings of diagonals
0..1 0..2
.13. .10.
.02. .32.
2..3 1..3
and second C[2] also includes two X-based fillings of diagonals
0..1 0..2
.10. .13.
.32. .02.
2..3 1..3
It is easy to see that f[1] = 0 and f[2] = 1, so K1(4) = A274171(4) = 2*0 + 2*1 = 2 and K2(4) = A274806(4) = K1(4) * 4! = 2 * 24 = 48.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|