የቆጠራ መርሆች

ከውክፔዲያ

ሥነ ጥምረት ውጤቶችን ለማረጋገጥ የሚረዱ መሰረተ ሃሳቦች የጥምረት መርሆች በመባል ይታወቃሉ። የመደመር ሕግየማባዛት ሕግ እና ወጋኝና አግላይ መርህ ለቆጠራ የሚያገለግሉ የሥነ ጥምረት መርሆች ናቸው። ሁለት ስብስቦች አንድ አይነት የአባላት ብዛት እንዳላቸው ለማረጋገጥ ደግሞ የተጣምዶ ማረጋገጫ ሚባለው መሰረተ ሃሳብ ይረዳል። የደበኔ ሳጥን መርህ ብዙ ጊዜ ያንድን ነገር መኖር ወይም ደግሞ ያንድን ነገር በጣም አንስተኛ ወይም ከፍተኛ ቁጥር ብዛት ለማረጋገጥ ይረዳል። ሁለቴ ቆጠራ እና የተለዩ አባላት ስሌት የተሰኙት መርሆወች በበኩላቸው የሥነጥምረት እኩልዮሾችን ለማረገጋገጥ አይነተኛ ዘዴዎች ናቸው። መፍጠሪያ አስረካቢዎች ና ዓይንባይን ዝምድናዎች ከፍተኛ ሃይል ያላቸው፣ የድርድር እና የሥነጥምረት ጥያቄዎችን ለመፍታት የሚያገለግሉ ወይም በጠራ ሁኔታ ለምግለጽ የሚያገለግሉ መሰረተ ሃሳቦች ናቸው።


የመደመር ህግ[ለማስተካከል | ኮድ አርም]

ዋና መጣጥፍ፦ የመደመር ህግ

አንድን ነገር ለማድረግ a መንገዶች ቢኖሩ እና ሌላ ነገር ለማድረግ b መንገዶች ቢኖሩ፣ ሁልቱን በአንድ ጊዜ ማድረግ ባይቻል፣ ከሁሉ አንድ ነገር ለማድረግ a + b መንገዶች አሉ ማለት ነው። አንድን ነገር ለመምረጥ a መንገዶች ቢኖሩ እና ሌላ ክዚህ ነገር ጋር የማይገናኝ ነገር ለመምረጥ b መንገዶች ቢኖሩ፣ ሁሌቱን አንድ ላይ መምረጥ ባይቻል፣ ከሁልቱ አንዱን ለመምረጥ a + b መንገዶች አሉ ማለት ነው። የአንድ ሙከራ ውጤት a ብዛት ሊኖራቸው የሚችል ቢሆን እና የሌላ ሙከራ ውጤት b ብዛት ሊኖራቸው ይሚችል ቢሆን፣ ሁለቱም ሙከራዎች አንድ ላይ ሊከወኑ የማይችሉ ቢሆኑ፣ የሁለቱ ሙክራዎች አጠቃላይ ውጤት a + b ሊሆን ይችላል ማለት ነው።

የመደመር ህግ

፣ እያንዳንዱ ስብስብ ከሌላው ስብስብ ጋር የየቅል ነው፣ ማለት የጋራ አባል የለውም


ምሳሌ

መሰረት እቤቷ ውስጥ 10 ጫማወች አሏት። እመኪናዋ ውስጥ 3 አይነት ጫማዎች አሏት። ጫማ አርጋ ስራ ለመሄድ ስንት አይነት ምርጫዎች አላት? እቤት ውስጥ 10+ መኪናዋ 3 = 13 አይነት ማለት ነው።

የማባዛት ህግ[ለማስተካከል | ኮድ አርም]

ዋና መጣጥፍ፦ የማባዛት ህግ

አንድን ነገር ለማድረግ a መንገዶች ቢኖሩና ሌላ ነገርን ለማድረግ b መንገዶች ቢኖሩ፣ ሁለቱን ነገሮች አንድ ላይ ለማድረግ a · b መንገዶች አሉ።

የማባዛት ህግ

ካርቴዣን ብዜት ይሰኛል። </math>


ምሳሌ

ከአበበ ቤት ወደ ሰሎሞን ቤት ለመሄድ 6 መንገዶች አሉ። ከስሎሞን ቤት ወደ መሰረት ቤት ለመሄድ 3 መንገዶች አሉ። ከአበበ ቤት ወደ መሰረት ቤት ለመጓዝ ስንት መንገዶች አሉ? መልሱ፡ 6*3 = 18 ነው።፡፡

ወጋኝ እና አግላይ መርህ[ለማስተካከል | ኮድ አርም]

የወጋኝ አግላይ መርህ በሶስት ስብስቦች ላይ

ዋና መጣጥፍ፦ ወጋኝ አግላይ መርህ

ወጋኝና አግላይ መርህ የብዙ ስብስቦችን ውህድ ብዛት ከተዋሃዱት ስብስቦች ቁጥር እና ከጋራ አባላቶቻቸው ብዛት አንጻር የሚያገኝ ነው። ለምሳሌ ሁለት ስብስቦችን A እና B ን ብንወስድ፣ የውህደታቸው ብዛት የእያንዳንዱ ስብስብ A እና B ብዛት ተደምሮ፣ ከዚህ ላይ የጋራ የሆኑት አባላቶች ብዛት ሲቀነስ ማለት ነው። ምክንያቱም የእያንዳንዱ ስብስብ አባላት ሲደመሩ፣ የጋራ የሆኑት አባላት ብዛት ሁለት ጊዜ ተደምረዋልና። ስለሆነም

ምሳሌ፡

አንድ ሳህን ውስጥ {እንጀራ፣ ኬክ፣ ዳቦ} አለ። ሌላ ሳህን ውስጥ {ኬክ፣ ዳቦ፣ ብስኩት፣ ከረሜላ}። አለሚቱ ከሁለቱ ሳህኖች አንድ ምግብ መምረጥ ቢፈቀድላት፣ ስንት ምርጫ አላት? ከመጀመሪያው ሳህን ለመምረጥ 3 መንገድ አላት። ከሁለተኛው ሳህን በ4 መንገድ መምረጥ ትችላለች። ስለዚህ ሁለቱን ስንደምር፣ 3+4 = 7 ምርጫ አላት። ሆኖም ይሄ ስህተት ነው፣ ምክንያቱም ኬክና ዳቦው የሁለቱ ስብስብ የጋራ ናቸውና። ስለሆነም አጠቃላይ ምርጫዋ 3+7-2 = 5 ብቻ ነው ማለት ነው፦ እንጀራ፣ ኬክ፣ ዳቦ፣ ብስኩት፣ ክረሜላ

ለሶስት ስብስቦች የሚሰራወ የወጋኝ አግላይ መርህ ቀመር ይህን ይመስላል፡

.

ይሄ መርህ ለብዙ ስብስቦች ሲጠቃለል፣ A1, ..., An አላቂ ስብስቦች ቢሆኑ

ወጋኝና አግላይ ቀመር

አግላይ እና ወጋኝ መርህ


የደበኔ ሳጥን መርህ[ለማስተካከል | ኮድ አርም]

(10) ደበኔዎች (9) ሳጥኖች ውስጥ ተቀምጥዋል፣ ስልሆንም አንዱ ሳጥን ከአንድ በላይ ደበኔ ይዟል

ዋና መጣጥፍ፦ የደበኔ ሳጥን ምርህ

የደበኔ ሳጥን መርህ እሚለው a ነገሮች b ሳጥኖች ውስጥ ቢቀመጡ, የነገሮቹ ብዛት ከሳጥኖቹ ብዛት ቢበልጥ a > b፣ አንዱ ሳጥን ሁለት ነገሮችን የግዴታ ይዟል።

ምሳሌ፡ አንድ ሻንጣ ውስጥ 12ሰማያዊ ካልሲዎችና 18ጥቁር ካልሲወች አሉ። አይናችንን ጨፍነን ስንት ካልሲ ከሳጥኑ ብናወጣ የግዴታ አንድ አይነት ቀለም ያላቸው ሁለት ካልሲዎች ልናገኝ እንችላለን? ለአንዱ ቀለም አይነት አንድ ሳጥን ብናበጅ እና ለሌላው አንድ ሳጥን ብናበጅ፣ ሁለት ሳጥን በቀለሞች አሉን። ሶስት ካልሲዎች ብናወጣ የግዴታ ሁለቱ አንዱ ሳጥን ውስጥ መውደቅ አለባቸው (አንድ አይነት ቀለም መሆን አለባቸው)፣ ስለሆነም መልሱ 3 ነው ማለት ነው።


ተጣምዶ ማረጋገጫ[ለማስተካከል | ኮድ አርም]

ዋና መጣጥፍ፦ ተጣምዶ ማረጋገጫ የተጣምዶ ማረጋገጫ አንድን ስብስብ ከሌላ ስብስብ ጋር ሊያዛምድ የሚችል አጣማጅ አስረካቢ ፈልጎ በማግኘት ሁለቱ ስብስቦች እኩል አባላት እንዳላቸው የሚረጋገጥበት መርህ ነው።

ሁለቴ ቆጠራ[ለማስተካከል | ኮድ አርም]

ዋና መጣጥፍ፦ ሁለቴ ቆጠራ

የአንድን ስብስብ ብዛት በሁለት አይነት መንገድ የምንቆጥርበት ሂደት ነው።


የተለይ አባል ስሌት[ለማስተካከል | ኮድ አርም]

ዋና መጣጥፍ፦ የተለየ አባል ስሌት

የተለየ አባል ስሌት ከአንድ ስብስብ ውስጥ አንድ ዓባልን ለይቶ በማውጣት ስለዚያ ስብስብ የሆነ ውጤትን ሲያረጋግጥ ማለት ነው።

መፍጠሪያ አስረካቢ[ለማስተካከል | ኮድ አርም]

ዋና መጣጥፍ፦ መፍጠሪያ አስረካቢ መፍጠሪያ አስረካቢዎች (ጄኔሬቲንግ ፈንክሽን) አእላፍ ተርም ያላቸው ፖሊኖሚያል ሲሆኑ፣ ኮፊሽንታችው የሆነ የቁጥር ድርድር የሚሰራ ነው። ይህ አይኔት የድርድር አወካከል ዘዴ በሂሳብ ዘንድ ብዙ በር የምሚከፍታና አዳዲስ እኩልዮሾችን የሚያስገኝ እንዲሁም ልዩ ልዩ ቀመሮችን የሚያስገኝ ነው። ከነዚህ መፍጠሪያ አስረካቢዎች ውስጥ ተራ የሚባለው ይሄን ይመስላል an

ዓይንበዓይን ዝምድና[ለማስተካከል | ኮድ አርም]

ዋና መጣጥፍ፦ ዓይንባይን ዝምድና

ዓይንባይን ዝምድና እያንዳንዱን የድርድር አባል በቀደሙት አባላት ይተረጉማል። ለምሳሌ የአንድ ከተማ ሰው ብዛት በዚያ ከተማ ከነበረው የሰው ብዛት አንጻር ሲተረጎም ማለት ነው። ለድርድር ጥናት ጠቃሚ ነው።


ዋቢ መጻሕፍት[ለማስተካከል | ኮድ አርም]

  • {en} J. H. van Lint and R. M. Wilson (2001), A Course in Combinatorics (Paperback), 2dn edition, Cambridge University Press. ISBN 0521006015