8.3. Іріктеу тәсілі арқылы комбинаторикалық есептерді шығару

Іріктеу тәсілі — есептің барлық мүмкін нұсқаларын белгілі бір ретпен тізіп шығып, оларды санау. Бірде-бір нұсқа жоғалмауы және ешқайсысы екі рет саналмауы үшін нұсқаларды жүйелі түрде жазамыз.

Мүмкін нұсқалар ағашы — іріктеудің сызбасы. Ағаштың түбі $*$ белгісімен белгіленеді, әр деңгей — бір таңдау қадамы, түбінен соңғы нүктеге дейінгі әр жол (бұтақ) — бір нұсқа. Соңғы нүктелер саны — нұсқалар саны.

1. Нысандарды қысқа белгілейміз: аттарды бас әріппен, заттарды не түстерді цифрмен.

2. Нұсқаларды ретпен жазамыз: бірінші орынға бірінші элементті қойып, оның барлық жалғасын тіземіз, содан кейін келесі элементке көшеміз (алфавит не өсу ретімен).

3. Реті маңызды ма — алдымен соны анықтаймыз. Кезекшілік, сан құрастыру, орынға отырғызу есептерінде реті маңызды ($15$ мен $51$ — әртүрлі сандар). Кесінді, қол алысу, екі адамды таңдау есептерінде реті маңызды емес ($AB$ пен $BA$ — бір кесінді), сондықтан әр жұпты бір рет, алфавит ретімен жазамыз — «үшбұрышты кесте» шығады.

4. Ағаштың әр тармағындағы бұтақтар саны бірдей болса, нұсқалар санын көбейтумен табамыз: бірінші қадамда $3$, екіншіде $2$ мүмкіндік болса, барлығы $3 \cdot 2 = 6$.

Мысал 1: $1$, $5$, $8$ цифрларынан цифрлары қайталанбайтын неше екі таңбалы сан жазуға болады? Ондықтар цифры — $1$, $5$ не $8$ ($3$ бұтақ), бірліктер цифры — қалған екі цифрдың бірі (әрқайсысынан бұтақ). Сандар: , , , , , — барлығы .

Суретте осы мысалдың мүмкін нұсқалар ағашы берілген: $6$ бұтақ — $6$ сан.

Мысал 2: $A$, $B$, $C$, $D$ төрт дос бір-бірімен бір реттен қол алысты. Реті маңызды емес, сондықтан: $AB$, $AC$, ; , ; . Барлығы рет.

Суретте әр қол алысу екі нүктені қосатын кесіндімен көрсетілген: барлығы $6$ кесінді.

Жиі қате: реті маңызды емес жағдайда $AB$ мен $BA$-ны екі нұсқа деп санау (жауап екі есе артық шығады); сан құрастырғанда $0$ цифрын бірінші орынға қою; нұсқаларды ретсіз жазып, біреуін жіберіп алу.