المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية
القيمة الغذائية للثوم Garlic
2024-11-20
العيوب الفسيولوجية التي تصيب الثوم
2024-11-20
التربة المناسبة لزراعة الثوم
2024-11-20
البنجر (الشوندر) Garden Beet (من الزراعة الى الحصاد)
2024-11-20
الصحافة العسكرية ووظائفها
2024-11-19
الصحافة العسكرية
2024-11-19


Antichain  
  
1786   06:52 مساءً   date: 5-1-2022
Author : Agnew, R. P.
Book or Source : . "Minimax Functions, Configuration Functions, and Partitions." J. Indian Math. Soc. 24
Page and Part : ...


Read More
Date: 4-1-2022 796
Date: 11-1-2022 991
Date: 12-1-2022 1058

Antichain

Let P be a finite partially ordered set, then an antichain in P is a set of pairwise incomparable elements. Antichains are also called Sperner systems in older literature (Comtet 1974).

For example, consider P to be a family of subsets together with the subset relation (i.e., s_1<=s_2 if s_1 is a subset of s_2). The following table gives the antichains on the set of subsets (i.e., the power set) of the n-set {1,2,3,...,n} for small n.

n antichains
1 emptyset,{{1}}
2 emptyset,{{1}},{{2}},{{1},{2}},{{1,2}}
3 emptyset,{{1}},{{2}},{{3}},{{1,2}},
  {{1,3}},{{2,3}},{{1},{2}},{{1},{3}},
  {{2},{3}},{{1,2,3}},{{1},{2,3}},{{1,2},{2,3}},
  {{1,2},{1,3}},{{1,2},{3}},{{2},{1,3}},
  {{2,3},{1,3}},{{1},{2},{3}},{{1,2},{2,3},{1,3}}

The number of antichains on the n-set {1,2,...,n} for n=0, 1, 2, ..., are 1, 2, 5, 19, 167, ... (OEIS A014466). If the empty set is not considered a valid antichain, then these reduce to 0, 1, 4, 18, 166, ... (OEIS A007153; Comtet 1974, p. 273). The numbers obtained by adding one to OEIS A014466, 2, 3, 6, 20, 168, 7581, 7828354, ... (OEIS A000372), are also frequently encountered (Speciner 1972).

The number of antichains on the n-set are equal to the number of monotonic increasing Boolean functions of n variables, and also the number of free distributive lattices with n generators (Comtet 1974, p. 273). Determining these numbers is known as Dedekind's problem, and the numbers in each of these sequences are sometimes called Dedekind numbers.

The partial order width of P is the maximum cardinal number of an antichain in P. For a partial order, the size of the longest antichain is called the partial order width w(P). Sperner (1928) proved that the maximum size (and hence the width of the partial order) of an antichain containing n elements is

 w_(max(n))=(n; |_n/2_|),

where (n; k) is a binomial coefficient and |_n_| is the floor function.


REFERENCES:

Agnew, R. P. "Minimax Functions, Configuration Functions, and Partitions." J. Indian Math. Soc. 24, 1-21, 1961.

Anderson, I. Combinatorics of Finite Sets. Oxford, England: Oxford University Press, p. 38, 1987.

Arocha, J. L. "Antichains in Ordered Sets" [Spanish]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27, 1-21, 1987.

Berman, J. "Free Spectra of 3-Element Algebras." In Universal Algebra and Lattice Theory (Puebla, 1982) (Ed. R. S. Freese and O. C. Garcia). New York: Springer-Verlag, 1983.

Berman, J. and Koehler, P. "Cardinalities of Finite Distributive Lattices." Mitteilungen aus dem Mathematischen Seminar Giessen 121, 103-124, 1976.

Birkhoff, G. Lattice Theory, 3rd ed. Providence, RI: Amer. Math. Soc., p. 63, 1967.

Church, R. "Numerical Analysis of Certain Free Distributive Structures." Duke Math. J. 6, 732-733, 1940.

Church. "Enumeration by Rank of the Elements of the Free Distributive Lattice with Seven Generators." Not. Amer. Math. Soc. 12, 724, 1965.

Comtet, L. "Sperner Systems." §7.2 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 271-273, 1974.

Dedekind, R. "Über Zerlegungen von Zahlen durch ihre grössten gemeinsammen Teiler." In Gesammelte Werke, Bd. 1. pp. 103-148, 1897.

Erdős, P.; Ko, Chao; and Rado, R. "Intersection Theorems for Systems of Finite Sets." Quart. J. Math. Oxford 12, 313-320, 1961.

Gilbert, E. N. "Lattice Theoretic Properties of Frontal Switching Networks." J. Math. Phys. 33, 57-97, 1954.

Hansel, G. "Problèmes de dénombrement et d'évaluation de bornes concernant les éléments du trellis distributif libre." Publ. Inst. Statist. Univ. Paris 16, 163-294, 1967.

Harrison, M. A. Introduction to Switching and Automata Theory. New York: McGraw-Hill, p. 188, 1965.

Hilton, A. J. W. and Milner, E. C. "Some Intersection Theorems of Systems of Finite Sets." Quart. J. Math. Oxford 18, 369-384, 1967.

Katona, G. "On a Conjecture of Erdős and a Stronger Form of Sperner's Theorem." Studia Sci. Math. Hung. 1, 59-63, 1966.

Katona, G. "A Theorem of Finite Sets." In Theory of Graphs, Proceedings of the Colloquium Held at Tihany, Hungary, September 1966 (Ed. P. Erdős and G. Katona). New York: Academic Press, pp. 187-207, 1968.

Kleitman, D. "A Conjecture of Erdős-Katona on Commensurable Pairs Among Subsets of a n-Set." In Theory of Graphs, Proceedings of the Colloquium Held at Tihany, Hungary, September 1966 (Ed. P. Erdős and G. Katona). New York: Academic Press, pp. 215-218, 1968.

Kleitman, D. "On Dedekind's Problem: The Number of Monotone Boolean Functions." Proc. Amer. Math. Soc. 21, 677-682, 1969.

Kleitman, D. and Markowsky, G. "On Dedekind's Problem: The Number of Isotone Boolean Functions. II." Trans. Amer. Math. Soc. 213, 373-390, 1975.

Lunnon, W. F. "The IU Function: The Size of a Free Distributive Lattice." In Combinatorial Mathematics and Its Applications: Proceedings of a conference held at the Mathematical Institute, Oxford, from 7-10 July, 1969 (Ed. D. J. A. Welsh). New York: Academic Press, pp. 173-181, 1971.

Mešalkin, L. D. "A Generalization of Sperner's Theorem on the Number of Subsets of a Finite Set." Theory Prob. 8, 203-204, 1963.

Milner, E. C. "A Combinatorial Theorem on Systems of Sets." J. London Math. Soc. 43, 204-206, 1968.

Muroga, S. Threshold Logic and Its Applications. New York: Wiley, p. 38 and 214, 1971.

Rivière, N. M. "Recursive Formulas on Free Distributive Lattices." J. Combin. Th. 5, 229-234, 1968.

Shapiro. "On the Counting Problem for Monotone Boolean Functions." Comm. Pure Appl. Math. 23, 299-312, 1970.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 241, 1990.

Sloane, N. J. A. Sequences A006826/M2469, A007153/M3551, and A014466 in "The On-Line Encyclopedia of Integer Sequences."

Speciner, M. Item 18 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 10, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item18.

Sperner, E. "Ein Satz über Untermengen einer endlichen Menge." Math. Z. 27, 544-548, 1928.

Ward, M. "Note on the Order of the Free Distributive Lattice." Bull. Amer. Math. Soc. 52, 423, 1946.

Yamamoto, K. "Logarithmic Order of Free Distributive Lattice." J. Math. Soc. Japan 6, 343-353, 1954.




الجبر أحد الفروع الرئيسية في الرياضيات، حيث إن التمكن من الرياضيات يعتمد على الفهم السليم للجبر. ويستخدم المهندسون والعلماء الجبر يومياً، وتعول المشاريع التجارية والصناعية على الجبر لحل الكثير من المعضلات التي تتعرض لها. ونظراً لأهمية الجبر في الحياة العصرية فإنه يدرّس في المدارس والجامعات في جميع أنحاء العالم. ويُعجب الكثير من الدارسين للجبر بقدرته وفائدته الكبيرتين، إذ باستخدام الجبر يمكن للمرء أن يحل كثيرًا من المسائل التي يتعذر حلها باستخدام الحساب فقط.وجاء اسمه من كتاب عالم الرياضيات والفلك والرحالة محمد بن موسى الخورازمي.


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

تعتبر المعادلات التفاضلية خير وسيلة لوصف معظم المـسائل الهندسـية والرياضـية والعلمية على حد سواء، إذ يتضح ذلك جليا في وصف عمليات انتقال الحرارة، جريان الموائـع، الحركة الموجية، الدوائر الإلكترونية فضلاً عن استخدامها في مسائل الهياكل الإنشائية والوصف الرياضي للتفاعلات الكيميائية.
ففي في الرياضيات, يطلق اسم المعادلات التفاضلية على المعادلات التي تحوي مشتقات و تفاضلات لبعض الدوال الرياضية و تظهر فيها بشكل متغيرات المعادلة . و يكون الهدف من حل هذه المعادلات هو إيجاد هذه الدوال الرياضية التي تحقق مشتقات هذه المعادلات.