பெல் எண்

சேர்வியல் கணிதத்தில், பெல் எண்ணானது (Bell number) ஒரு கணத்தின் பிரிவினைகளின் எண்ணிக்கையைத் தருகிறது. 19 ஆம் நூற்றாண்டிலிருந்து கணிதவியலாளர்களால் மேற்கொள்ளப்பட்ட இவ்வெண்கள் பற்றிய ஆய்வின் துவக்கம் சப்பானின் நடுக்காலமாக (1185-1600) அறியப்பட்டாலும், 1930 களில் இவ்வெண்கள் பற்றிய குறிப்புகளைத் தந்த கணிதவியலாளர் எரிக் டெம்பிள் பெல் என்பாரின் பெயராலேயே அழைக்கப்படுகின்றன.

B₀ = B₁ = 1 என்பதில் தொடங்கியமையும் பெல் எண்கள்::

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ... (OEIS-இல் வரிசை A000110)

.

n உறுப்புகள் கொண்ட பிரிவினைகளாக ஒரு கணத்தை எத்தனை வெவ்வேறு வழிகளில் பிரிக்கலாம் என்பதை, n ஆவது பெல் எண் B_n தருகிறது. அதாவது அக்கணத்தின் மீதான சமான உறவுகளின் எண்ணிக்கையைக் குறிக்கிறது. கணிதத்தில் மட்டுமல்லாது கவிதைகளில் n- வரிசைகள் கொண்ட கவிதைகளில் எத்தனை வேறுபட்ட ஒலி இயைபு அமைவுகள் இருக்க முடியும் என்ற எண்ணிக்கையைத் தருகிறது.^[1]

நிகழ்தகவுப் பரவல்களின் விலக்கப் பெருக்குத் தொகைகளாகவும் (moments of probability distributions) பெல் எண்கள் உள்ளன. குறிப்பாக, கூட்டுச்சராசரி 1 கொண்ட பாய்சான் பரவலின் n ஆம் விலக்கப் பெருக்குத்தொகை B_n ஆகும்.

கணப் பிரிவினைகள் தொகு

5 உறுப்புகள் கொண்ட கணத்தின் 52 பிரிவினைகள்.

பொதுவாக ஒரு கணத்தின், n உறுப்புகள் கொண்ட பிரிவினைகளின் எண்ணிக்கையை B_n குறிக்கிறது. ஒரு கணத்தின் (S) பிரிவினை என்பது, அக்கணத்தின் ஒவ்வொரு உறுப்பும் ஒரேயொரு உட்கணத்தில் மட்டும் உள்ளவாறு பிரிக்கப்படுகின்ற மூலகணத்தின் (S) வெற்றில்லா உட்கணங்களின் கணமாகும். இப்பிரிவினை கணங்களின் சேர்ப்பு, மூலகணம் (S) ஆக அமையும்.

எடுத்துக்காட்டாக, 3-உறுப்பு கணத்தை ( {a, b, c}) 5 வெவ்வேறான வகைகளில் பிரிக்கலாம் என்பதால் B₃ = 5:

{ {a}, {b}, {c} }

{ {a}, {b, c} }

{ {b}, {a, c} }

{ {c}, {a, b} }

{ {a, b, c} }.

வெற்றுக் கணத்திற்கு ஒரெயொரு பிரிவினை மட்டுமே உள்ளதால், B₀ = 1. வெற்றுக் கணத்தின் ஒவ்வொரு உட்கணமும் வெற்றற்ற கணமாகவும் அவற்றின் சேர்ப்பு வெற்று கணமாகவும் கொள்ளப்படுவதால், வெற்றுக் கணத்திற்கு அது மட்டுமே பிரிவினையாக அமையும். பிரிவினைகள் அல்லது உறுப்புகளின் வரிசை கணக்கில் எடுத்துக்கொள்ளப்படவில்லை. அதாவது கீழ்வருபவை முற்றொத்தவைகளாகும்:

{ {b}, {a, c} }

{ {a, c}, {b} }

{ {b}, {c, a} }

{ {c, a}, {b} }.

மாறாக, கணங்களின் வரிசையைக் கணக்கில் எடுத்துக்கொண்டால் அவை வெவ்வேறான பிரிவினைகளைத் தரும். இந்த வரிசைப்படுத்தப்பட்ட பிரிவினைகளின் எண்ணிக்கை வரிசைப்படுத்தப்பட்ட பெல் எண்கள் எனப்படும்.

காரணியாக்கம் தொகு

N ஒரு வர்க்கக்காரணியற்ற முழுஎண் (வெவ்வேறான n பகா எண்களின் பெருக்கலாக அமையும் எண்) எனில், அதன் வெவ்வேறான பெருக்கல் பகிர்வுகளின் எண்ணிக்கையை B_n குறிக்கும். N இன் இப்பெருக்கல் பகிர்வுகள் ஒன்றைவிடப் பெரிய எண்களைக் காரணிகளாகக் கொண்டிருக்கும்; மேலும் ஒரே கார ணிகளை வெவ்வேறான வரிசையில் கொண்ட பெருக்கல் பகிர்வுகள் முற்றொத்தவையாகக் கருதப்படும்.^[2]

எடுத்துக்காட்டாக, எண் 30 ஆனது பகா எண்கள் 2, 3, 5 இன் பெருக்குத்தொகையாகும். அதன் ஐந்துவிதமான காரணியாக்கங்கள்:

30\times 1=2\times 15=3\times 10=5\times 6=2\times 3\times 5

ஒலியியைபு அமைப்புகள் தொகு

n-வரிகள் கொண்ட கவிதைகளில்ல் அமையக்கூடிய ஒலியியைபு அமைப்புகளின் எண்ணிக்கையை பெல் எண்கள் குறிக்கின்றன. ஒன்றோடொன்று ஒலியியைபுடைய வரிகளை ஒலியியைபு அமைப்பு குறிப்பதால், வரிகளை உறுப்புகளாகக் கொண்ட கணத்தின் பிரிவினையாக இருக்கும். இப்பிரிவினை ஒலியியைபுகளை உறுப்புகளாகக் கொண்ட உட்கணங்களாகும். ஒரு வரிக்கு ஒரு ரோம எழுத்துவீதமாக, ஒன்றுக்கொன்று ஒத்த ஒலியியைபுடைய வரிகளுக்கு ஒரே ரோம எழுத்து குறிக்கப்பட்ட ரோம எழுத்துக்களின் தொடர்வரிசையாக ஒலியியைபு அமைப்புகள் அமைகின்றன.

நான்கு வரிகளில் அமையக்கூடிய 15 விதமான ஒலியியைபு அமைப்புகள்:

AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD.^[1]

முக்கோண வடிவமைப்பு மூலம் கணக்கிடல் தொகு

வலதுபுற மூலைவிட்ட தொடர்வரிசையில் பெல் எண்களைக் கொண்ட முக்கோண அமைப்பு

பெல் முக்கோணம் மூலம் பெல் எண்களைக் காணமுடியும். அலெக்சாண்டர் அயிட்கென் மற்றும் சார்லசு சாண்டர்சு பியர்சு என்ற கணிதவியலாளர்களின் பெயரால் பெல் முக்கோணம் அயிட்கென்னின் வரிசை (Aitken's array) அல்லது பியர்சு முக்கோணம் என அழைக்கப்படுகிறது.^[3]

முதல் வரிசையில் எண் 1 எழுதிக்கொள்ளப்படுகிறது:

x_{0,1}=1

அடுத்த வரிசையின் இடதுகோடி உறுப்பாக முந்தைய வரிசையின் வலதுகோடி உறுப்பு எழுதப்படுகிறது:

x_{i,1}\leftarrow x_{i-1,r}

இதில் (i-1)-th வரிசையின் கடைசி உறுப்பு r.

இடதுகோடி உறுப்பையும் அதற்கு மேலுள்ள முந்தைய வரிசையின் உறுப்பையும் கூட்டக்கிடைக்கும் எண் இந்த வரிசையின் அடுத்த உறுப்பாகும்:

(x_{i,j}\leftarrow x_{i,j-1}+x_{i-1,j-1})

.

அதாவது,

இரண்டாவது வரிசையின் இடதுகோடி உறுப்பு 1. அதற்கடுத்த உறுப்பு 1+1 = 2.

முதல் வரிசையை விட ஒரு உறுப்பு அதிகமாக இருக்கும்வரை இச்செயல் தொடரப்படுகிறது.

இவ்வாறு அடுத்தடுத்த வரிசைகள் உருவாக்கப்படுகின்றன.

ஒவ்வொரு வரிசையின் இடதுகோடி எண்ணும் பெல் எண்ணாக இருக்கும்:

B_{i}\leftarrow x_{i,1}

இம்முறைப்படி உருவாக்கப்பட்ட முக்கோணத்தின் முதல் ஐந்து வரிசைகள்:

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52

முக்கோணத்தின் இடது மற்றும் வலது பக்கங்களில் பெல் எண்கள் உள்ளன.

பண்புகள் தொகு

கூட்டுத்தொகை வாய்பாடுகள் தொகு

ஈருறுப்புக் குணகங்களைக் கொண்ட கீழ்வரும் மீள்வரு தொடர்பை பெல் எண்கள் நிறைவு செய்யும்:^[4]

B_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}.

ஒவ்வொரு பெல் எண்ணும் இசுடர்லிங் உட்கண எண்களின் கூடுதலாக அமையும்:

B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}.

இவ்விரு வாய்பாடுகளும் இணைந்த வாய்பாடு ((Spivey 2008)):

B_{n+m}=\sum _{k=0}^{n}\sum _{j=0}^{m}\left\{{m \atop j}\right\}{n \choose k}j^{n-k}B_{k}.

பிறப்பாக்கிச் சார்பு தொகு

பெல் எண்களின் படிக்குறி பிறப்பாக்கிச் சார்பு:

B(x)=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=e^{e^{x}-1}.

நிகழ்தகவுப் பரவல்களின் விலக்கப் பெருக்குத்தொகைகள் தொகு

B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.

^[5]

படிக்குறிச் சார்பின் டெய்லர் தொடரைப் பயன்படுத்தி பிறப்பாக்கிச் சார்பை விரிவாக்கியபின் அவ்விரிவிலுள்ள ஒரே அடுக்குள்ள உறுப்புகளை சேகரிப்பதன் மூலம் இவ்வாய்பாடைப் பெறலாம்.^[6] இதன் மூலம் பெல் எண் B_n எதிர்வுப் பெறுமதி 1 கொண்ட பாய்சான் பரவலின் n ஆவது விலக்கப் பெருக்குத்தொகையாகும்.

n ஆவது பெல் எண், n ஆவது பெல் பல்லுறுப்புக்கோவையின் குணகங்களின் கூட்டுத்தொகையாக அமையும். மேலும் n ஆவது பெல் எண், ஏதேனுமொரு நிகழ்தகவுப் பரவலின் n ஆவது விலக்கப் பெருக்குத்தொகையை, முதல் n குவிப்பெருக்கங்களின் சார்பாகத் தரும்.

சமான எண்கணிதம் தொகு

p ஒரு பகா எண் எனில்^[7]:

B_{p+n}\equiv B_{n}+B_{n+1}{\pmod {p}}

பொதுவடிவம்^[8]:

B_{p^{m}+n}\equiv mB_{n}+B_{n+1}{\pmod {p}}.

ஒவ்வொரு பகா எண் p க்கும், பெல் எண்கள் மாடுலோ p காலமுறை கொண்டது. எடுத்துக்காட்டாக p = 2 எனில், பெல் எண்கள் ஒற்றை-ஒற்றை-இரட்டை என்ற வடிவில் காலமுறையளவு மூன்றுடையதாக மீள்கின்றன. ஏதேனுமொரு பகாஎண் p எனில் இம்மீளலின் காலமுறையளவு ${\frac {p^{p}-1}{p-1}}$ -இன் வகுஎண்ணாக இருக்கும். மேலும், p ≤ 101 எனும் அனைத்துப் பகாஎண்கள் மற்றும் p = 113, 163, 167, 173 ஆகியவற்றுக்கு இதே எண்ணாக இருக்கும் (OEIS-இல் வரிசை A001039) .^[9]

மாடுலோ n இன் பெல் எண்களின் காலமுறையளவு:

1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, 25239592216021, 411771, 10153, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784341, 85593501183, 949112181811268728834319677753, 312, 3905, 75718776648063, 117, 1647084, 91703076898614683377208150526107718802981, 30459, 568972471024107865287021434301977158534824481, 96, 370905171793, 155107549103688143283, 107197717, 156, ... (OEIS-இல் வரிசை A054767)

தொகையீட்டு உருவகிப்பு தொகு

B_{n}={\frac {n!}{2\pi ie}}\int _{\gamma }{\frac {e^{e^{z}}}{z^{n+1}}}\,dz.

குறிப்புகள் தொகு

↑ ^1.0 ^1.1 (Gardner 1978).
↑ (Williams 1945) credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
↑ வார்ப்புரு:SloanesRef
↑ (Wilf 1994), p. 23.
↑ (Dobiński 1877); (Rota 1964); (Bender & Williamson 2006).
↑ (Flajolet & Sedgewick 2009).
↑ Becker & Riordan (1948).
↑ Hurst & Schultz (2009).
↑ (Williams 1945); (Wagstaff 1996).

மேற்கோள்கள் தொகு

Asai, Nobuhiro; Kubo, Izumi; Kuo, Hui-Hsiung (2000). "Bell numbers, log-concavity, and log-convexity". Acta Applicandae Mathematicae 63 (1-3): 79–87. doi:10.1023/A:1010738827855.
Alexander Aitken (1933). "A problem in combinations". Edinburgh Mathematical Notes 28: 18–23. doi:10.1017/S1757748900002334.
Becker, H. W.; John Riordan (mathematician) (1948). "The arithmetic of Bell and Stirling numbers". American Journal of Mathematics 70: 385–394. doi:10.2307/2372336. https://archive.org/details/sim_american-journal-of-mathematics_1948_70/page/385. .
Eric Temple Bell (1934). "Exponential polynomials". Annals of Mathematics 35: 258–277. doi:10.2307/1968431. https://archive.org/details/sim_annals-of-mathematics_1934-04_35_2/page/258. .
Eric Temple Bell (1938). "The iterated exponential integers". Annals of Mathematics 39: 539–557. doi:10.2307/1968633. https://archive.org/details/sim_annals-of-mathematics_1938-07_39_3/page/539. .
Bender, Edward A.; Williamson, S. Gill (2006). "Example 11.7, Set Partitions". Foundations of Combinatorics with Applications. Dover. பக். 319–320. பன்னாட்டுத் தரப்புத்தக எண்:0-486-44603-4. http://www.math.ucsd.edu/~ebender/CombText/ch-11.pdf.
Berend, D.; Tassa, T. (2010). "Improved bounds on Bell numbers and on moments of sums of random variables". Probability and Mathematical Statistics 30 (2): 185–205.
Berndt, Bruce C. (2011). "Ramanujan Reaches His Hand From His Grave To Snatch Your Theorems From You". Asia Pacific Mathematics Newsletter 1 (2): 8–13. http://www.asiapacific-mathnews.com/01/0102/0008_0013.pdf.
Nicolaas_Govert_de_Bruijn (1981). Asymptotic methods in analysis (3rd ). Dover. பக். 108.
Callan, David (2006). "A combinatorial interpretation of the eigensequence for composition". Journal of Integer Sequences 9 (1): 06.1.4. Bibcode: 2005math......7169C. https://eudml.org/doc/52955.
Canfield, E. Rodney (1995). "Engel's inequality for Bell numbers". Journal of Combinatorial Theory. Series A 72 (1): 184–187. doi:10.1016/0097-3165(95)90033-0.
Claesson, Anders (2001). "Generalized pattern avoidance". European Journal of Combinatorics 22 (7): 961–971. doi:10.1006/eujc.2001.0515.
John Horton Conway; Richard K. Guy (1996). "Famous Families of Numbers: Bell Numbers and Stirling Numbers". The Book of Numbers. Copernicus Series. Springer. பக். 91–94. பன்னாட்டுத் தரப்புத்தக எண்:9780387979939.
Dobiński, G. (1877). "Summirung der Reihe $\textstyle \sum {\frac {n^{m}}{n!}}$ für m = 1, 2, 3, 4, 5, …". Grunert's Archiv 61: 333–336. http://www.archive.org/stream/archivdermathem88unkngoog#page/n346.
Engel, Konrad (1994). "On the average rank of an element in a filter of the partition lattice". Journal of Combinatorial Theory. Series A 65 (1): 67–78. doi:10.1016/0097-3165(94)90038-8.
Philippe Flajolet; Robert Sedgewick (computer scientist) (2009). "II.3 Surjections, set partitions, and words". Analytic Combinatorics. Cambridge University Press. பக். 106–119. http://algo.inria.fr/flajolet/Publications/book.pdf.
Martin Gardner (1978). "The Bells: versatile numbers that can count partitions of a set, primes and even rhymes". சயன்டிஃபிக் அமெரிக்கன் 238: 24–30. doi:10.1038/scientificamerican0578-24. Reprinted with an addendum as "The Tinkly Temple Bells", Chapter 2 of Fractal Music, Hypercards, and more ... Mathematical Recreations from Scientific American, W. H. Freeman, 1992, pp. 24–38
Hazewinkel, Michiel, ed. (2001), "Bell numbers", Encyclopedia of Mathematics, Springer, ISBN 978-1556080104
Hurst, Greg; Schultz, Andrew (2009). "An elementary (number theory) proof of Touchard's congruence". arXiv:0906.0696 [math.CO]. {{cite arXiv}}: Invalid |ref=harv (help)
Donald Knuth (2013). "Two thousand years of combinatorics". in Wilson, Robin; Watkins, John J.. Combinatorics: Ancient and Modern. Oxford University Press. பக். 7–37.
László Lovász (1993). "Section 1.14, Problem 9". Combinatorial Problems and Exercises (2nd ). Amsterdam, Netherlands: North-Holland. பக். 17. http://books.google.com/books?id=e99fXXYx9zcC&pg=PA17.
Leo Moser; Wyman, Max (1955). "An asymptotic formula for the Bell numbers". Transactions of the Royal Society of Canada, Section III 49: 49–54.
Charles Sanders Peirce (1880). "On the algebra of logic". American Journal of Mathematics 3 (1): 15–57. doi:10.2307/2369442. .
Rota, Gian-Carlo (1964), "The number of partitions of a set", American Mathematical Monthly, 71 (5): 498–504, doi:10.2307/2312585, MR 0161805 {{citation}}: Invalid |ref=harv (help)
Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers". Journal of Integer Sequences 11 (2): Article 08.2.5, 3. http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Spivey/spivey25.pdf.
Sam Wagstaff (1996). "Aurifeuillian factorizations and the period of the Bell numbers modulo a prime". Mathematics of Computation 65 (213): 383–391. doi:10.1090/S0025-5718-96-00683-7. Bibcode: 1996MaCom..65..383W. http://homes.cerias.purdue.edu/~ssw/bell/bell.ps.
Herbert Wilf (1994). Generatingfunctionology (2nd ). Boston, MA: Academic Press. பன்னாட்டுத் தரப்புத்தக எண்:0-12-751956-4.
Williams, G. T. (1945). "Numbers generated by the function e^{e^x − 1}". American Mathematical Monthly 52: 323–327.

வெளியிணைப்புகள் தொகு

Robert Dickau. "Diagrams of Bell numbers".
Weisstein, Eric W., "Bell Number", MathWorld.
Gottfried Helms. "Further properties & Generalization of Bell-Numbers" (PDF).

[mg-1] 1.0 ^1.1 (Gardner 1978).

[2] (Williams 1945) credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).

[3] வார்ப்புரு:SloanesRef

[4] (Wilf 1994), p. 23.

[5] (Dobiński 1877); (Rota 1964); (Bender & Williamson 2006).

[analco-6] (Flajolet & Sedgewick 2009).

[FOOTNOTEBeckerRiordan1948-7] Becker & Riordan (1948).

[FOOTNOTEHurstSchultz2009-8] Hurst & Schultz (2009).

[9] (Williams 1945); (Wagstaff 1996).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]