ಕ್ಯಾಟಲಾನ್ ಸಂಖ್ಯೆ

ಗಣಿತದಲ್ಲಿ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಎಂಬ ಕ್ಷೇತ್ರದಲ್ಲಿ "ಹತ್ತು ಕೆಂಪು ಮಣಿಗಳು ಮತ್ತು ಐದು ಹಸಿರುಮಣಿಗಳನ್ನು ಬಳಸಿ ಎಷ್ಟು ಬಗೆಯ ಸರಗಳನ್ನು ಸೃಷ್ಟಿಸಬಹುದು?" ಎಂಬಂಥ ಲೆಕ್ಕಗಳಿಗೆ ಉತ್ತರಿಸುವ ಪ್ರಯತ್ನ ನಡೆಯುತ್ತದೆ. ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಕ್ಷೇತ್ರದಲ್ಲಿ ಕ್ಯಾಟಲಾನ್ ಸಂಖ್ಯೆ ಎಂಬುದು ಒಂದು ವಿಶಿಷ್ಟ ಬಗೆಯ ಸಂಖ್ಯೆ.ಬೆಲ್ಜಿಯನ್ ಗಣಿತಜ್ಞ ಯೂಜೀನ್ ಚಾರ್ಲ್ಸ್ ಕ್ಯಾಟಲಾನ್ (೧೮೧೪ - ೧೮೯೪) ಎಂಬುವನ ಗೌರವಾರ್ಥ ಈ ಸಂಖ್ಯೆಗಳಿಗೆ ಹೆಸರು ಬಂದಿದೆ. ಕ್ಯಾಟಲಾನ್ ಸಂಖ್ಯೆಗಳ ಸರಣಿಯಲ್ಲಿ n ಸ್ಥಾನದಲ್ಲಿ ಬರುವ ಸಂಖ್ಯೆಯನ್ನು ಹೀಗೆ ಪರಿಭಾಷಿಸುತ್ತಾರೆ.

$C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\qquad {\mbox{ for }}n\geq 0.$

ಇಲ್ಲಿ ${x \choose y}$ ಎಂಬುದು x ವಸ್ತುಗಳಿಂದ y ವಸ್ತುಗಳನ್ನು ಎಷ್ಟು ವಿವಿಧ ಬಗೆಗಳಲ್ಲಿ ಆರಿಸಿಕೊಳ್ಳಬಹುದು ಎಂಬುದರ ಗಣತಿ. ಉದಾಹರಣೆಗೆ ನಾಲ್ಕುಬಗೆಯ ತಿಂಡಿಗಳಿಂದ ನಾವು ಎರಡನ್ನು ೬ ವಿಧಗಳಲ್ಲಿ ಆರಿಸಿಕೊಳ್ಳಬಹುದು. ಮೊದಲ ಕೆಲವು ಕ್ಯಾಟಲಾನ್ ಸಂಖ್ಯೆಗಳನ್ನು ಕೆಳಗೆ ತೋರಿಸಿದೆ. ಇಲ್ಲಿ n ಗಣತಿಯು ಸೊನ್ನೆಯಿಂದ ಪ್ರಾರಂಭ.

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ….

n ಹೆಚ್ಚಿಸುತ್ತಾ ಹೋದರೆ ಕ್ಯಾಟಲಾನ್ ಸಂಖ್ಯೆಯ ಬೆಳವಣಿಗೆಯನ್ನು ಹೀಗೆ ಅಂದಾಜು ಮಾಡಬಹುದು:

$C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$

ಉಪಯೋಗಗಳು

ಕ್ಯಾಟಲಾನ್ ಸಂಖ್ಯೆಗಳು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಅನೇಕ ಕಡೆ ಉದ್ಭವಿಸುತ್ತವೆ

ಕಂಸಗಳನ್ನು ಬಳಸಿ ಗಣಿತ ತೋರಿಕೆಗಳು

ಗಣಿತದಲ್ಲಿ ಬರೆಯುವ ತೋರಿಕೆಗಳ ಒಂದೆರಡು ಉದಾಹರಣೆ ನೋಡಿ. (x+y)*(x-y), (x+(x*y)+y), ಮೊದಲಾದವು. ಇವುಗಳಲ್ಲಿ ಕಂಸಚಿಹ್ನೆಗಳನ್ನು ಮಾತ್ರ ಉಳಿಸಿಕೊಂಡು ತೋರಿಕೆಗಳನ್ನು ಮತ್ತೆ ಬರೆದರೆ ಸಿಕ್ಕುವುದು ()(), (()). ಎರಡು ಎಡ-ಕಂಸ ಮತ್ತು ಎರಡು ಬಲ ಕಂಸ ಚಿಹ್ನೆಗಳನ್ನು ಬಳಸಿ ಬೇರೆ ಯಾವುದಾದರೂ ಬಗೆಯ ತೋರಿಕೆ ಬರೆಯಬಹುದೇ? n ಎಡ-ಕಂಸಗಳನ್ನು ಮತ್ತು n ಬಲ-ಕಂಸಗಳನ್ನು ಬಳಸಿ ಎಷ್ಟು ಬಗೆಯ ತೋರಿಕೆಗಳನ್ನು ಬರೆಯಬಹುದು? ಆ ಸಂಖ್ಯೆಯೇ n ಸರಣಿಸಂಖ್ಯೆಯ ಕ್ಯಾಟಲಾನ್ ಸಂಖ್ಯೆ (ಅಥವಾ C_n) . ಉದಾಹರಣೆಗೆ ಮೂರು ಎಡ ಮತ್ತು ಮೂರು ಬಲ ಕಂಸಚಿಹ್ನೆಗಳನ್ನು ಬಳಸಿ ಐದು ಬಗೆಯ ತೋರಿಕೆಗಳನ್ನು ಬರೆಯಬಹುದು.

$()()(),(())(),()(()),(()()),((()))$

ಹಾದಿಗಳ ಎಣಿಕೆ

ಕೆಳಗಿನ ಚಿತ್ರದಲ್ಲಿ $4\times 4$ ಚೌಕಾಬಾರದ ಮಣೆಯನ್ನು ತೋರಿಸಲಾಗಿದೆ. ಈಗೊಂದು ಆಟ ನೋಡೋಣ. ಎಲ್ಲಕ್ಕಿಂತ ಕೆಳಗಿನ ಸಾಲಿನಲ್ಲಿ ಎಲ್ಲಕ್ಕಿಂತ ಎಡದಲ್ಲಿರುವ ಮನೆಯಿಂದ ಪ್ರಾರಂಭಿಸಬೇಕು. ಎಲ್ಲಕ್ಕಿಂತ ಮೇಲಿನ ಸಾಲಿನ ಅತ್ಯಂತ ಬಲಕ್ಕಿರುವ ಮನೆಗೆ ಹೋಗಿ ಮುಟ್ಟಬೇಕು. ನೀವು ಬಲಕ್ಕೆ ಅಥವಾ ಮೇಲಕ್ಕೆ ಮಾತ್ರ ಹೋಗಬಹುದು. ಉದಾ - ಬಲ-ಬಲ-ಬಲ-ಮೇಲೆ-ಮೇಲೆ-ಮೇಲೆ ಎಂಬುದು ಒಂದು ಬಗೆ. ಇಂಥ ಎಷ್ಟು ಬಗೆಗಳಿವೆ? ಸ್ವಲ್ಪ ಯೋಚಿಸಿದರೆ "ಬಲ" ಎಂಬುದನ್ನು ಎಡ-ಕಂಸ ಚಿಹ್ನೆಗೆ ಮತ್ತು "ಮೇಲೆ" ಎಂಬುದನ್ನು ಬಲ-ಕಂಸ ಚಿಹ್ನೆಗೆ ಬದಲಾಯಿಸಬಹುದು. ಹೀಗಾಗಿ $n\times n$ ಚೌಕಾಬಾರದ ಮಣೆಯಲ್ಲಿ ಒಂದು ಮೂಲೆಯಿಂದ ಕರ್ಣದ ಇನ್ನೊಂದು ಮೂಲೆಗೆ ಹೋಗಿ ಮುಟ್ಟಲು ಇರುವ ಸಾಧ್ಯತೆಗಳು C_n ಅಥವಾ n ಸರಣಿಯ ಕ್ಯಾಟಲಾನ್ ಸಂಖ್ಯೆ!

ಇವನ್ನೂ ನೋಡಿ

ನಾರಾಯಣ ಸಂಖ್ಯೆ