Davenport–Schinzel sequence
ಸಂಯೋಜನೆಯಲ್ಲಿ, ಡೇವನ್ಪೋರ್ಟ್-ಶ್ಚಿನ್ಜೆಲ್ ಅನುಕ್ರಮವು ಚಿಹ್ನೆಗಳ ಒಂದು ಅನುಕ್ರಮವಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಯಾವುದೇ ಎರಡು ಚಿಹ್ನೆಗಳು ಪರ್ಯಾಯವಾಗಿ ಕಾಣಿಸಿಕೊಳ್ಳುವ ಸಂಖ್ಯೆಯು ಸೀಮಿತವಾಗಿರುತ್ತದೆ. ಡೇವನ್ಪೋರ್ಟ್-ಶ್ಚಿನ್ಜೆಲ್ ಅನುಕ್ರಮದ ಗರಿಷ್ಠ ಸಂಭವನೀಯ ಉದ್ದವು ಅದರ ವಿಶಿಷ್ಟ ಚಿಹ್ನೆಗಳ ಸಂಖ್ಯೆಯಿಂದ ಸೀಮಿತವಾಗಿದೆ, ಇದನ್ನು ಅನುಮತಿಸಲಾದ ಪರ್ಯಾಯಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅವಲಂಬಿಸಿರುವ ಸಣ್ಣ ಆದರೆ ಸ್ಥಿರವಲ್ಲದ ಅಂಶದಿಂದ ಗುಣಿಸಲಾಗುತ್ತದೆ. ರೇಖೀಯ ಭೇದಾತ್ಮಕ ಸಮೀಕರಣಗಳನ್ನು ವಿಶ್ಲೇಷಿಸಲು ಡೇವನ್ಪೋರ್ಟ್-ಶಿನ್ಜೆಲ್ ಅನುಕ್ರಮಗಳನ್ನು ಮೊದಲ ಬಾರಿಗೆ 1965 ರಲ್ಲಿ ಹೆರಾಲ್ಡ್ ಡೇವನ್ಪೋರ್ಟ್ ಮತ್ತು ಆಂಡ್ರೆಜ್ ಶಿನ್ಜೆಲ್ ಅವರು ವ್ಯಾಖ್ಯಾನಿಸಿದರು. ಈ ಅನುಕ್ರಮಗಳನ್ನು ಅನುಸರಿಸುವುದು ಮತ್ತು ಅವುಗಳ ಉದ್ದದ ಮಿತಿಗಳು ಪ್ರತ್ಯೇಕ ಜ್ಯಾಮಿತಿಯಲ್ಲಿ ಮತ್ತು ಜ್ಯಾಮಿತೀಯ ಕ್ರಮಾವಳಿಗಳ ವಿಶ್ಲೇಷಣೆಯಲ್ಲಿ ಪ್ರಮಾಣಿತ ಸಾಧನವಾಗಿ ಮಾರ್ಪಟ್ಟಿವೆ. ವ್ಯಾಖ್ಯಾನ ಯು = ಯು1, ಯು2, ಯು3 ಎಂಬ ಒಂದು ಸೀಮಿತ ಅನುಕ್ರಮವು ಈ ಕೆಳಗಿನ ಎರಡು ಗುಣಲಕ್ಷಣಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸಿದರೆ ಅದನ್ನು ಕ್ರಮಗಳ ಡೇವನ್ಪೋರ್ಟ್-ಶ್ಚಿನ್ಜೆಲ್ ಅನುಕ್ರಮವೆಂದು ಹೇಳಲಾಗುತ್ತದೆಃ ಅನುಕ್ರಮದಲ್ಲಿ ಯಾವುದೇ ಎರಡು ಅನುಕ್ರಮ ಮೌಲ್ಯಗಳು ಪರಸ್ಪರ ಸಮನಾಗಿರುವುದಿಲ್ಲ. x ಮತ್ತು y ಅನುಕ್ರಮದಲ್ಲಿ ಸಂಭವಿಸುವ ಎರಡು ವಿಭಿನ್ನ ಮೌಲ್ಯಗಳಾಗಿದ್ದರೆ, ಅನುಕ್ರಮವು x ಮತ್ತು y ನಡುವೆ ಪರ್ಯಾಯವಾಗಿ s + 2 ಮೌಲ್ಯಗಳನ್ನು ಒಳಗೊಂಡಿರುವ. x, y,. y, x,. y, ಅನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ಉದಾಹರಣೆಗೆ, 1,2,1,3,1,3,2,4,5,5,2,3 ಅನುಕ್ರಮವು 3ನೇ ಕ್ರಮದ ಡೇವನ್ಪೋರ್ಟ್-ಶಿನ್ಜೆಲ್ ಅನುಕ್ರಮವಾಗಿದೆಃ ಇದು ನಾಲ್ಕು ಉದ್ದದ ಪರ್ಯಾಯ ಅನುಕ್ರಮಗಳನ್ನು ಒಳಗೊಂಡಿದೆ, ಉದಾಹರಣೆಗೆ. 1,. 2,. 1,. 2,. (ಇದು ಇಡೀ ಅನುಕ್ರಮದ ಅನುಕ್ರಮವಾಗಿ ನಾಲ್ಕು ವಿಭಿನ್ನ ರೀತಿಯಲ್ಲಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತದೆ) ಆದರೆ ಇದು ಐದು ಉದ್ದದ ಯಾವುದೇ ಪರ್ಯಾಯ ಅನುಕ್ರಮಗಳನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. 's' ಕ್ರಮದ ಡೇವನ್ಪೋರ್ಟ್-ಶ್ಚಿನ್ಜೆಲ್ ಅನುಕ್ರಮವು n ವಿಭಿನ್ನ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದನ್ನು (n, s) ಡೇವನ್ಪೋರ್ಟ್-ಶ್ಚಿನ್ಜೆಲ್ ಅನುಕ್ರಮ ಅಥವಾ DS (n, s)-ಅನುಕ್ರಮ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಉದ್ದದ ಮಿತಿಗಳು ಡಿಎಸ್ (ಎನ್, ಎಸ್)-ಅನುಕ್ರಮದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಎನ್ ಅನಂತಕ್ಕೆ ಹೋಗುವಾಗ ಮಿತಿಯಲ್ಲಿ ಲಕ್ಷಣರಹಿತವಾಗಿ ವಿಶ್ಲೇಷಿಸಲಾಗಿದೆ, ಎಸ್ ಸ್ಥಿರ ಸ್ಥಿರಾಂಕವಾಗಿದೆ ಮತ್ತು ಬಹುತೇಕ ಬಿಗಿಯಾದ ಗಡಿಗಳು ಎಲ್ಲಾ ಎಸ್ಗಳಿಗೆ ತಿಳಿದಿವೆ. λs (ಎನ್) ಉದ್ದದ ಡಿಎಸ್ (ಎನ್, ಎಸ್)-ಅನುಕ್ರಮದ ಉದ್ದವನ್ನು ಸೂಚಿಸೋಣ. λsನಲ್ಲಿ ತಿಳಿದಿರುವ ಅತ್ಯುತ್ತಮ ಮಿತಿಗಳು ವಿಲೋಮ ಅಕರ್ಮನ್ ಕಾರ್ಯ α (n) = min {m | A (m, m) ≤ n} ಅನ್ನು ಒಳಗೊಂಡಿರುತ್ತವೆ, ಅಲ್ಲಿ A ಎಂಬುದು ಅಕರ್ಮನ್ ಕಾರ್ಯವಾಗಿದೆ. ಅಕರ್ಮನ್ ಕ್ರಿಯೆಯ ಅತ್ಯಂತ ತ್ವರಿತ ಬೆಳವಣಿಗೆಯಿಂದಾಗಿ, ಅದರ ವಿಲೋಮ α ಬಹಳ ನಿಧಾನವಾಗಿ ಬೆಳೆಯುತ್ತದೆ ಮತ್ತು ಯಾವುದೇ ಪ್ರಾಯೋಗಿಕ ಗಾತ್ರದ ಸಮಸ್ಯೆಗಳಿಗೆ ಗರಿಷ್ಠ ನಾಲ್ಕು ಆಗಿರುತ್ತದೆ. ದೊಡ್ಡ O ಮತ್ತು ದೊಡ್ಡ θ ಸಂಕೇತಗಳನ್ನು ಬಳಸಿಕೊಂಡು, ಈ ಕೆಳಗಿನ ಮಿತಿಗಳನ್ನು ತಿಳಿಯಲಾಗುತ್ತದೆಃ .. .. .. ಈ ಸಂಕೀರ್ಣತೆಯನ್ನು ರೇಖೆಯ ಭಾಗಗಳಿಂದ 2 ಅಂಶದೊಳಗೆ ಅರಿತುಕೊಳ್ಳಬಹುದುಃ ಸಮತಲದಲ್ಲಿ n ರೇಖೆಯ ಭಾಗಗಳ ವ್ಯವಸ್ಥೆಗಳಿವೆ, ಅದರ ಕೆಳಗಿನ ಲಕೋಟೆಗಳು ಸಂಕೀರ್ಣತೆ ω (nα (n)) ಅನ್ನು ಹೊಂದಿರುತ್ತವೆ. .. .. s ≤ 6 ರ ಸಮ ಮತ್ತು ಬೆಸ ಮೌಲ್ಯಗಳೆರಡಕ್ಕೂ, ಎಲ್ಲಿ. s ಬದಲಾಗುತ್ತಿರುವಾಗ λs (n) ನ ಮೌಲ್ಯವನ್ನು ಸಹ ಕರೆಯಲಾಗುತ್ತದೆ ಆದರೆ n ಒಂದು ಸಣ್ಣ ಸ್ಥಿರಾಂಕವಾಗಿದೆಃ s ಎಂಬುದು n ನ ಕಾರ್ಯವಾಗಿದ್ದಾಗ ಡೇವನ್ಪೋರ್ಟ್-ಶ್ಚಿನ್ಜೆಲ್ ಅನುಕ್ರಮಗಳಲ್ಲಿನ ಮೇಲಿನ ಮತ್ತು ಕೆಳಗಿನ ಗಡಿಗಳು ಬಿಗಿಯಾಗಿರುವುದಿಲ್ಲ. ಯಾವಾಗ, ಮತ್ತು. ಯಾವಾಗ,. ಯಾವಾಗ,. ಕೆಳಗಿನ ಲಕೋಟೆಯ ಅನ್ವಯವು ವಾಸ್ತವಿಕ ಚಲಪರಿಮಾಣ x ನ ಕಾರ್ಯಗಳ ಗುಂಪಿನ ಕೆಳಗಿನ ಲಕೋಟೆಯು ಅವುಗಳ ಬಿಂದುವಾರು ಕನಿಷ್ಠದಿಂದ ನೀಡಲಾದ ಕಾರ್ಯವಾಗಿದೆಃ f (x) = ಮಿನಿಫೈ (x). ಈ ಕಾರ್ಯಗಳು ವಿಶೇಷವಾಗಿ ಉತ್ತಮವಾಗಿ ವರ್ತಿಸುತ್ತವೆ ಎಂದು ಭಾವಿಸೋಣಃ ಅವೆಲ್ಲವೂ ನಿರಂತರವಾಗಿವೆ, ಮತ್ತು ಅವುಗಳಲ್ಲಿ ಯಾವುದೇ ಎರಡು ಹೆಚ್ಚಿನ s ಮೌಲ್ಯಗಳಲ್ಲಿ ಸಮಾನವಾಗಿರುತ್ತವೆ. ಈ ಊಹೆಗಳೊಂದಿಗೆ, ನೈಜ ರೇಖೆಯನ್ನು ಸೀಮಿತವಾಗಿ ಅನೇಕ ಮಧ್ಯಂತರಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು, ಅದರೊಳಗೆ ಒಂದು ಕಾರ್ಯವು ಇತರ ಎಲ್ಲಾ ಕಾರ್ಯಗಳಿಗಿಂತ ಸಣ್ಣ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ಮಧ್ಯಂತರಗಳ ಅನುಕ್ರಮವು, ಪ್ರತಿ ಮಧ್ಯಂತರದೊಳಗೆ ಕನಿಷ್ಠಗೊಳಿಸುವ ಕಾರ್ಯದಿಂದ ಲೇಬಲ್ ಮಾಡಲಾಗಿದ್ದು, s ಕ್ರಮದ ಡೇವನ್ಪೋರ್ಟ್-ಶಿನ್ಜೆಲ್ ಅನುಕ್ರಮವನ್ನು ರೂಪಿಸುತ್ತದೆ. ಹೀಗಾಗಿ, ಈ ಕ್ರಮದ ಡೇವನ್ಪೋರ್ಟ್-ಶಿನ್ಜೆಲ್ ಅನುಕ್ರಮದ ಸಂಕೀರ್ಣತೆಯ ಮೇಲಿನ ಯಾವುದೇ ಮೇಲಿನ ಮಿತಿಯು ಕೆಳಗಿನ ಲಕೋಟೆಯ ಈ ಪ್ರಾತಿನಿಧ್ಯದಲ್ಲಿನ ಮಧ್ಯಂತರಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸಹ ಬಂಧಿಸುತ್ತದೆ. ಡೇವನ್ಪೋರ್ಟ್ ಮತ್ತು ಶಿನ್ಜೆಲ್ನ ಮೂಲ ಅನ್ವಯದಲ್ಲಿ, ಪರಿಗಣನೆಯಲ್ಲಿರುವ ಕಾರ್ಯಗಳು s ಕ್ರಮದ ಒಂದೇ ಏಕರೂಪದ ರೇಖೀಯ ಭೇದಾತ್ಮಕ ಸಮೀಕರಣಕ್ಕೆ ವಿಭಿನ್ನ ಪರಿಹಾರಗಳ ಒಂದು ಗುಂಪಾಗಿತ್ತು. ಯಾವುದೇ ಎರಡು ವಿಭಿನ್ನ ಪರಿಹಾರಗಳು ಹೆಚ್ಚಿನ s ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರಬಹುದು, ಆದ್ದರಿಂದ n ವಿಭಿನ್ನ ಪರಿಹಾರಗಳ ಗುಂಪಿನ ಕೆಳಗಿನ ಹೊದಿಕೆಯು DS (n, s)-ಅನುಕ್ರಮವನ್ನು ರೂಪಿಸುತ್ತದೆ. ಕೆಳಗಿನ ಲಕೋಟೆಯ ಅದೇ ಪರಿಕಲ್ಪನೆಯನ್ನು ತುಂಡುಗಳಾಗಿ ಮಾತ್ರ ನಿರಂತರವಾಗಿರುವ ಅಥವಾ ನೈಜ ರೇಖೆಯ ಮಧ್ಯಂತರಗಳಲ್ಲಿ ಮಾತ್ರ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಕಾರ್ಯಗಳಿಗೆ ಅನ್ವಯಿಸಬಹುದು; ಆದಾಗ್ಯೂ, ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಕಾರ್ಯಗಳ ಸ್ಥಗಿತದ ಬಿಂದುಗಳು ಮತ್ತು ಪ್ರತಿ ಕಾರ್ಯವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಮಧ್ಯಂತರದ ಅಂತಿಮ ಬಿಂದುಗಳು ಅನುಕ್ರಮದ ಕ್ರಮಕ್ಕೆ ಸೇರುತ್ತವೆ. ಉದಾಹರಣೆಗೆ, ಸಮತಲದಲ್ಲಿನ ಲಂಬವಲ್ಲದ ರೇಖೆ ವಿಭಾಗವನ್ನು ಅವುಗಳ ಅನುಗುಣವಾದ y ಮೌಲ್ಯಗಳಿಗೆ x ಮೌಲ್ಯಗಳ ಮಧ್ಯಂತರವನ್ನು ಮ್ಯಾಪ್ ಮಾಡುವ ಕಾರ್ಯದ ಗ್ರಾಫ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು ಮತ್ತು ರೇಖೆ ವಿಭಾಗಗಳ ಸಂಗ್ರಹದ ಕೆಳಗಿನ ಲಕೋಟೆಯು ಡೇವನ್ಪೋರ್ಟ್-ಶಿನ್ಜೆಲ್ ಅನುಕ್ರಮವನ್ನು ರಚಿಸುತ್ತದೆ ಏಕೆಂದರೆ ಯಾವುದೇ ಎರಡು ರೇಖೆ ವಿಭಾಗಗಳು ಗರಿಷ್ಠ ನಾಲ್ಕು ಉದ್ದದೊಂದಿಗೆ ಪರ್ಯಾಯ ಅನುಕ್ರಮವನ್ನು ರಚಿಸಬಹುದು. ಸ್ಕ್ವೇರ್ಫ್ರೀ ಪದ ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳನ್ನೂ ಸಹ ನೋಡಿ. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ಮ್ಯಾಥ್ ವರ್ಲ್ಡ್ನಿಂದ ಹೊರಗಿನ ಕೊಂಡಿಗಳು ಡೇವನ್ಪೋರ್ಟ್-ಶ್ಚಿನ್ಜೆಲ್ ಸೀಕ್ವೆನ್ಸ್. ಸ್ಟೀವನ್ ಎಮ್. ಲಾವಲ್ಲೆ ಬರೆದ ಮೋಷನ್ ಪ್ಲಾನಿಂಗ್ ಪುಸ್ತಕದ ಒಂದು ವಿಭಾಗವಾದ ಡೇವನ್ಪೋರ್ಟ್-ಶ್ಚಿನ್ಜೆಲ್ ಸೀಕ್ವೆನ್ಸಸ್. ಪದಗಳ ಮೇಲಿನ ಅನುಕ್ರಮಗಳು ಮತ್ತು ಸರಣಿ ಸಂಯೋಜನೆಗಳು ಪ್ರತ್ಯೇಕ ರೇಖಾಗಣಿತ