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

 

Logo


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)
39

%I M3068 N1244

%S 1,1,3,19,219,4231,130023,6129859,431723379,44511042511,6611065248783,

%T 1396281677105899,414864951055853499,171850728381587059351,

%U 98484324257128207032183,77567171020440688353049939,83480529785490157813844256579,122152541250295322862941281269151,241939392597201176602897820148085023

%N Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs).

%C From _Altug Alkan_, Dec 22 2015: (Start)

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

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

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

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

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

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

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

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

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

%C 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.

%C 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,...

%C (End)

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

%D 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.

%D 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.

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

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

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

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

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

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

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

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

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

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

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

%H Juliana Bowles and Marco B. Caminati, <a href="https://arxiv.org/abs/1705.07228">A Verified Algorithm Enumerating Event Structures</a>, arXiv:1705.07228 [cs.LO], 2017.

%H G. Brinkmann, B. D. McKay, <a href="http://dx.doi.org/10.1023/A:1016543307592">Posets on up to 16 Points</a>, Order 19 (2) (2002) 147-179

%H J. I. Brown and S. Watson, <a href="http://dx.doi.org/10.1016/0012-365X(95)00004-G">The number of complements of a topology on n points is at least 2^n (except for some special cases)</a>, Discr. Math., 154 (1996), 27-39.

%H K. K.-H. Butler and G. Markowsky, <a href="http://www.laptop.maine.edu/Enumeration.pdf">Enumeration of finite topologies</a>, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184

%H K. K.-H. Butler and G. Markowsky, <a href="/A000798/a000798_1.pdf">Enumeration of finite topologies</a>, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H S. D. Chatterji, <a href="/A000798/a000798_10.pdf">The number of topologies on n points</a>, Manuscript, 1966 [Annotated scanned copy]

%H M. Erné, <a href="http://dx.doi.org/10.1007/BF01173716">Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen</a>, Manuscripta Math., 11 (1974), 221-259.

%H M. Erné, <a href="/A006056/a006056.pdf">Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen</a>, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)

%H M. Erné and K. Stege, <a href="/A006870/a006870.pdf">The number of partially ordered (labeled) sets</a>, Preprint, 1989. (Annotated scanned copy)

%H M. Erné and K. Stege, <a href="http://dx.doi.org/10.1007/BF00383446">Counting Finite Posets and Topologies</a>, Order, 8 (1991), 247-265.

%H J. W. Evans, F. Harary and M. S. Lynn, <a href="/A000798/a000798_8.pdf"> On the computer enumeration of finite topologies</a>, Commun. ACM, 10 (1967), 295-297, 313. [Annotated scanned copy]

%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Transitive relations, topologies and partial orders</a>

%H G. Grekos, <a href="/A000112/a000112_1.pdf">Letter to N. J. A. Sloane, Oct 31 1994, with attachments</a>

%H Dongseok Kim, Young Soo Kwon, Jaeun Lee, <a href="http://arxiv.org/abs/1206.0550">Enumerations of finite topologies associated with a finite graph</a>, arXiv preprint arXiv:1206.0550 [math.CO], 2012. - From _N. J. A. Sloane_, Nov 09 2012

%H M. Y. Kizmaz, <a href="http://arxiv.org/abs/1503.08359">On The Number Of Topologies On A Finite Set</a>, arXiv preprint arXiv:1503.08359 [math.NT], 2015.

%H G. Kreweras, <a href="http://dx.doi.org/10.1016/0012-365X(85)90137-2">Dénombrement des ordres étagés</a>, Discrete Math., 53 (1985), 147-149.

%H Institut f. Mathematik, Univ. Hanover, <a href="http://www-ifm.math.uni-hannover.de/html/preprints.phtml">Erne/Heitzig/Reinhold papers</a>

%H N. Lygeros and P. Zimmermann, <a href="http://www.lygeros.org/Math/poset.html">Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771</a>

%H G. Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

%H Bob Proctor, <a href="http://www.unc.edu/~rap/Posets/">Chapel Hill Poset Atlas</a>

%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

%H Rosenberg, Ivo; <a href="http://dx.doi.org/10.1016/0097-3165(73)90058-7">The number of maximal closed classes in the set of functions over a finite domain</a>, J. Combinatorial Theory Ser. A 14 (1973), 1-7.

%H Ivo Rosenberg and N. J. A. Sloane, <a href="/A002824/a002824_1.pdf">Correspondence, 1971</a>

%H D. Rusin, <a href="http://www.math.niu.edu/~rusin/known-math/97/finite.top">Further information and references</a> [Broken link]

%H D. Rusin, <a href="/A000112/a000112.top.txt">Further information and references</a> [Cached copy]

%H N. J. A. Sloane, <a href="/A000112/a000112_2.pdf">List of sequences related to partial orders, circa 1972</a>

%H N. J. A. Sloane, <a href="/A000112/a000112_2.pdf">List of sequences related to partial orders, circa 1972</a>

%H N. J. A. Sloane, <a href="/classic.html#LOSS">Classic Sequences</a>

%H J. A. Wright, <a href="/A000798/a000798_3.pdf">There are 718 6-point topologies, quasiorderings and transgraphs</a>, Preprint, 1970 [Annotated scanned copy]

%H J. A. Wright, <a href="/A000798/a000798_4.pdf">Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences</a>

%H <a href="/index/Pos#posets">Index entries for sequences related to posets</a>

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

%F Related to A000112 by Erné's formulas: 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).

%F From _Altug Alkan_, Dec 22 2015: (Start)

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

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

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

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

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

%F (End)

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

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

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

%K nonn,nice

%O 0,3

%A _N. J. A. Sloane_

%E a(15)-a(16) from Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 23:15 EST 2018. Contains 299595 sequences. (Running on oeis4.)