A005154 -id:A005154 - cp's OEIS frontend

A076725 a(n) = a(n-1)^2 + a(n-2)^4, a(0) = a(1) = 1.

1, 1, 2, 5, 41, 2306, 8143397, 94592167328105, 13345346031444632841427643906, 258159204435047592104207508169153297050209383336364487461

Offset: 0

Michael Somos, Oct 29 2002

a(n) and a(n+1) are relatively prime for n >= 0.
The number of independent sets on a complete binary tree with 2^(n-1)-1 nodes. - Jonathan S. Braunhut (jonbraunhut(AT)usa.net), May 04 2004. For example, when n=3, the complete binary tree with 2 levels has 2^2-1 nodes and has 5 independent sets so a(3)=5. The recursion for number of independent sets splits in two cases, with or without the root node being in the set.
a(10) has 113 digits and is too large to include.

			a(2) = a(1)^2 + a(0)^4 = 1^2 + 1^4 = 2.
a(3) = a(2)^2 + a(1)^4 = 2^2 + 1^4 = 5.
a(4) = a(3)^2 + a(2)^4 = 5^2 + 2^4 = 41.
a(5) = a(4)^2 + a(3)^4 = 41^2 + 5^4 = 2306.
a(6) = a(5)^2 + a(4)^4 = 2306^2 + 41^4 = 8143397.
a(7) = a(6)^2 + a(5)^4 = 8143397^2 + 2306^4 = 94592167328105.

Robert Israel, Table of n, a(n) for n = 0..13
Karl Petersen, Ibrahim Salama, Tree shift complexity, arXiv:1712.02251 [math.DS], 2017.
Index entries for sequences of form a(n+1)=a(n)^2 + ...

Cf. A000283, A005154, A112969, A114793.

A[0]:= 1: A[1]:= 1:
for n from 2 to 10 do
  A[n]:= A[n-1]^2 + A[n-2]^4;
od:
seq(A[i],i=0..10); # Robert Israel, Aug 21 2017

RecurrenceTable[{a[n] == a[n-1]^2 + a[n-2]^4, a[0] ==1, a[1] == 1}, a, {n, 0, 10}] (* Vaclav Kotesovec, Dec 18 2014 *)
NestList[{#[[2]],#[[1]]^4+#[[2]]^2}&,{1,1},10][[All,1]] (* Harvey P. Dale, Jul 03 2021 *)

{a(n) = if( n<2, 1, a(n-1)^2 + a(n-2)^4)}

{a=[0,0];for(n=1,99,iferr(a=[a[2],log(exp(a*[4,0;0,2])*[1,1]~)],E,return([n,exp(a[2]/2^n)])))} \\ To compute an approximation of the constant c1 = exp(lim_{n->oo} (log a(n))/2^n). \\ M. F. Hasler, May 21 2017

a=vector(20); a[1]=1;a[2]=2; for(n=3, #a, a[n]=a[n-1]^2+a[n-2]^4); concat(1, a) \\ Altug Alkan, Apr 04 2018

If b(n) = 1 + 1/b(n-1)^2, b(1)=1, then b(n) = a(n)/a(n-1)^2.
Lim_{n->inf} a(n)/a(n-1)^2 = A092526 (constant).
a(n) is asymptotic to c1^(2^n) * c2.
c1 = 1.2897512927198122075..., c2 = 1/A092526 = A263719 = (1/6)*(108 + 12*sqrt(93))^(1/3) - 2/(108 + 12*sqrt(93))^(1/3) = 0.682327803828019327369483739711... is the root of the equation c2*(1 + c2^2) = 1. - Vaclav Kotesovec, Dec 18 2014

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 15 2007

A351409 a(n) = n(n!)^(2n-2).

Original entry on oeis.org

1, 8, 3888, 764411904, 214990848000000000, 224634374557469245440000000000, 1880461634768804771224006806208512000000000000, 240091793104790737576620139562796649430329798636339200000000000000, 813675117804798213250391541747787241264315446434692481270971279693253181440000000000000000

Offset: 1

Dan Eilers, Feb 11 2022

nonn

a(n) is the number of reduced Stable Marriage Problem instances of order n. In the SMP, relabeling men or women has no effect on the number of stable matchings. So the men and women can be relabeled to normalize the order of man #1's rankings (with woman #1 as his first choice and woman n as his last choice), and to similarly normalize the order of woman #1's rankings, except for her ranking of man #1. This reduces the number of possible instances by a factor of n!(n-1)! (A010790 with shifted offset), from (n!)^(2n) (A185141) to a(n). This reduction is directly analogous to the identical reduction from latin squares (A002860) to reduced latin squares (A000315), and can be directly applied to the Latin Stable Marriage Problem (A351413). As with reduced latin squares, some further reduction is possible analogous to row/column reduced latin squares (A123234).
It is tempting to aim for a reduction of (n!)^2 by simultaneously normalizing all of man #1 and woman #1's preferences, but that isn't possible unless man #1 and woman #1 happen to be mutual first choices.
Applying this reduction to A344669 reduces A344669(2) and A344669(4) to 1, demonstrating that these maximal instances arising in A005154 are unique up to participant relabeling. It raises the question of which other values of n make A344669(n) reducible to 1.

Andrew Howroyd, Table of n, a(n) for n = 1..20
Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021, [Section 7, Symmetries].

Cf. A185141, A000315, A351413, A344669.

a[n_] := n*(n!)^(2*n - 2); Table[a[n], {n, 1, 9}] (* Robert P. P. McKone, Feb 12 2022 *)

a(n) = n*(n!)^(2*n-2) \\ Andrew Howroyd, Feb 12 2022

a(n) = A185141(n) / A010790(n-1).

A069124 Number of stable matchings in a certain form of Pseudo-Latin squares of order n based on Latin subsquares.

Original entry on oeis.org

1, 2, 3, 10, 12, 32, 42, 268, 288, 656, 924, 4360, 3816, 11336, 13536, 195472, 200832, 423104, 618576, 2404960, 2506464, 6994784, 8820864, 85524160, 60669696, 145981952, 194348448, 1073479840

Offset: 1

N. J. A. Sloane, Apr 12 2002

a(n) is from Table 1 of Thurber's linked paper. The particular form of Pseudo-Latin squares is based on upper-left subsquares of the power-of-2 Latin squares of A005154, defined as G(n) in Section 3 of Thurber's paper. - Dan Eilers, May 16 2025
There is a possibility that some of the terms in this sequence from a(7) onward are incorrect. See A371810 for an alternative. - Sean A. Irvine, Apr 16 2024
a(7)=42 verified using MiniZinc, see linked file with details. - Dan Eilers, May 14 2025

Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, The Stable Matching Problem and Sudoku, arXiv:2108.02654 [math.HO], 2021.
Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021.
Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, The Stable Marriage Problem and Sudoku, College Math. J. (2023).
Dan Eilers, Response to Sean A. Irvine comment regarding a(7)=42, 2025.
Peter J. Stuckey, Kim Marriott, and Guido Tack, The MiniZinc Handbook, Listing 2.2.12, stable-marriage.mzn, Version 2.9.2, 6 March 2025.
E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Cf. A371810.

Cf. A005154 (power-of-2 Latin squares used as basis for subsquares). - Dan Eilers, May 16 2025

Name edited by Dan Eilers, May 16 2025

A351413 a(n) is the maximum number of stable matchings in the Latin Stable Marriage Problem of order n.

Original entry on oeis.org

1, 2, 3, 10, 9, 48, 61

Offset: 1

Dan Eilers, Feb 10 2022

In the Latin Stable Marriage Problem of order n, the sum of a man and woman's rankings of each other is n+1. This implies that the men's and women's ranking tables are Latin squares. As a subproblem of the Stable Marriage Problem, Latin instances provide lower bounds for the maximum number of stable matchings in the general problem, such as A005154 and A065982. For sizes 1 to 4, Latin instances provide exact bounds; they are conjectured to provide exact bounds for sizes a power of 2; they provide the best lower bounds known for sizes 6, 10, 12, and 24, of 48, 1000, 6472, and 126112960, respectively.
The next term, a(8), is conjectured to be 268, consistent with A005154. The minimum number of stable matchings for Latin instances of order n is n, and is realized for the cyclic group of order n. The average number of stable matchings is 7 for n=4 (cf. A351430 showing an average of about 1.5 for the general problem), and benefits from avoidance of mutual first choices and more generally the lack of overlap between the men's and women's preferred matchings. The Latin squares of A005154 and A065982 can be interpreted as multiplication tables of groups, n-th powers of the cyclic group C2 and n-th dihedral groups, respectively.
The sequence decreases from a(4)=10 to a(5)=9, in contrast to the corresponding sequence for the general problem, which Thurber showed to be strictly increasing. This has motivated the study of less restrictive subproblems, such as pseudo-Latin squares (A069124, A069156), Latin x Latin instances (A344664, A344665, A343697), instances where participants have different first choices (A343475, A343694, A343695), or instances with unspecified/tied/template rankings (A284458 with only first choices specified).
The sequence is empirically derived, originally based on reduced Latin squares (A000315). There are fewer instances to try using RC-equivalent Latin squares (A123234) instead of reduced Latin squares.

			Maximal instance of order 2 with 2 stable matchings:
  12
  21
Maximal instance of order 3 with 3 stable matchings:
  123
  231
  312
Maximal instance of order 4 with 10 stable matchings (group C2xC2):
  1234
  2143
  3412
  4321
Maximal instance of order 5 with 9 stable matchings:
  12345
  21453
  34512
  45231
  53124
Maximal instance of order 6 with 48 stable matchings (Dihedral group):
  123456
  214365
  365214
  456123
  541632
  632541
Maximal instance of order 7 with 61 stable matchings:
  1234567
  2316745
  3125476
  4657312
  5743621
  6471253
  7562134

C. Converse, Lower bounds for the maximum number of stable pairings for the general marriage problem based on the latin marriage problem, Ph. D. Thesis, Claremont Graduate School, Claremont, CA (1992) [Examples are from 69-70].

A. T. Benjamin, C. Converse, and H. A. Krieger, Note. How do I marry thee? Let me count the ways, Discrete Appl. Math. 59 (1995) 285-292.
Matvey Borodin, Eric Chen, Aidan Duncan, Tanya Khovanova, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, and Michael Voigt, Sequences of the Stable Matching Problem, arXiv:2201.00645 [math.HO], 2021 [Sections 3.7 and 4.2].
J. S. Hwang, Complete stable marriages and systems of I-M preferences, In: McAvaney K.L. (eds) Combinatorial Mathematics VIII. Lecture Notes in Mathematics, vol 884. Springer, Berlin, Heidelberg (1981) 49-63.
E. G. Thurber, Concerning the maximum number of stable matchings in the stable marriage problem, Discrete Math., 248 (2002), 195-219.

Cf. A005154 (powers of 2), A065982 (multiples of 2), A069156 (not necessarily Latin), A000315 (reduced Latin squares), A123234 (RC-equivalent Latin squares).

cp's OEIS Frontend

A076725 a(n) = a(n-1)^2 + a(n-2)^4, a(0) = a(1) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A351409 a(n) = n*(n!)^(2*n-2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A069124 Number of stable matchings in a certain form of Pseudo-Latin squares of order n based on Latin subsquares.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A351413 a(n) is the maximum number of stable matchings in the Latin Stable Marriage Problem of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A351409 a(n) = n(n!)^(2n-2).