ይህ ጽሁፍ የሚያተኩረው ልዩ የሂሳብ ክፍል (combinatorics) በሚባለው የሒሳብ ክፍል ላይ ነው። ቀመሮች፣ ደንቦች፣ የችግር አፈታት ምሳሌዎች - ይህን ሁሉ ጽሑፉን እስከ መጨረሻው በማንበብ እዚህ ማግኘት ይችላሉ።
ታዲያ፣ ይህ ክፍል ምንድን ነው? Combinatorics ማንኛውንም ዕቃ የመቁጠር ጉዳይን ይመለከታል። ነገር ግን በዚህ ሁኔታ እቃዎቹ ፕለም, ፒር ወይም ፖም አይደሉም, ግን ሌላ ነገር ነው. Combinatorics የክስተት እድልን እንድናገኝ ይረዳናል። ለምሳሌ ካርዶችን ሲጫወቱ ተቃዋሚው ትራምፕ ካርድ ያለው ዕድል ምን ያህል ነው? ወይም እንደዚህ ያለ ምሳሌ - ከሃያ ኳሶች ቦርሳ በትክክል ነጭ የማግኘት እድሉ ምን ያህል ነው? ቢያንስ የዚህን የሂሳብ ክፍል መሰረታዊ ነገሮች ማወቅ ያለብን ለእንደዚህ አይነት ስራዎች ነው።
የጥምር ውቅረቶች
የመሠረታዊ ፅንሰ-ሀሳቦችን እና የማጣመር ቀመሮችን ጉዳይ ከግምት ውስጥ በማስገባት ለተጣመሩ አወቃቀሮች ትኩረት መስጠት አንችልም። እነሱ ጥቅም ላይ የሚውሉት ለማቀነባበር ብቻ ሳይሆን የተለያዩ ጥምር ችግሮችን ለመፍታት ጭምር ነው. የዚህ አይነት ሞዴሎች ምሳሌዎች፡ ናቸው።
- አቀማመጥ፤
- permutation፤
- ጥምር፤
- የቁጥር ቅንብር፤
- የተከፈለ ቁጥር።
ስለመጀመሪያዎቹ ሦስቱ በኋላ በበለጠ ዝርዝር እንነጋገራለን ነገርግን በዚህ ክፍል ውስጥ ለቅንብር እና ክፍፍል ትኩረት እንሰጣለን ። ስለ አንድ የተወሰነ ቁጥር ስብጥር (ስይ፣ ሀ) ሲናገሩ የቁጥር ሀ ውክልና እንደ የታዘዘ የአንዳንድ አዎንታዊ ቁጥሮች ድምር ማለት ነው። እና ክፋይ ያልታዘዘ ድምር ነው።
ክፍል
በቀጥታ ወደ ጥምር ቀመሮች እና ችግሮችን ግምት ውስጥ ከማስገባታችን በፊት እንደሌሎች የሒሳብ ክፍሎች ኮምቢነቶሪክስ የራሱ ንዑስ ክፍሎች እንዳሉት ልብ ማለት ያስፈልጋል። እነዚህ የሚከተሉትን ያካትታሉ፡
- ቁጥር፤
- መዋቅራዊ፤
- እጅግ;
- የራምሴ ቲዎሪ፤
- ይሆናል፤
- ቶፖሎጂካል፤
- የማይወሰን።
በመጀመሪያው ጉዳይ፣ ስለ ቁጠራ ማጣመር ነው እየተነጋገርን ያለነው፣ ችግሮቹ በስብስብ አካላት የተፈጠሩ የተለያዩ ውቅሮችን መቁጠርን ወይም መቁጠርን ያስባሉ። እንደ አንድ ደንብ, በእነዚህ ስብስቦች ላይ አንዳንድ እገዳዎች ተጭነዋል (ልዩነት, ልዩነት, የመድገም እድል, ወዘተ). እና የእነዚህ አወቃቀሮች ቁጥር የመደመር ወይም የማባዛት ህግን በመጠቀም ይሰላል, ትንሽ ቆይቶ እንነጋገራለን. መዋቅራዊ ጥምር የግራፍ እና የማትሮይድ ንድፈ ሃሳቦችን ያጠቃልላል። የ "Extremal combinatorics" ችግር ምሳሌ የሚከተሉትን ባህሪያት የሚያረካ የግራፍ ትልቁ ልኬት ነው … በአራተኛው አንቀጽ ላይ የራምሴይ ቲዎሪ ጠቅሰናል, ይህም በዘፈቀደ ውቅሮች ውስጥ መደበኛ መዋቅሮች መኖራቸውን ያጠናል. ሊሆን የሚችልcombinatorics ጥያቄውን መመለስ ይችላል - አንድ የተሰጠ ስብስብ የተወሰነ ንብረት ያለው ዕድል ምን ያህል ነው. እርስዎ እንደሚገምቱት፣ ቶፖሎጂካል ጥምር ዘዴዎች በቶፖሎጂ ውስጥ ይተገበራሉ። እና በመጨረሻም ሰባተኛው ነጥብ - ኢንፊኒታሪ combinatorics የማጣመር ዘዴዎችን ወደ ወሰን የሌላቸው ስብስቦች አተገባበር ያጠናል.
የመደመር ደንብ
ከማዋሃድ ቀመሮች መካከል፣ አንድ ሰው በጣም ቀላል የሆኑትን ማግኘት ይችላል፣ ይህም ለረጅም ጊዜ የምናውቃቸው ናቸው። ምሳሌ ድምር ደንብ ነው. ሁለት ድርጊቶች (C እና E) ተሰጥተውናል እንበል፣ እርስ በርሳቸው የሚጋጩ ከሆኑ፣ ድርጊት C በበርካታ መንገዶች (ለምሳሌ፣ ሀ)፣ እና E ርምጃ በ b-መንገድ ሊደረግ ይችላል፣ ከዚያም ማንኛቸውም (ሐ) ወይም E) በ + b መንገዶች ሊከናወን ይችላል.
በንድፈ ሀሳብ፣ ይህ ለመረዳት በጣም ከባድ ነው፣ አጠቃላይ ነጥቡን በቀላል ምሳሌ ለማስተላለፍ እንሞክራለን። በአንድ ክፍል ውስጥ ያሉትን አማካይ የተማሪዎች ቁጥር እንውሰድ - ሃያ አምስት ነው እንበል። ከእነዚህም መካከል አሥራ አምስት ሴት ልጆች እና አሥር ወንዶች ልጆች ይገኙበታል። አንድ ረዳት በየቀኑ ለክፍሉ ይመደባል። ዛሬ የክፍል ረዳትን ለመመደብ ስንት መንገዶች አሉ? ለችግሩ መፍትሄው በጣም ቀላል ነው, ወደ መደመር ደንብ እንጠቀማለን. የሥራው ጽሑፍ ወንዶች ወይም ልጃገረዶች ብቻ ተረኛ ሊሆኑ እንደሚችሉ አይናገርም. ስለዚህ, ከአስራ አምስቱ ሴት ልጆች ወይም ከአስሩ ወንዶች መካከል የትኛውም ሊሆን ይችላል. ድምር ደንቡን በመተግበር የአንደኛ ደረጃ ተማሪ በቀላሉ ሊቋቋመው የሚችል ቀላል ምሳሌ እናገኛለን፡ 15 + 10. ካሰላን በኋላ መልሱን እናገኛለን፡ ሀያ አምስት። ማለትም ሃያ አምስት መንገዶች ብቻ አሉ።ለዛሬ የግዴታ ክፍል መድቡ።
ማባዛት ህግ
የማባዛት ህግም የመሠረታዊ የማጣመሪያ ቀመሮች ነው። በቲዎሪ እንጀምር። በርካታ ድርጊቶችን ማከናወን አለብን እንበል (ሀ): የመጀመሪያው እርምጃ የሚከናወነው በ 1 መንገድ ነው, ሁለተኛው - በ 2 መንገዶች, ሦስተኛው - በ 3 መንገዶች, እና የመጨረሻው a-ድርጊት በ sa መንገዶች እስኪፈጸም ድረስ. ከዚያም እነዚህ ሁሉ ድርጊቶች (እኛ በጠቅላላ ያሉን) በ N መንገዶች ሊከናወኑ ይችላሉ. ያልታወቀ N እንዴት ማስላት ይቻላል? ቀመሩ በዚህ ላይ ይረዳናል፡ N \u003d c1c2c3…ca.
እንደገና፣ በንድፈ ሀሳብ ምንም ግልጽ ነገር የለም፣ ወደ ቀላል የማባዛት ህግን መተግበር እንሂድ። አሥራ አምስት ሴት ልጆች እና አሥር ወንዶች ልጆች የሚማሩበትን ሃያ አምስት ሰዎች አንድ ዓይነት ክፍል እንውሰድ። በዚህ ጊዜ ብቻ ሁለት አገልጋዮችን መምረጥ ያስፈልገናል. እነሱም ወንዶች ወይም ሴቶች ብቻ ወይም ሴት ልጅ ያለው ወንድ ብቻ ሊሆኑ ይችላሉ. ወደ ችግሩ የመጀመሪያ ደረጃ መፍትሄ እንሸጋገራለን. የመጀመሪያውን ረዳት እንመርጣለን, በመጨረሻው አንቀጽ ላይ እንደወሰንነው, ሃያ አምስት ሊሆኑ የሚችሉ አማራጮችን እናገኛለን. በሥራ ላይ ያለው ሁለተኛው ሰው ከቀሩት ሰዎች ውስጥ የትኛውም ሊሆን ይችላል. እኛ ሃያ አምስት ተማሪዎች ነበሩን, አንዱን መርጠናል, ይህም ማለት ከቀሩት ሃያ አራት ሰዎች ውስጥ የትኛውም ተረኛ ሁለተኛ ሊሆን ይችላል. በመጨረሻም የማባዛት ህግን እንተገብራለን እና ሁለቱ አገልጋዮች በስድስት መቶ መንገዶች ሊመረጡ እንደሚችሉ አግኝተናል። ይህንን ቁጥር ያገኘነው ሀያ አምስት እና ሀያ አራት በማባዛት ነው።
Swap
አሁን አንድ ተጨማሪ የማጣመር ቀመር እንመለከታለን። በዚህ የጽሁፉ ክፍል እኛስለ ሽምግልና እንነጋገር። ችግሩን ወዲያውኑ በምሳሌ አስቡበት። የቢሊርድ ኳሶችን እንውሰድ፣ n-th ቁጥራቸው አለን። እኛ ማስላት አለብን፡ እነሱን በአንድ ረድፍ ለማዘጋጀት ስንት አማራጮች እንዳሉ ማለትም የታዘዘ ስብስብ ለመስራት።
እንጀምር፣ ኳሶች ከሌሉ እኛ ደግሞ ዜሮ የምደባ አማራጮች አለን። እና አንድ ኳስ ካለን, ዝግጅቱ እንዲሁ ተመሳሳይ ነው (በሂሳብ, ይህ እንደሚከተለው ሊጻፍ ይችላል: Р1=1). ሁለት ኳሶች በሁለት የተለያዩ መንገዶች ሊደረደሩ ይችላሉ: 1, 2 እና 2, 1. ስለዚህ, Р2=2. ሶስት ኳሶች በስድስት መንገዶች ሊደረደሩ ይችላሉ (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. እና እንደዚህ አይነት ሶስት ኳሶች ከሌሉ, ግን አስር ወይም አስራ አምስት? ሁሉንም ሊሆኑ የሚችሉ አማራጮችን ለመዘርዘር በጣም ረጅም ነው, ከዚያም ኮምፓኒተሮች ወደ እኛ እርዳታ ይመጣሉ. የፔርሙቴሽን ቀመር ለጥያቄያችን መልስ ለማግኘት ይረዳናል. Pn=nP(n-1)። ቀመሩን ለማቃለል ከሞከርን: Pn=n(n - 1) … 21. እና ይህ የመጀመሪያዎቹ የተፈጥሮ ቁጥሮች ውጤት ነው. እንደዚህ ያለ ቁጥር ፋብሪያል ተብሎ ይጠራል፣ እና እንደ n! ይገለጻል።
ችግሩን እናስብበት። መሪው በየማለዳው ክፍተቱን በመስመር (ሃያ ሰዎች) ይገነባል። በቡድኑ ውስጥ ሶስት ምርጥ ጓደኞች አሉ - Kostya, Sasha እና Lesha. እርስ በእርሳቸው አጠገብ የመሆን እድሉ ምን ያህል ነው? ለጥያቄው መልስ ለማግኘት "ጥሩ" ውጤትን በጠቅላላው የውጤቶች ብዛት መከፋፈል ያስፈልግዎታል. የፔርሙቴሽን ጠቅላላ ቁጥር 20 ነው!=2.5 ኩንታል. "ጥሩ" ውጤቶችን እንዴት መቁጠር ይቻላል? Kostya, Sasha እና Lesha አንድ ሱፐርማን ናቸው እንበል. ከዚያም እኛአሥራ ስምንት ጉዳዮች ብቻ አሉን። በዚህ ጉዳይ ላይ የመተላለፊያዎች ብዛት 18=6.5 ኳድሪልዮን ነው. ከዚህ ሁሉ ጋር ፣ Kostya ፣ Sasha እና Lesha በዘፈቀደ የማይከፋፈሉ ሶስት እጥፍ በመካከላቸው መንቀሳቀስ ይችላሉ ፣ እና ይህ 3 ተጨማሪ ነው!=6 አማራጮች። ስለዚህ በአጠቃላይ 18 "ጥሩ" ህብረ ከዋክብት አሉን!3! የተፈለገውን ዕድል ብቻ ማግኘት አለብን: (18!3!) / 20! ይህም በግምት 0.016 ነው። ወደ መቶኛ ከተቀየረ 1.6% ብቻ ይሆናል።
መኖርያ
አሁን ሌላ በጣም አስፈላጊ እና አስፈላጊ የማጣመር ቀመር እንመለከታለን። ማረፊያ የሚቀጥለው እትማችን ነው፣ በዚህ የአንቀጹ ክፍል እንድትመለከቱት እንመክራለን። የበለጠ ውስብስብ እንሆናለን። ከጠቅላላው ስብስብ (n) ብቻ ሳይሆን ከትንሽ (ሜ) ሊሆኑ የሚችሉ ለውጦችን ማገናዘብ እንደምንፈልግ እናስብ። ማለትም፣ የ n ንጥሎችን በ m. እንመለከታለን።
የማጣመር መሰረታዊ ቀመሮች መታወስ ብቻ ሳይሆን መረዳት አለባቸው። ምንም እንኳን እነሱ የበለጠ የተወሳሰበ ቢሆኑም ፣ አንድ ግቤት ስለሌለን ፣ ግን ሁለት። እንበል m \u003d 1 ፣ ከዚያ A \u003d 1 ፣ m \u003d 2 ፣ ከዚያ A \u003d n(n - 1)። ቀመሩን የበለጠ ካቀልነው እና ፋብሪካዎችን በመጠቀም ወደ ማስታወሻ ከቀየርን ፣ በጣም አጭር ቀመር እናገኛለን-A \u003d n! / (n - ሜትር)!
ጥምር
ከሞላ ጎደል ሁሉንም መሰረታዊ የማጣመር ቀመሮችን ከምሳሌዎች ጋር ተመልክተናል። አሁን ወደ መጨረሻው ደረጃ እንሸጋገር የመዋሃድ መሰረታዊ ኮርሶችን - ጥምሩን ማወቅ. አሁን እኛ ካለን n ውስጥ m ንጥሎችን እንመርጣለን, ሁሉንም በተቻለ መጠን ግን እንመርጣለን. ታዲያ ይህ ከመኖርያ እንዴት ይለያል? አንሆንም።ቅደም ተከተል ግምት ውስጥ ያስገቡ. ይህ ያልታዘዘ ስብስብ ጥምረት ይሆናል።
ወዲያውኑ ማስታወሻውን ያስተዋውቁ፡ C. የ m ኳሶችን ከ n ውስጥ እናስቀምጣለን። ለትዕዛዝ ትኩረት መስጠታችንን እናቆማለን እና ተደጋጋሚ ጥምረቶችን እናገኛለን. የጥምረቶችን ቁጥር ለማግኘት, የምደባዎችን ቁጥር በ m መከፋፈል ያስፈልገናል! (ሚ ፋክተር)። ማለትም C \u003d A / m! ስለዚህ, ከ n ኳሶች ለመምረጥ ጥቂት መንገዶች አሉ, ሁሉንም ነገር ለመምረጥ ስንት በግምት እኩል ነው. ለዚህ ምክንያታዊ አገላለጽ አለ: ትንሽ መምረጥ ሁሉንም ነገር ከሞላ ጎደል ከመጣል ጋር ተመሳሳይ ነው. እንዲሁም የእቃዎቹን ግማሹን ለመምረጥ በሚሞከርበት ጊዜ ከፍተኛው የጥምረቶች ብዛት ሊደረስ እንደሚችል እዚህ ላይ መጥቀስ አስፈላጊ ነው።
ችግርን ለመፍታት ቀመር እንዴት እንደሚመረጥ?
የማዋሃድ መሰረታዊ ቀመሮችን በዝርዝር መርምረናል፡ አቀማመጥ፣ መተላለፍ እና ጥምር። አሁን የእኛ ተግባር በኮሚኒቶሪክስ ውስጥ ችግሩን ለመፍታት አስፈላጊውን ቀመር መምረጥ ነው. የሚከተለውን በጣም ቀላል እቅድ መጠቀም ትችላለህ፡
- እራስህን ጠይቅ፡ የችግሩ ጽሁፍ ላይ የንጥረ ነገሮች ቅደም ተከተል ግምት ውስጥ ገብቷል?
- መልሱ የለም ከሆነ፣ እንግዲያውስ ጥምር ቀመሩን ይጠቀሙ (C=n! / (m!(n - m)!)))።
- መልሱ የለም ከሆነ፣ አንድ ተጨማሪ ጥያቄ መመለስ ያስፈልግዎታል፡ ሁሉም ንጥረ ነገሮች በጥምረት ውስጥ ተካትተዋል?
- መልሱ አዎ ከሆነ፣የማስተላለፊያ ቀመሩን (P=n!) ይጠቀሙ።
- መልሱ የለም ከሆነ፣ እንግዲያውስ የምደባ ቀመሩን ይጠቀሙ (A=n! / (n - m)!)።
ምሳሌ
የጥምር አካላትን፣ ቀመሮችን እና አንዳንድ ሌሎች ጉዳዮችን ተመልክተናል። አሁን ወደ እንቀጥልአንድ እውነተኛ ችግር ግምት ውስጥ በማስገባት. ከፊትህ ኪዊ፣ ብርቱካንማ እና ሙዝ እንዳለህ አስብ።
ጥያቄ አንድ፡ በስንት መንገድ እንደገና ማስተካከል ይቻላል? ይህንን ለማድረግ የፔርሙቴሽን ቀመር እንጠቀማለን-P=3!=6 መንገዶች።
ጥያቄ ሁለት፡ አንድ ፍሬ በምን ያህል መንገድ ሊመረጥ ይችላል? ይህ ግልጽ ነው ፣ እኛ ሶስት አማራጮች ብቻ አሉን - ኪዊ ፣ ብርቱካንማ ወይም ሙዝ ይምረጡ ፣ ግን ጥምር ቀመሩን እንተገብራለን-C \u003d 3! / (2!1!)=3.
ጥያቄ ሶስት፡በምን አይነት መንገድ ሁለት ፍሬዎችን መምረጥ ይቻላል? ምን አማራጮች አሉን? ኪዊ እና ብርቱካን; ኪዊ እና ሙዝ; ብርቱካንማ እና ሙዝ. ማለትም ፣ ሶስት አማራጮች ፣ ግን ይህ ጥምር ቀመሩን በመጠቀም ማረጋገጥ ቀላል ነው-C \u003d 3! / (1!2!)=3
ጥያቄ አራት፡በምን አይነት መንገድ ሶስት ፍሬዎችን መምረጥ ይቻላል? እንደሚመለከቱት, ሶስት ፍሬዎችን ለመምረጥ አንድ መንገድ ብቻ አለ: ኪዊ, ብርቱካንማ እና ሙዝ ይውሰዱ. ሲ=3! / (0!3!)=1.
ጥያቄ አምስት፡ቢያንስ አንድ ፍሬ ምን ያህል መንገድ መምረጥ ይቻላል? ይህ ሁኔታ አንድ, ሁለት ወይም ሁሉንም ሶስት ፍሬዎች መውሰድ እንደምንችል ያመለክታል. ስለዚህ, C1 + C2 + C3=3 + 3 + 1=7. ማለትም ከጠረጴዛው ላይ ቢያንስ አንድ ፍሬ ለመውሰድ ሰባት መንገዶች አሉን.
