Davenport–Schinzel sequence
સંયોજનશાસ્ત્રમાં, ડેવનપોર્ટ-શ્ચિન્ઝેલ ક્રમ એ પ્રતીકોનો ક્રમ છે જેમાં કોઈપણ બે પ્રતીકો આવર્તનમાં કેટલી વાર દેખાઈ શકે છે તે મર્યાદિત છે. ડેવનપોર્ટ-શ્ચિન્ઝેલ ક્રમની મહત્તમ શક્ય લંબાઈ તેના વિશિષ્ટ પ્રતીકોની સંખ્યા દ્વારા મર્યાદિત હોય છે, જે નાના પરંતુ બિન-સ્થિર પરિબળ દ્વારા ગુણાકાર કરવામાં આવે છે, જે માન્ય વિકલ્પોની સંખ્યા પર આધાર રાખે છે. ડેવનપોર્ટ-શ્ચિન્ઝેલ સિક્વન્સની વ્યાખ્યા સૌપ્રથમ 1965માં હેરોલ્ડ ડેવનપોર્ટ અને એન્ડ્રેઝ શ્ચિન્ઝેલ દ્વારા રેખીય વિભેદક સમીકરણોનું વિશ્લેષણ કરવા માટે કરવામાં આવી હતી. આ ક્રમોનું પાલન કરવું અને તેમની લંબાઈની સીમાઓ પણ સ્વતંત્ર ભૂમિતિ અને ભૌમિતિક અલ્ગોરિધમ્સના વિશ્લેષણમાં એક પ્રમાણભૂત સાધન બની ગઈ છે. વ્યાખ્યા એક મર્યાદિત ક્રમ U = u1, u2, u3, ને ક્રમ s નો ડેવનપોર્ટ-શ્ચિન્ઝેલ ક્રમ કહેવામાં આવે છે જો તે નીચેના બે ગુણધર્મોને સંતોષેઃ અનુક્રમમાં કોઈ પણ બે ક્રમિક મૂલ્યો એકબીજાના સમાન નથી. જો x અને y એ અનુક્રમમાં આવતા બે અલગ મૂલ્યો હોય, તો અનુક્રમમાં અનુગામી. x,. y,., x,., y,. નો સમાવેશ થતો નથી, જેમાં x અને y વચ્ચે વારાફરતી s + 2 મૂલ્યો હોય છે. દાખલા તરીકે, ક્રમ 1,2,1,3,1,3,2,4,5,5,2,3 એ ક્રમ 3 નો ડેવનપોર્ટ-શિન્ઝેલ ક્રમ છેઃ તેમાં લંબાઈ ચારના વૈકલ્પિક અનુગામીઓ છે, જેમ કે. 1,. 2,. 1,. 2,. (જે સમગ્ર ક્રમના અનુગામી તરીકે ચાર અલગ અલગ રીતે દેખાય છે) પરંતુ તેમાં લંબાઈ પાંચની કોઈ વૈકલ્પિક અનુગામીઓ નથી. જો ક્રમ s ના ડેવનપોર્ટ-શ્ચિન્ઝેલ ક્રમમાં n અલગ મૂલ્યો હોય, તો તેને (n, s) ડેવનપોર્ટ-શ્ચિન્ઝેલ ક્રમ અથવા DS (n, s)-ક્રમ કહેવામાં આવે છે. લંબાઈની સીમાઓ DS (n, s)-અનુક્રમની જટિલતાનું સીમામાં એસિમ્પ્ટોટિક રીતે વિશ્લેષણ કરવામાં આવ્યું છે કારણ કે n અનંત તરફ જાય છે, એવી ધારણા સાથે કે s એક નિશ્ચિત અચળાંક છે, અને લગભગ ચુસ્ત સીમાઓ તમામ s માટે જાણીતી છે. ચાલો λs (n) સૌથી લાંબી DS (n, s)-અનુક્રમની લંબાઈ સૂચવે છે. λs પર જાણીતી શ્રેષ્ઠ સીમાઓમાં વ્યસ્ત એકરમેન વિધેય α (n) = ન્યૂનતમ {m | A (m, m) ≤ n} નો સમાવેશ થાય છે, જ્યાં A એ એકરમેન વિધેય છે. એકરમેન કાર્યની ખૂબ જ ઝડપી વૃદ્ધિને કારણે, તેનો વ્યસ્ત α ખૂબ જ ધીમે ધીમે વધે છે, અને કોઈપણ વ્યવહારુ કદની સમસ્યાઓ માટે મહત્તમ ચાર હોય છે. મોટા O અને મોટા θ નોટેશનનો ઉપયોગ કરીને, નીચેની સીમાઓ જાણીતી છેઃ . . . આ જટિલતાને 2 બાય લાઇન સેગમેન્ટ્સના પરિબળમાં અનુભવી શકાય છેઃ સમતલમાં n લાઇન સેગમેન્ટ્સની વ્યવસ્થા અસ્તિત્વમાં છે, જેમના નીચલા પરબિડીયાઓમાં જટિલતા ω (nα (n)) હોય છે. . . s ≤ 6 ના સમ અને વિષમ બંને મૂલ્યો માટે, જ્યાં. જ્યારે s ચલ હોય ત્યારે λs (n) નું મૂલ્ય પણ જાણીતું હોય છે પરંતુ n એ એક નાનો અચળાંક છેઃ જ્યારે s એ n નું વિધેય હોય ત્યારે ડેવનપોર્ટ-શ્ચિન્ઝેલ સિક્વન્સ પર ઉપલા અને નીચલા સીમાઓ ચુસ્ત હોતી નથી. ક્યારે, અને. જ્યારે,. જ્યારે,. વાસ્તવિક ચલ x ના વિધેયોના સમૂહ fi (x) નું નીચું પરબિડીયું તેમના બિંદુ મુજબ લઘુત્તમ દ્વારા આપવામાં આવેલ વિધેય છેઃ f (x) = મિનિફિ (x). ધારો કે આ વિધેયો ખાસ કરીને સારી રીતે વર્તવામાં આવે છેઃ તે બધા સતત છે, અને તેમાંથી કોઈપણ બે મહત્તમ s મૂલ્યો પર સમાન છે. આ ધારણાઓ સાથે, વાસ્તવિક રેખાને મર્યાદિત રીતે ઘણા અંતરાલોમાં વિભાજિત કરી શકાય છે, જેમાં એક કાર્યના મૂલ્યો અન્ય તમામ કાર્યો કરતા નાના હોય છે. દરેક અંતરાલમાં લઘુતમ કાર્ય દ્વારા લેબલ થયેલ આ અંતરાલોનો ક્રમ, ક્રમ s નો ડેવનપોર્ટ-શ્ચિન્ઝેલ ક્રમ બનાવે છે. આમ, આ ક્રમના ડેવનપોર્ટ-શ્ચિન્ઝેલ ક્રમની જટિલતા પરની કોઈપણ ઉપલી સીમા પણ નીચલા પરબિડીયુંની આ રજૂઆતમાં અંતરાલોની સંખ્યાને મર્યાદિત કરે છે. ડેવનપોર્ટ અને શિન્ઝેલની મૂળ એપ્લિકેશનમાં, વિચારણા હેઠળના વિધેયો ક્રમ s ના સમાન સજાતીય રેખીય વિભેદક સમીકરણના વિવિધ ઉકેલોનો સમૂહ હતો. કોઈપણ બે અલગ ઉકેલોમાં મહત્તમ s મૂલ્યો સમાન હોઈ શકે છે, તેથી n અલગ ઉકેલોના સમૂહની નીચલી પરબિડીયું DS (n, s)-અનુક્રમ બનાવે છે. નીચલા પરબિડીયુંની સમાન વિભાવના એવા કાર્યો પર પણ લાગુ કરી શકાય છે જે માત્ર પીસવાઇઝ કન્ટિન્યુઅસ હોય અથવા જે ફક્ત વાસ્તવિક રેખાના અંતરાલો પર વ્યાખ્યાયિત કરવામાં આવે; જો કે, આ કિસ્સામાં, કાર્યોની વિસંગતતાના બિંદુઓ અને અંતરાલના અંતિમ બિંદુઓ કે જેમાં દરેક કાર્યને વ્યાખ્યાયિત કરવામાં આવે છે તે ક્રમના ક્રમમાં ઉમેરો કરે છે. દાખલા તરીકે, સમતલમાં બિન-ઊભી રેખા ખંડને x મૂલ્યોના અંતરાલને તેમના અનુરૂપ y મૂલ્યો સાથે મેપ કરતા કાર્યના આલેખ તરીકે અર્થઘટન કરી શકાય છે, અને રેખા વિભાગોના સંગ્રહનું નીચું પરબિડીયું ક્રમ ત્રણનો ડેવનપોર્ટ-શ્ચિન્ઝેલ ક્રમ બનાવે છે કારણ કે કોઈપણ બે રેખા વિભાગો મહત્તમ ચાર લંબાઈ સાથે વૈકલ્પિક અનુગામી રચના કરી શકે છે. સ્ક્વેરફ્રી વર્ડ નોટ્સ રેફરન્સ પણ જુઓ. . . . . . . . . . . . . . . બાહ્ય કડીઓ ડેવનપોર્ટ-શ્ચિન્ઝેલ સિક્વન્સ, મેથવર્લ્ડમાંથી. ડેવનપોર્ટ-શ્ચિન્ઝેલ સિક્વન્સિસ, સ્ટીવન એમ. લાવાલેના પુસ્તક મોશન પ્લાનિંગનો એક વિભાગ. શબ્દો પર ક્રમ અને શ્રેણી સંયોજન અલગ ભૂમિતિ