A371810 a(n) is the number of pseudo-Latin stable matchings in a particular matrix of size n (see Comments for detail).

1, 2, 3, 10, 12, 32, 54, 268, 288, 656, 1044, 4360, 5472, 15632, 26424, 195472, 200832, 423104, 650736, 2404960, 2950272, 8146112, 13758624, 85524160, 93450240

Offset

1,2

Comments

This sequence arose from an attempt to reproduce A069124 by following the description in Thurber, 2002.

Define a matrix G for powers of 2, by G(1)=[1], and G(2^(k+1)) of size 2^(k+1) X 2^(k+1) by the block matrix [G(2^k), G(2^k)+2^k; G(2^k)+2^k, G(2^k)], where G(2^k)+2^k means add 2^k to each element of G(2^k) [see Thurber, p. 198 for more detail].

This sequence computes the number of pseudo-Latin stable matchings in the upper left n X n submatrix of G. Again, consult Thurber for definitions of what constitutes a stable matching in this situation.

Thurber's computation of these values are presented in A069124, but an attempt to reproduce that sequence gave the numbers of this sequence. The values here appear to be always increasing (unlike A069124). This is interesting because much of the Thurber paper is concerned with proving that the number of pseudo-Latin stable matchings is strictly increasing.

The first point of difference with A069124 occurs at n=7, but note that some later values do agree.

Links

Table of n, a(n) for n=1..25.

Sean A. Irvine, Java program (github)

E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Crossrefs

Cf. A069124.

Sequence in context: A168060 A306076 A069124 * A218028 A067769 A066089

Adjacent sequences: A371807 A371808 A371809 * A371811 A371812 A371813

Keyword

nonn,more

Author

Sean A. Irvine, Apr 06 2024

Status

approved