login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS Foundation is grateful to everyone who made a donation during our Annual Appeal.     Visit the new and spectacular Pictures from the OEIS page!

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001035 Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs).
(Formerly M3068 N1244)
34
1, 1, 3, 19, 219, 4231, 130023, 6129859, 431723379, 44511042511, 6611065248783, 1396281677105899, 414864951055853499, 171850728381587059351, 98484324257128207032183, 77567171020440688353049939, 83480529785490157813844256579, 122152541250295322862941281269151, 241939392597201176602897820148085023 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

From Altug Alkan, Dec 22 2015: (Start)

a(p^k) == 1 mod p and a(n + p) == a(n + 1) mod p for all primes p.

a(0+19) == a(0+1) mod 19 or a(19^1) == 1 mod 19, that is, a(19) mod 19 = 1.

a(2+17) == a(2+1) mod 17. So a(19) == 19 mod 17, that is, a(19) mod 17 = 2.

a(6+13) == a(6+1) mod 13. So a(19) == 6129859 mod 13, that is, a(19) mod 13 = 8.

a(8+11) == a(8+1) mod 11. So a(19) == 44511042511 mod 11, that is, a(19) mod 11 = 1.

a(12+7) == a(12+1) mod 7. So a(19) == 171850728381587059351 mod 7, that is, a(19) mod 7 = 1.

a(14+5) == a(14+1) mod 5. So a(19) == 77567171020440688353049939 mod 5, that is, a(19) mod 5 = 4.

a(16+3) == a(16+1) mod 3. So a(19) == 122152541250295322862941281269151 mod 3, that is, a(19) mod 3 = 1.

a(17+2) == a(17+1) mod 2. So a(19) mod 2 = 1.

In conclusion, a(19) is a number of the form 2*3*5*7*11*13*17*19*n - 1615151, that is, 9699690*n - 1615151.

Additionally, for n > 0, note that the last digit of a(n) has the simple periodic pattern: 1,3,9,9,1,3,9,9,1,3,9,9,...

(End)

REFERENCES

G. Birkhoff, Lattice Theory, Amer. Math. Soc., 1961, p. 4.

K. K.-H. Butler, A Moore-Penrose inverse for Boolean relation matrices, pp. 18-28 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.

K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184.

S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.

L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 60, 229.

M. Erné, Struktur- und Anzahlformeln fuer Topologien auf endlichen Mengen, PhD dissertation, Westfaelische Wilhelms-Universitaet zu Muenster, 1972.

M. Erné and K. Stege, The number of labeled orders on fifteen elements, personal communication.

J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313.

J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000) no. 4, 333-341.

M. Y. Kizmaz, On The Number Of Topologies On A Finite Set, arXiv preprint arXiv:1503.08359, 2015

D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975) 205-220.

A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc., 8 (1968), 194-198.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, pages 96ff; Vol. 2, Problem 5.39, p. 88.

LINKS

Table of n, a(n) for n=0..18.

G. Brinkmann,  B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179

J. I. Brown and S. Watson, The number of complements of a topology on n points is at least 2^n (except for some special cases), Discr. Math., 154 (1996), 27-39.

K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184

K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

S. D. Chatterji, The number of topologies on n points, Manuscript, 1966 [Annotated scanned copy]

M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.

M. Erné and K. Stege, Counting Finite Posets and Topologies, Order, 8 (1991), 247-265.

J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313. [Annotated scanned copy]

S. R. Finch, Transitive relations, topologies and partial orders

G. Grekos, Letter to N. J. A. Sloane, Oct 31 1994, with attachments

Dongseok Kim, Young Soo Kwon, Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550 [math.CO], 2012. - From N. J. A. Sloane, Nov 09 2012

G. Kreweras, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147-149.

Institut f. Mathematik, Univ. Hanover, Erne/Heitzig/Reinhold papers

N. Lygeros and P. Zimmermann, Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771

G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Bob Proctor, Chapel Hill Poset Atlas

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

Rosenberg, Ivo; The number of maximal closed classes in the set of functions over a finite domain, J. Combinatorial Theory Ser. A 14 (1973), 1-7.

D. Rusin, Number of topologies

N. J. A. Sloane, List of sequences related to partial orders, circa 1972

N. J. A. Sloane, List of sequences related to partial orders, circa 1972

N. J. A. Sloane, Classic Sequences

J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970 [Annotated scanned copy]

J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences

Index entries for sequences related to posets

FORMULA

Related to A000798 by A000798(n) = Sum Stirling2(n, k)*A001035(k).

Related to A000112 by Erné's formulae: A001035(n+1)=-s(n, 1), A001035(n+2)=n*A001035(n+1)+s(n, 2), A001035(n+3)=binomial(n+4, 2)*A001035(n+2)-s(n, 3), where s(n, k)=sum(binomial(n+k-1-m, k-1)*binomial(n+k, m)*sum((m!)/(number of automorphisms of P)*(-(number of antichains of P))^k, P an unlabeled poset with m elements), m=0..n).

From Altug Alkan, Dec 22 2015: (Start)

a(p^k) == 1 mod p for all primes p and for all nonnegative integers k.

a(n + p) == a(n + 1) mod p for all primes p and for all nonnegative integers n.

If n = 1, then a(1 + p) == a(2) mod p, that is, a(p + 1) == 3 mod p.

If n = p, then a(p + p) == a(p + 1) mod p, that is, a(2*p) == a(p + 1) mod p.

In conclusion, a(2*p) == 3 mod p for all primes p.

(End)

EXAMPLE

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 shows the unlabeled posets with <= 4 points.

CROSSREFS

Cf. A000798 (labeled topologies), A001930 (unlabeled topologies), A000112 (unlabeled posets), A006057.

Sequences in the Erné (1974) paper: A000798, A001035, A006056, A006057, A001929, A001927, A006058, A006059, A000110.

Sequence in context: A005647 A158876 A001833 * A267634 A217906 A166380

Adjacent sequences:  A001032 A001033 A001034 * A001036 A001037 A001038

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Terms for n=15 and 16 from Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000

a(17) and a(18) from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 7 06:29 EST 2016. Contains 268050 sequences.