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

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

Untitled Document
أبحث عن شيء أخر
تربية الماشية في جمهورية مصر العربية
2024-11-06
The structure of the tone-unit
2024-11-06
IIntonation The tone-unit
2024-11-06
Tones on other words
2024-11-06
Level _yes_ no
2024-11-06
تنفيذ وتقييم خطة إعادة الهيكلة (إعداد خطة إعادة الهيكلة1)
2024-11-05

المشارك الفطري Mycobiont
10-4-2019
Pareto Distribution
12-4-2021
نظرية توحيد العلوم وتوحيد القوى
17-4-2016
الزجَّاج
29-12-2015
التحلل الحيوي و الريزوسفير Rhizosphere
2023-11-02
في الاعواض
10-08-2015

Birthday Problem  
  
2568   05:25 مساءً   date: 6-3-2021
Author : Abramson, M. and Moser, W. O. J.
Book or Source : "More Birthday Surprises." Amer. Math. Monthly 77
Page and Part : ...


Read More
Date: 28-3-2021 1265
Date: 10-2-2021 1191
Date: 3-4-2021 2700

Birthday Problem

Consider the probability Q_1(n,d) that no two people out of a group of n will have matching birthdays out of d equally possible birthdays. Start with an arbitrary person's birthday, then note that the probability that the second person's birthday is different is (d-1)/d, that the third person's birthday is different from the first two is [(d-1)/d][(d-2)/d], and so on, up through the nth person. Explicitly,

Q_1(n,d) = (d-1)/d(d-2)/d...(d-(n-1))/d

(1)

= ((d-1)(d-2)...[d-(n-1)])/(d^(n-1)).

(2)

But this can be written in terms of factorials as

 Q_1(n,d)=(d!)/((d-n)!d^n),

(3)

so the probability P_2(n,d) that two or more people out of a group of n do have the same birthday is therefore

P_2(n,d) = 1-Q_1(n,d)

(4)

= 1-(d!)/((d-n)!d^n).

(5)

In general, let Q_i(n,d) denote the probability that a birthday is shared by exactly i (and no more) people out of a group of n people. Then the probability that a birthday is shared by k or more people is given by

 P_k(n,d)=1-sum_(i=1)^(k-1)Q_i(n,d).

(6)

In general, Q_k(n,d) can be computed using the recurrence relation

 Q_k(n,d)=sum_(i=1)^(|_n/k_|)[(n!d!)/(d^(ik)i!(k!)^i(n-ik)!(d-i)!)sum_(j=1)^(k-1)Q_j(n-ik,d-i)((d-i)^(n-ik))/(d^(n-ik))]

(7)

(Finch 1997). However, the time to compute this recursive function grows exponentially with k and so rapidly becomes unwieldy.

If 365-day years have been assumed, i.e., the existence of leap days is ignored, and the distribution of birthdays is assumed to be uniform throughout the year (in actuality, there is a more than 6% increase from the average in September in the United States; Peterson 1998), then the number of people needed for there to be at least a 50% chance that at least two share birthdays is the smallest n such that P_2(n,365)>=1/2. This is given by n=23, since

P_2(23,365) = (38093904702297390785243708291056390518886454060947061)/(75091883268515350125426207425223147563269805908203125)

(8)

 approx 0.507297.

(9)

The number n of people needed to obtain P_2(n,d)>=1/2 for d=1, 2, ..., are 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, ... (OEIS A033810). The minimal number of people to give a 50% probability of having at least n coincident birthdays is 1, 23, 88, 187, 313, 460, 623, 798, 985, 1181, 1385, 1596, 1813, ... (OEIS A014088; Diaconis and Mosteller 1989).

The probability P_2(n,d) can be estimated as

P_2(n,d)  approx 1-e^(-n(n-1)/2d)

(10)

 approx 1-(1-n/(2d))^(n-1),

(11)

where the latter has error

 epsilon<(n^3)/(6(d-n+1)^2)

(12)

(Sayrafiezadeh 1994).

Q_2 can be computed explicitly as

Q_2(n,d) = (n!)/(d^n)sum_(i=1)^(|_n/2_|)1/(2^i)(d; i)(d-i; n-2i)

(13)

= (d!)/(d^n(d-n)!)[_2F_1(1/2n,1/2(1-n);d-n+1;2)-1],

(14)

where (n; m) is a binomial coefficient and _2F_1(a,b,;c;z) is a hypergeometric function. This gives the explicit formula for P_3(n,d) as

P_3(n,d) = 1-Q_1(n,d)-Q_2(n,d)

(15)

= 1-d^(-n)d!_2F^~_1(1/2n,1/2(1-n);1+d-n;2),

(16)

where _2F^~_1(a,b;c;z) is a regularized hypergeometric function.

A good approximation to the number of people n such that p=P_k(n,d) is some given value can be given by solving the equation

 ne^(-n/(dk))=[d^(k-1)k!ln(1/(1-p))(1-n/(d(k+1)))]^(1/k)

(17)

for n and taking [n], where [n] is the ceiling function (Diaconis and Mosteller 1989). For p=0.5 and k=1, 2, 3, ..., this formula gives n=1, 23, 88, 187, 313, 459, 622, 797, 983, 1179, 1382, 1592, 1809, ... (OEIS A050255), which differ from the true values by from 0 to 4. A much simpler but also poorer approximation for n such that p=0.5 for k<20 is given by

 n=47(k-1.5)^(3/2)

(18)

(Diaconis and Mosteller 1989), which gives 86, 185, 307, 448, 606, 778, 965, 1164, 1376, 1599, 1832, ... for k=3, 4, ... (OEIS A050256).

The "almost" birthday problem, which asks the number of people needed such that two have a birthday within a day of each other, was considered by Abramson and Moser (1970), who showed that 14 people suffice. An approximation for the minimum number of people needed to get a 50-50 chance that two have a match within k days out of d possible is given by

 n(k,d)=1.2sqrt(d/(2k+1))

(19)

(Sevast'yanov 1972, Diaconis and Mosteller 1989).


REFERENCES:

Abramson, M. and Moser, W. O. J. "More Birthday Surprises." Amer. Math. Monthly 77, 856-858, 1970.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 45-46, 1987.

Bloom, D. M. "A Birthday Problem." Amer. Math. Monthly 80, 1141-1142, 1973.

Bogomolny, A. "Coincidence." http://www.cut-the-knot.org/do_you_know/coincidence.shtml.

Clevenson, M. L. and Watkins, W. "Majorization and the Birthday Inequality." Math. Mag. 64, 183-188, 1991.

Diaconis, P. and Mosteller, F. "Methods for Studying Coincidences." J. Amer. Statist. Assoc. 84, 853-861, 1989.

Feller, W. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. New York: Wiley, pp. 31-32, 1968.

Finch, S. "Puzzle #28 [June 1997]: Coincident Birthdays." http://www.mathcad.com/library/LibraryContent/puzzles/puzzle.asp?num=28.

Gehan, E. A. "Note on the 'Birthday Problem.' " Amer. Stat. 22, 28, Apr. 1968.

Heuer, G. A. "Estimation in a Certain Probability Problem." Amer. Math. Monthly 66, 704-706, 1959.

Hocking, R. L. and Schwertman, N. C. "An Extension of the Birthday Problem to Exactly k Matches." College Math. J. 17, 315-321, 1986.

Hunter, J. A. H. and Madachy, J. S. Mathematical Diversions. New York: Dover, pp. 102-103, 1975.

Klamkin, M. S. and Newman, D. J. "Extensions of the Birthday Surprise." J. Combin. Th. 3, 279-282, 1967.

Levin, B. "A Representation for Multinomial Cumulative Distribution Functions." Ann. Statistics 9, 1123-1126, 1981.

McKinney, E. H. "Generalized Birthday Problem." Amer. Math. Monthly 73, 385-387, 1966.

Mises, R. von. "Über Aufteilungs--und Besetzungs-Wahrscheinlichkeiten." Revue de la Faculté des Sciences de l'Université d'Istanbul, N. S. 4, 145-163, 1939. Reprinted in Selected Papers of Richard von Mises, Vol. 2 (Ed. P. Frank, S. Goldstein, M. Kac, W. Prager, G. Szegö, and G. Birkhoff). Providence, RI: Amer. Math. Soc., pp. 313-334, 1964.

Peterson, I. "MathTrek: Birthday Surprises." Nov. 21, 1998. http://www.sciencenews.org/sn_arc98/11_21_98/mathland.htm.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 179-180, 1994.

Sayrafiezadeh, M. "The Birthday Problem Revisited." Math. Mag. 67, 220-223, 1994.

Sevast'yanov, B. A. "Poisson Limit Law for a Scheme of Sums of Dependent Random Variables." Th. Prob. Appl. 17, 695-699, 1972.

Sloane, N. J. A. Sequences A014088, A033810, A050255, and A050256 in "The On-Line Encyclopedia of Integer Sequences."

Stewart, I. "What a Coincidence!" Sci. Amer. 278, 95-96, June 1998.

Tesler, L. "Not a Coincidence!" http://www.nomodes.com/coincidence.html.




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


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

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