Кіріспе
Дәлелдеу техникасының түрі. Комбинаторикада қос санау, сондай-ақ екі жолмен санау деп аталатын бұл әдіс, екі өрнектің тең екенін көрсету үшін қолданылатын комбинаторлық дәлелдеу техникасы. "Комбинаторикадағы ең маңызды құралдардың бірі" деп есептелетін бұл техникада, бір жиынның мөлшерін екі түрлі жолмен санау арқылы екі өрнекке жету мүмкіндігі қарастырылады. Екі өрнек те сол жиынның мөлшерін көрсететіндіктен, олар бір-бірімен тең болады.
In combinatorics, double counting, also called counting in two ways, is a combinatorial proof technique for showing that two expressions are equal by demonstrating that they are two ways of counting the size of one set. In this technique, which call "one of the most important tools in combinatorics", one describes a finite set from two perspectives leading to two distinct expressions for the size of the set. Since both expressions equal the size of the same set, they equal each other.
(Натурал сандарды) көбейту
Бұл екі рет санаудың қарапайым мысалы, көбінесе кішкентай балаларға көбейтуді үйретуде қолданылады. Осы контексте, натурал сандардың көбейтуі қайталанатын қосу ретінде ұсынылады, содан кейін тікбұрышты торға орналастырылған бірнеше затты екі түрлі жолмен санау арқылы көбейтудің өзгешелігі (коммутативтілігі) көрсетіледі. Егер торда қатарлар мен бағандар болса, онда біз алдымен қатарлардағы заттарды қосып санаймыз, содан кейін бағандардағы заттарды қосып екінші рет санаймыз, осылайша, осы нақты қатарлар мен бағандар саны үшін, .
Комитеттерді құру
Екі еселік есептеу әдісінің бір мысалы – адамдардан комитет құрастырудың қанша тәсілмен болатынын санау, мұнда комитетке адамдардың кез келген саны (тіпті бірі де болмаса) кіре алады. Яғни, элементі бар жиынның қанша ішкі жиыны болатынын есептеу. Комитет құрудың бір жолы – әр адамнан оған қатысу-қатыспауын сұрау. Әр адамның екі таңдауы бар – «иә» немесе «жоқ», және бұл таңдаулар басқа адамдардың таңдауларынан тәуелсіз. Сондықтан мүмкіндік бар. Басқаша айтқанда, комитет мөлшері 0-ден -ге дейінгі сан болуы керек екенін байқауға болады. Әр мүмкін мөлшер үшін, адамдардан адамдық комитет құрудың қанша тәсілі бар екені – биномдық коэффициентіне тең.
Therefore the total number of possible committees is the sum of binomial coefficients over Equating the two expressions gives the identity
a special case of the binomial theorem. A similar double counting method can be used to prove the more general identity
Осылайша, мүмкін комитеттердің жалпы саны – биномдық коэффициенттердің қосындысына тең. Екі өрнекті теңестіргенде, біртұтас биномдық теореманың ерекше жағдайы шығады. Осыған ұқсас екі еселік есептеу әдісін жалпы сәйкестікті дәлелдеу үшін де қолдануға болады.
Therefore the total number of possible committees is the sum of binomial coefficients over Equating the two expressions gives the identity
a special case of the binomial theorem. A similar double counting method can be used to prove the more general identity
Қол алысу леммасы
Екі еселік санау аргументімен дәлелденетін тағы бір теорема, кез келген бағытталмаған графтың тақ дәрежелі төбелерінің саны жұп болатынын айтады. Яғни, іргелес қабырғаларының саны тақ болатын төбелердің саны жұп болуы керек. Көбінесе, адамдар қол алысқан бір топта, қолдарды тақ санымен ұстаған адамдардың саны жұп болуы керек; осы себепті бұл нәтиже қол алысу леммасы деп аталады. Мұны екі еселік санау арқылы дәлелдеу үшін, төбелердің дәрежесін деп белгілейік. Графтың төбе-қабырға инциденттерінің саны екі түрлі жолмен есептелуі мүмкін: төбелердің дәрежелерін қосу арқылы немесе әрбір қабырға үшін екі инцидентті санау арқылы. Сондықтан,
мұнда – қабырғалардың саны. Демек, төбелердің дәрежелерінің қосындысы жұп сан болады, егер төбелердің тақ саны тақ дәрежелі болса, онда мұндай жағдай мүмкін емес. Осы факт, осы дәлелмен бірге, 1736 жылы Леонхард Эйлердің «Кенигсбергтің жеті көпірі» туралы еңбегінде кездеседі, ол графтар теориясын зерттеуді бастады.
Қосымша мысалдар
Вандермонд сәйкестігі, биномдық коэффициенттердің қосындыларына қатысты тағы бір сәйкестік, оны екі рет санау арқылы дәлелдеуге болады. Төртбұрышты пирамида саны. Бірінші квадрат сандардың қосындысы мен кубтық көпмүшелік арасындағы теңдік сандардың үштіктерін екі рет санау арқылы көрсетілуі мүмкін, мұндағы сан қалған екі саннан үлкен. Любелл–Ямамото–Мешалькин теңсіздігі. Любеллдің жиындық отбасыларындағы осы нәтиженің дәлелі – пермутациялар бойынша екі рет санау аргументі, ол теңдік емес, теңсіздікті дәлелдеу үшін қолданылады. Эрдёш–Ко–Радо теоремасы, жиындардың қиылысатын отбасыларының жоғарғы шегі, Гюла О.Х. Катона екі рет санау теңсіздігін пайдаланып дәлелдеді. Ферманың кішкентай теоремасының дәлелі. Екі рет санау арқылы бөлінбелілікті дәлелдеу: кез келген жай сан және натурал сан үшін екі немесе одан көп символдары бар символдар әліпбиі бойынша ұзындығы сөздер бар. Бұларды бір-біріне дөңгелек ауысу арқылы өзгеруі мүмкін сөздердің топтарына біріктіруге болады; мұндай топтар алқалар деп аталады. Сондықтан, (алқалар саны) жай санға бөлінеді. Квадраттық өзара байланыс дәлелі. Айзенштейннің дәлелі үшбұрыштағы торлық нүктелерді екі рет санау арқылы маңызды сандық теориялық фактіні шығарады.
Қатысушы тақырыптар
Биективті дәлелдеме. Екі рет санау бір жиынды екі түрлі жолмен санау болса, биективті дәлелдеме екі жиынды бір түрлі жолмен санауды білдіреді, олардың элементтерінің бір-бірге сәйкес екенін көрсетеді. Қосылу-азайту принципі – жиынтардың бірігінің мөлшерін анықтайтын формула, оны сол бірігінің тағы бір формуласымен бірге екі рет санау аргументінің бір бөлігі ретінде пайдалануға болады.