Jeremy F. Alm - cp's OEIS frontend

A386593 Number of sub-relation-algebras of Re(n), the collection of all binary relations over {1,2,...,n}.

1, 2, 6, 30, 124

Offset: 1

Jeremy F. Alm, Jul 26 2025

The first four terms are not that difficult to verify. In fact, for n < 5 the subalgebra lattice of Re(n) is the dual of the subgroup lattice of S_n. Hence a(n) = A005432(n) for n < 5.

Relation algebras are closed under union, intersection, complement, composition, inverse, and identity.

Bjarni Jónsson, Maximal algebras of binary relations. In: Contributions to Group Theory, Contemporary Mathematics, vol. 33, pp. 299-307. Amer. Math. Soc., Providence (1984).

Cf. A005432.

A367537 a(n) is the number of ways to make a Secret Santa assignment among n couples such that no one gets their partner's name and if A gets B's name, B does not get A's name.

Original entry on oeis.org

0, 2, 48, 2652, 251328, 34213080, 6362490816

Offset: 1

Jeremy F. Alm, Nov 21 2023

Equivalent to the number of derangements of [2n] such that (i) there are no 2-cycles, and (ii) neither k nor k+n maps to the other (k <= n).
A367538(n) <= a(n) <= A038205(2n) <= A000166(2n), and all the inequalities are strict except for n = 1.
Inspired by a question from a coworker about enumerating all possible Secret Santa assignments for an actual Secret Santa exchange for Xmas 2023, subject to these constraints.

Cf. A000166, A038205, A367538.

A367538 a(n) is the number of ways to make a Secret Santa assignment among n couples such that (i) no one gets their partner's name, (ii) if A gets B's name, B does not get A's name, and (iii) if A gets B's name, then A's partner does not get B's partner's name.

Original entry on oeis.org

0, 0, 32, 1200, 126720, 17862400, 3403153920

Offset: 1

Jeremy F. Alm, Nov 21 2023

Equivalent to the number of derangements of [2n] such that (i) there are no 2-cycles, (ii) neither k nor k+n maps to the other (k <= n), and (iii) we never have that both k maps to m and k+n maps to m+n.
a(n) <= A367537(n) <= A038205(2n) <= A000166(2n), and all the inequalities are strict except for n = 1.
Inspired by a question from a coworker about enumerating all possible Secret Santa assignments for an actual Secret Santa exchange for Xmas 2023, subject to these constraints.

Cf. A000166, A038205, A367537.

A366552 a(n) is the index of the first row of A296142 in which n appears, or 0 if n does not appear.

Original entry on oeis.org

0, 1, 104, 122, 0, 130, 3, 9, 103, 0, 119, 5, 11, 105, 0, 121, 7, 13, 107, 0, 123, 9, 15, 109, 0, 125, 11, 17, 111, 0

Offset: 1

Jeremy F. Alm, Oct 13 2023

a(5k) = 0 for all k, since no multiple of 5 appears in A296142.

Cf. A296142, A321351.

A321351 a(n) is the index of the row of A321350 in which n first appears, or zero if n does not appear.

Original entry on oeis.org

0, 1, 0, 26, 3, 0, 19, 5, 0, 21, 7, 0, 23, 9, 0, 25, 11, 0, 27, 13, 0, 29, 15, 0, 2, 17, 0, 4, 19, 0, 6, 21, 0, 8, 23, 0, 10, 25, 0, 12, 27, 0, 14, 29, 0, 16, 31, 0, 18, 33, 0, 20, 35, 0, 22

Offset: 1

Jeremy F. Alm, Nov 06 2018

No multiple of 3 appears, so a(3n) = 0 for all n.

			a(5) = 3, since in A321350, 2 --> (2+3)^2 --> 5, so 5 first appears in the third row.

Cf. A296142, A321350.

a(n) <= (2/3)*n + 15 for n > 6.

A321350 Triangle read by rows: first row is 2; given row k, define the elements of row k+1 to be the (sorted) elements derived from row k by two recursion rules: (i.) if x is in row k, then (x+3)^2 is in row k+1; (ii.) if x^2 is in row k, then x is in row k+1.

Original entry on oeis.org

2, 25, 5, 784, 28, 64, 619369, 8, 787, 961, 4489, 383621674384, 31, 67, 121, 619372, 624100, 929296, 20178064, 147165589059485451825769, 11, 790, 964, 1156, 4492, 4900, 15376, 383621674387, 383625390625, 389504554609, 863596631401, 407154387856489, 21657710603225344113280242498332241368243395984

Offset: 1

Jeremy F. Alm, Nov 06 2018

A variant of A296142, a sequence inspired by problem A1 on the 2017 William Lowell Putnam Mathematical Competition.

			First few rows are
2;
25;
5, 784;
28, 64, 619369;
8, 787, 961, 4489, 383621674384;
31, 67, 121, 619372, 624100, 929296, 20178064, 147165589059485451825769;
11, 790, 964, 1156, 4492, 4900, 15376, 383621674387, 383625390625, 389504554609, 863596631401, 407154387856489, 21657710603225344113280242498332241368243395984;

Cf. A296142, A321351.

A320837 For p the n-th prime congruent to 1 (mod 4), a(n) is the clique number of the subgraph of the quadratic residue (Paley) graph over F_p, the field of order p, that is induced by the set of vertices that are themselves quadratic residues.

Original entry on oeis.org

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

Offset: 1

Jeremy F. Alm, Oct 21 2018

			a(1) = 1 because the subgraph of the Paley graph of order 5 induced by {1,4} is the two-vertex empty graph.

Eric Weisstein's World of Mathematics, Clique Number
Eric Weisstein's World of Mathematics, Paley Graph

Cf. A002144 (primes of form 4n + 1), A320757.

A320757 For p the n-th prime congruent to 1 (mod 4), a(n) is the clique number of the quadratic residue (Paley) graph over F_p, the field of order p.

Original entry on oeis.org

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

Offset: 1

Jeremy F. Alm, Oct 20 2018

			a(1) = 2, since the Paley graph of order 5 is a 5-cycle, and contains no triangle.

Eric Weisstein's World of Mathematics, Clique Number
Eric Weisstein's World of Mathematics, Paley Graph

Cf. A002144 (primes of form 4n + 1), A320837.

A305464 Largest prime modulus p such that there exists a multiplicative-coset Ramsey algebra in n colors over Z/pZ, or 0 if no such prime exists.

Original entry on oeis.org

5, 13, 41, 101, 277, 491, 0, 577, 1181, 1409, 1201, 0, 2801, 2851, 1217, 4013, 3061, 1901, 4241, 9619, 10781, 6947, 7681, 8501, 11597, 14149, 18089, 10847

Offset: 2

Jeremy F. Alm, Jun 01 2018

a(n) <= n^4 + 5 (cf. Alm, 2017). There cannot be arbitrarily large multiplicative-coset Ramsey algebras in a fixed number of colors.

a(n) < A294676(n).

Jeremy F. Alm, 401 and beyond: improved bounds and algorithms for the Ramsey algebra search, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.4. (Also here: arXiv:1609.01817 [math.NT], 2016.)

Cf. A263308, A294676.

A298566 a(n) is the smallest prime q congruent to 1 mod n such that for all primes p >= q with p congruent to 1 mod n, the multiplicative subgroup H of (Z/pZ)* of index n contains a nontrivial mod-p arithmetic progression of length 3.

Original entry on oeis.org

11, 31, 41, 41, 139, 211, 113, 199, 211, 617, 433, 1093, 379, 1381, 929, 2381, 3907, 2851, 1901, 1051, 2927, 2347, 3889, 2251, 2887, 3943, 2017, 2089, 4861, 2357, 7457, 8317, 8467, 6091, 8317, 3331, 7829, 17707, 8081, 7873, 16927, 17029, 15797, 13411, 17987, 41737, 12241

Offset: 2

Jeremy F. Alm, Jan 21 2018

nonn

Greater than A298565.

Jeremy F. Alm, Python program
Jeremy F. Alm, Arithmetic Progressions of Length Three in Multiplicative Subgroups of F_p, arXiv:1902.10046 [math.NT], 2019. Also in Integers (2020) Vol. 20A, Article #A1.

Cf. A298565.

cp's OEIS Frontend

User: Jeremy F. Alm

A386593 Number of sub-relation-algebras of Re(n), the collection of all binary relations over {1,2,...,n}.

Views

Author

Keywords

Comments

References

Crossrefs

A367537 a(n) is the number of ways to make a Secret Santa assignment among n couples such that no one gets their partner's name and if A gets B's name, B does not get A's name.

Views

Author

Keywords

Comments

Crossrefs

A367538 a(n) is the number of ways to make a Secret Santa assignment among n couples such that (i) no one gets their partner's name, (ii) if A gets B's name, B does not get A's name, and (iii) if A gets B's name, then A's partner does not get B's partner's name.

Views

Author

Keywords

Comments

Crossrefs

A366552 a(n) is the index of the first row of A296142 in which n appears, or 0 if n does not appear.

Views

Author

Keywords

Comments

Crossrefs

A321351 a(n) is the index of the row of A321350 in which n first appears, or zero if n does not appear.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A321350 Triangle read by rows: first row is 2; given row k, define the elements of row k+1 to be the (sorted) elements derived from row k by two recursion rules: (i.) if x is in row k, then (x+3)^2 is in row k+1; (ii.) if x^2 is in row k, then x is in row k+1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A320837 For p the n-th prime congruent to 1 (mod 4), a(n) is the clique number of the subgraph of the quadratic residue (Paley) graph over F_p, the field of order p, that is induced by the set of vertices that are themselves quadratic residues.

Views

Author

Keywords

Examples

Links

Crossrefs

A320757 For p the n-th prime congruent to 1 (mod 4), a(n) is the clique number of the quadratic residue (Paley) graph over F_p, the field of order p.

Views

Author

Keywords

Examples

Links

Crossrefs

A305464 Largest prime modulus p such that there exists a multiplicative-coset Ramsey algebra in n colors over Z/pZ, or 0 if no such prime exists.

Views

Author

Keywords

Comments

Links

Crossrefs

A298566 a(n) is the smallest prime q congruent to 1 mod n such that for all primes p >= q with p congruent to 1 mod n, the multiplicative subgroup H of (Z/pZ)* of index n contains a nontrivial mod-p arithmetic progression of length 3.

Views

Author

Keywords

Comments

Links

Crossrefs