Айталанбайтын орналастырулар

 

n- нен k бойынша қайталанбайтын орналастыру деп n элементтен құралған жиынның k элементтен тұратын ішкі жиынын айтады.

Екі орналастыру элементтердің орналасу реті бойынша бір-бірінен өзгешеленеді. Мысалы, 1,2,5 және 1,5,2 сандарының орналасуында құрамы бірдей, ал элементтерінің реті өзгеше, сондықтан бұл орналастырулар әр түрлі.

n- нен k бойынша қайталанбайтын орналастырулар санын арқылы белгіленеді.

Теорема. = .

Дәлелдеу. Орналастырудың берілгендерін құрастырған кезде бірінші орынға n элементтің кез келгенін қоюға болады. Екінші орынға қалған (n – 1) элементтерінің кез келгенін қоюға болады. Әрі қарай осылай кете береді. k -ші орынға қалған n – k + 1 элементтерінің кез келгенін қоюға болады. Көбейтінді ережесі бойынша n- нен k бойынша жалпы орналастырулар саны = n × (n – 1)×…×(n – k + 1) = .

Мысал. Футбол бойынша дүние жүзілік чемпионатында 18 команда қатысады. Қанша тәсілмен медальдар командалар арасында берілуі мүмкін?

Бұл жерде орналастыру санын табу керек, себебі алтын, күміс және қола медальдардың берілуін ескеру керек. Және де олар бір-бірден ғана беріледі.

n -дәрежелі алмастыруы орналастырудың жеке жағдайлары болып табылады, яғни әрбір n – дәрежелі алмастыру n- нен n бойынша орналастыру.

 

Айталанбайтын терулер

 

n- нен k бойынша қайталанбайтын теру деп n элементтен тұратын жиынның k элементтен тұратын іш жиынды айтады.

Екі терудің айырмашылығы орналасуында емес, тек элементтерінің құрамында. Сондықтан элементтердің орналасуы терулерде ескерілмейді. 1, 2, 3 және 1, 3, 2 терулері бірдей деп есептеледі.

n = 5, k = 3 болғанда 10 теру бар болады: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

Барлық n- нен k бойынша алынған қайталанбайтын терулер санын арқылы белгілейді және биномдық коэффициент деп атайды.

Теорема. = .

Мысал. Сыныпта 30 оқушы бар. Неше әдіспен 3 кезекшіні таңдап алуға болады? Берілген жағдайда элементтер арасындағы тәртіпті ескерудің қажеті жоқ, сондықтан кезекшілерді таңдау әдістер саны терулер санымен өрнектеледі.

Дәлелдеу. n- нен k бойынша барлық терулерді құрастырайық. Содан кейін әрбір терудегі элементтерді барлық мүмкін әдістермен алмастырамыз. Осыдан құрамымен немесе элементтерінің ораласу ретімен ерекшеленетін тізбекті аламыз. Сонымен бұл n- нен k бойынша алынған барлық мүмкін болатын орналастырулар болады. Олардың саны . Әрбір теру k! орналасуын береді. Көбейтінді ережесі бойынша

= × k!. Бұдан = = .

сандары үшін биномдық коэфициент деген атын келесі формула көрсетеді:

(a + b) ⁿ = aⁿ + a^{n –1} b +…+ a^kb^{n – k} +…+ ab^{n –1} + bⁿ.

Егер a = 1, b = 1 деп қойсақ, онда 2 ⁿ = + +…+ +…+ + , формуласын аламыз, себебі = = 1. Осылай биномдық коэфициент қосындысы 2 ⁿ -ге тең.

Есеп 1. m ´ n өлшемді тақтаның торынан неше түрлі төртбұрыштар қиып алуға болады?

			.	n
.
m

Төртбұрыш қабырғаларының орналасуымен анықталады. Көлденеңінен қабырғалар m + 1 жағдайдың кез келгенінен орын алады. Онда оларды таңдау әдістер саны . Тігінен қабырғаларды әдістермен таңдауға болады. Көбейтінді ережесі бойынша, төртбұрыштар саны × .

Лексикографикалық ретте терулер алгоритмін келтірейік. 1, 2,..., k бірінші теру болады (алғашқы k сандары өспелі тәртіпте), ал соңғысы n – k + 1,…, n теруі (соңғы k сандары өспелі тәртіпте).

1) 1, 2,..., k алғашқы теру құралады.

2) Келесі теру a ₁,…, a_k a_i = i (a_n = n, a_{n –1} = n – 1 теңдік бұзылғанша дейін) теңдігі орындалғанша дейін оңнан солға қарай қарастырылады.

3) Егер i = n – k болса, онда 7-ші пунктке көшу керек.

4) Егер i > n – k, онда а_i -ді 1-ге арттырамыз: a_i = a_i + 1.

5) Келесі элементтерді өспелі тәртіпте аламыз: a_j = a_{j –1} + 1,

j = i +1,…, n – 1.

6) Келесі теру дайын. Оны экранға (файлға, басылымға) шығару керек. 2-ші пунктке көшу керек.

7) Алгоритм соңы.

Кез келген n -нен k бойынша теру k бірлігі бар n-өлшемді екілік векторлармен тығыз байланысты. k бірлігі бар b = (b ₁,…, b_n) – екілік вектор болсын. b_i = 1 болғанда, тек сонда ғана i Î S болатын b векторына S жиыны сәйкес келеді.

Лексикографикалық ретте терулер екілік тізбекке сәйкес келеді.

Есеп 2. Дөңес n -бұрыштың диагональдары неше нүктеде қиылысады, ал олардың үшеуі бір де бір нүктеде қиылыспайтын болса ше?

Әрбір екі диагональдың қиылысу нүктесіне n -бұрыштың 4 төбесі сәйкес келеді. n -бұрыштың әрбір 4 төбесіне 1 қиылысу нүктесі сәйкес келеді. Сондықтан барлық қиылысу нүктелерінің саны n төбеден 4 төбені таңдап алу әдістердің санына тең болады: = .

Есеп 3. Өлшемі m ´ n (“шахмат қаласы”) болатын, тіктөртбұрышты шаршылар торын қарастырайық. Ол n – 1 көлденеңінен және m – 1 тігінен көшелерге бөлінген m ´ n тіктөртбұрыштардан құралады. Бұл торда төменгі сол жақ бұрыштан ((0; 0) нүктесінен) жоғарғы оң жақ бұрышына ((m, n) нүктесіне) апаратын әр түрлі қысқа жолдардың саны қандай?

 

(0, n)							(m, n)
(0, 0)							(m, 0)

Шешімі: (0; 0) нүктесінен (m, n) нүктесіне апаратын әрбір қысқа жол m + n кесінділерден тұрады. Олардың ішінде m көлденеңінен және n тігінен кесінділер бар. Әр түрлі жолдан көлденеңінен және тігінен кесінділердің алмасу ретімен ғана өзгешеленеді, яғни .

Тігінен n кесіндіні, көлденеңінен m кесіндіні таңдау әдістер санын қарастыруға болады, онда біз жауабын алар едік. Сонымен бірге біз = теңдігін орнаттық.