Labelled enumeration theorem
ಸಂಯೋಜಿತ ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಲೇಬಲ್ ಮಾಡಲಾದ ಎಣಿಕೆ ಪ್ರಮೇಯವು ಲೇಬಲ್ ಮಾಡಲಾದ ಪ್ರಕರಣಕ್ಕಾಗಿ ಪೊಲ್ಯಾ ಎಣಿಕೆ ಪ್ರಮೇಯದ ಪ್ರತಿರೂಪವಾಗಿದೆ, ಅಲ್ಲಿ ನಾವು ಘಾತೀಯ ಉತ್ಪಾದಕ ಕಾರ್ಯ (ಇಜಿಎಫ್) ಜಿ (ಝಡ್) ನಿಂದ ನೀಡಲಾದ ಲೇಬಲ್ ಮಾಡಲಾದ ವಸ್ತುಗಳ ಗುಂಪನ್ನು ಹೊಂದಿದ್ದೇವೆ, ಇವುಗಳನ್ನು ಎನ್ ಸ್ಲಾಟ್ಗಳಾಗಿ ವಿತರಿಸಲಾಗುತ್ತಿದೆ ಮತ್ತು ಕ್ರಮಪಲ್ಲಟನೆ ಗುಂಪು ಜಿ ಇದು ಸ್ಲಾಟ್ಗಳನ್ನು ಕ್ರಮಬದ್ಧಗೊಳಿಸುತ್ತದೆ, ಹೀಗಾಗಿ ಸಂರಚನೆಗಳ ಸಮಾನ ವರ್ಗಗಳನ್ನು ರಚಿಸುತ್ತದೆ. ಸ್ಲಾಟ್ಗಳಲ್ಲಿನ ವಸ್ತುಗಳನ್ನು ಮರು-ಲೇಬಲ್ ಮಾಡುವ ವಿಶೇಷ ಮರು-ಲೇಬಲ್ ಮಾಡುವ ಕಾರ್ಯಾಚರಣೆಯಿದೆ, 1 ರಿಂದ k ಗೆ ಲೇಬಲ್ಗಳನ್ನು ನಿಯೋಜಿಸುತ್ತದೆ, ಅಲ್ಲಿ k ಎಂಬುದು ಒಟ್ಟು ನೋಡ್ಗಳ ಸಂಖ್ಯೆ, ಅಂದರೆ. ಪ್ರತ್ಯೇಕ ವಸ್ತುಗಳ ನೋಡ್ಗಳ ಸಂಖ್ಯೆಯ ಮೊತ್ತ. ಈ ಮರು-ಲೇಬಲ್ ಪ್ರಕ್ರಿಯೆಯ ಅಡಿಯಲ್ಲಿ ವಿವಿಧ ಸಂರಚನೆಗಳ ಸಂಖ್ಯೆಯ ಇಜಿಎಫ್ ಅನ್ನು ನಿರ್ದಿಷ್ಟವಾಗಿ, ಜಿ n ಕ್ರಮದ ಸಮ್ಮಿತೀಯ ಗುಂಪಾಗಿದ್ದರೆ (ಆದ್ದರಿಂದ, |G | = ಎನ್! ), ಕಾರ್ಯಗಳನ್ನು ಮತ್ತಷ್ಟು ಒಂದೇ ಉತ್ಪಾದಿಸುವ ಕಾರ್ಯವಾಗಿ ಸಂಯೋಜಿಸಬಹುದುಃ ಇದು ಘಾತೀಯ ಡಬ್ಲ್ಯೂ. ಆರ್. ಟಿ. ವೇರಿಯೇಬಲ್ Z ಮತ್ತು ಸಾಮಾನ್ಯ ಡಬ್ಲ್ಯೂಆರ್ಟಿ. ಚಲಪರಿಮಾಣ t. ಮರು-ಲೇಬಲ್ ಮಾಡುವ ಪ್ರಕ್ರಿಯೆಯು 1 ರಿಂದ m ವರೆಗಿನ ಲೇಬಲ್ಗಳನ್ನು ಹೊಂದಿರುವ ಲೇಬಲ್ ಮಾಡಲಾದ ಆಂತರಿಕ ನೋಡ್ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಗಾತ್ರದ ವಸ್ತುವು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ನಾವು ಭಾವಿಸುತ್ತೇವೆ. ಲೇಬಲ್ ಮಾಡದ ಕೇಸ್ಗೆ ಹೋಲಿಸಿದರೆ ಸ್ಲಾಟ್ಗಳ ಮೇಲೆ G ಯ ಕ್ರಿಯೆಯು ಬಹಳ ಸರಳವಾಗಿದೆ, ಏಕೆಂದರೆ ಲೇಬಲ್ಗಳು ಸ್ಲಾಟ್ಗಳಲ್ಲಿನ ವಸ್ತುಗಳನ್ನು ಪ್ರತ್ಯೇಕಿಸುತ್ತವೆ ಮತ್ತು G ಯ ಕೆಳಗಿರುವ ಕಕ್ಷೆಗಳು ಒಂದೇ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುತ್ತವೆ. (ಇಜಿಎಫ್ ಜಿ (ಝಡ್) ಶೂನ್ಯ ಗಾತ್ರದ ವಸ್ತುಗಳನ್ನು ಒಳಗೊಂಡಿಲ್ಲದಿರಬಹುದು. ಏಕೆಂದರೆ ಅವುಗಳನ್ನು ಲೇಬಲ್ಗಳಿಂದ ಪ್ರತ್ಯೇಕಿಸಲಾಗಿಲ್ಲ ಮತ್ತು ಆದ್ದರಿಂದ ಅಂತಹ ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ವಸ್ತುಗಳ ಉಪಸ್ಥಿತಿಯು ಅದಕ್ಕಿಂತ ಕಡಿಮೆ ಗಾತ್ರದ ಕಕ್ಷೆಗಳನ್ನು ಸೃಷ್ಟಿಸುತ್ತದೆ). ಹೇಳಿದಂತೆ, ವಸ್ತುಗಳ ನೋಡ್ಗಳನ್ನು ಸ್ಲಾಟ್ಗಳಲ್ಲಿ ವಿತರಿಸಿದಾಗ ಅವುಗಳನ್ನು ಮರು-ಲೇಬಲ್ ಮಾಡಲಾಗುತ್ತದೆ. ಗಾತ್ರದ ವಸ್ತುವು ಮೊದಲ ಸ್ಲಾಟ್ಗೆ ಹೋಗುತ್ತದೆ, ಗಾತ್ರದ ವಸ್ತುವು ಎರಡನೇ ಸ್ಲಾಟ್ಗೆ ಹೋಗುತ್ತದೆ, ಮತ್ತು ಹೀಗೆ, ಮತ್ತು ಸಂರಚನೆಯ ಒಟ್ಟು ಗಾತ್ರವು ಕೆ ಆಗಿದೆ, ಆದ್ದರಿಂದ ಮರು-ಲೇಬಲ್ ಮಾಡುವ ಪ್ರಕ್ರಿಯೆಯು ಈ ಕೆಳಗಿನಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಃ ಕೆ ಲೇಬಲ್ಗಳ ಗುಂಪಿನ ವಿಭಾಗಗಳಲ್ಲಿ ಒಂದನ್ನು ಗಾತ್ರದ ಉಪಗುಂಪುಗಳಾಗಿ ಆಯ್ಕೆ ಮಾಡಿ ಈಗ ಪ್ರತಿ ವಸ್ತುವಿನ ಆಂತರಿಕ ನೋಡ್ಗಳನ್ನು ಆಯಾ ಉಪಗುಂಪಿನಿಂದ ಲೇಬಲ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಮರು-ಲೇಬಲ್ ಮಾಡಿ, ಲೇಬಲ್ಗಳ ಕ್ರಮವನ್ನು ಕಾಪಾಡಿಕೊಳ್ಳಿ. ಇ. ಜಿ. ಮೊದಲ ವಸ್ತುವು 1 ರಿಂದ 4 ರವರೆಗೆ ಲೇಬಲ್ ಮಾಡಲಾದ ನಾಲ್ಕು ನೋಡ್ಗಳನ್ನು ಹೊಂದಿದ್ದರೆ ಮತ್ತು ಈ ವಸ್ತುವಿಗಾಗಿ ಆಯ್ಕೆ ಮಾಡಲಾದ ಲೇಬಲ್ಗಳ ಸೆಟ್ {2,5,6,10} ಆಗಿದ್ದರೆ, ನೋಡ್ 1 ಲೇಬಲ್ 2, ನೋಡ್ 2, ಲೇಬಲ್ 5, ನೋಡ್ 3, ಲೇಬಲ್ 6 ಮತ್ತು ನೋಡ್ 4, ಲೇಬಲ್ 10 ಅನ್ನು ಸ್ವೀಕರಿಸುತ್ತದೆ. ಈ ರೀತಿಯಾಗಿ ವಸ್ತುಗಳ ಮೇಲಿನ ಲೇಬಲ್ಗಳು ವಸ್ತುವಿಗಾಗಿ ಆಯ್ಕೆ ಮಾಡಿದ ಉಪಗುಂಪಿನಿಂದ ಲೇಬಲ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ವಿಶಿಷ್ಟ ಲೇಬಲಿಂಗ್ ಅನ್ನು ಪ್ರೇರೇಪಿಸುತ್ತವೆ. ಪ್ರಮೇಯದ ಪುರಾವೆ ಇದು ಒಟ್ಟು ಗಾತ್ರದ k ಅಥವಾ ವಿಭಿನ್ನ ಸಂರಚನೆಗಳಿವೆ ಎಂದು ಮರು-ಲೇಬಲ್ ರಚನೆಯಿಂದ ಅನುಸರಿಸುತ್ತದೆ. ಸೂತ್ರವು ಒಂದು ಪೂರ್ಣಾಂಕಕ್ಕೆ ಮೌಲ್ಯಮಾಪನ ಮಾಡುತ್ತದೆ ಏಕೆಂದರೆ k <n ಗೆ ಶೂನ್ಯವಾಗಿದೆ (g ಗಾತ್ರದ ಶೂನ್ಯ ವಸ್ತುಗಳನ್ನು ಒಳಗೊಂಡಿಲ್ಲ ಎಂದು ನೆನಪಿಡಿ) ಮತ್ತು ನಾವು ಹೊಂದಿರುವಾಗ ಮತ್ತು G ಯ ಕ್ರಮವು ಅದರ ಕ್ರಮವನ್ನು ವಿಭಜಿಸುತ್ತದೆ, ಅಂದರೆ, ಲ್ಯಾಗ್ರೇಂಜ್ನ ಪ್ರಮೇಯದಿಂದ. ಲೇಬಲ್ ಮಾಡಲಾದ ಸಂರಚನೆಗಳ ಇ. ಜಿ. ಎಫ್ ಅನ್ನು ಅನುಕ್ರಮಗಳನ್ನು ಎಣಿಸುವ ಮೂಲಕವೂ ಪಡೆಯಬಹುದು, ಅಂದರೆ. ಸ್ಲಾಟ್ಗಳನ್ನು ಕ್ರಮಪಲ್ಲಟಗೊಳಿಸದಿದ್ದಾಗ, ಮತ್ತು-ಫ್ಯಾಕ್ಟರ್ ಇಲ್ಲದೆ ಮೇಲಿನ ವಾದವನ್ನು ಬಳಸುವ ಮೂಲಕ ಮರು-ಲೇಬಲಿಂಗ್ನ ಅಡಿಯಲ್ಲಿ ಅವುಗಳ ಉತ್ಪಾದನಾ ಕಾರ್ಯವನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಅಂತಿಮವಾಗಿ, ಪ್ರತಿಯೊಂದು ಅನುಕ್ರಮವು ಗಾತ್ರದ ಕಕ್ಷೆಗೆ ಸೇರಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಆದ್ದರಿಂದ ಕಕ್ಷೆಗಳ ಉತ್ಪಾದನಾ ಕಾರ್ಯವನ್ನು ಫ್ರಾಂಕೋಯಿಸ್ ಬರ್ಗೆರಾನ್, ಗಿಲ್ಬರ್ಟ್ ಲೇಬೆಲ್ಲೆ, ಪಿಯರೆ ಲೆರೋಕ್ಸ್, ಥಿಯೋರಿ ಡೆಸ್ ಎಸ್ಪೀಸಸ್ ಎಟ್ ಕಾಂಬಿನಾಟೋಯಿರ್ ಡೆಸ್ ಸ್ಟ್ರಕ್ಚರ್ಸ್ ಆರ್ಬೊರೆಸೆಂಟ್ಸ್, ಲಾಸಿಮ್, ಮಾಂಟ್ರಿಯಲ್ (1994) ಉಲ್ಲೇಖಗಳು ನೀಡಿವೆ. ಇಂಗ್ಲಿಷ್ ಆವೃತ್ತಿಃ ಕಾಂಬಿನೇಟೋರಿಯಲ್ ಸ್ಪೀಸೀಸ್ ಅಂಡ್ ಟ್ರೀ-ಲೈಕ್ ಸ್ಟ್ರಕ್ಚರ್ಸ್, ಕೇಂಬ್ರಿಡ್ಜ್ ಯೂನಿವರ್ಸಿಟಿ ಪ್ರೆಸ್ (1998). ಎನ್ಯೂಮರೇಟಿವ್ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ನಲ್ಲಿನ ಪ್ರಮೇಯಗಳು ಪುರಾವೆಗಳನ್ನು ಹೊಂದಿರುವ ಲೇಖನಗಳು