Кіріспе
Конвольді биномдық коэффициенттер туралы математикалық теорема
арнайы детерминанттың өрнегі
Комбинаторикада Вандермондтың сәйкестігі (немесе Вандермондтың конволюциясы) – биномдық коэффициенттерге қатысты келесі теңдік:
the expression for a special determinant
In combinatorics, Vandermonde's identity (or Vandermonde's convolution) is the following identity for binomial coefficients:
кәз келген теріс емес бүтін сандар r, m, n үшін. Бұл теңдік Александр Теофиль Вандермондтың (1772) құрметіне аталған, бірақ оны 1303 жылы қытай математигі Чжу Шицзе білген. Осы теореманың q-аналогы бар, ол q-Вандермонд сәйкестігі деп аталады. Вандермондтың сәйкестігін көптеген тәсілдермен, соның ішінде жалпылауға болады.
Геометриялық дәлелдеу
r x (m+n−r) квадраттарынан тұратын тіктөртбұрышты тор алыңыз. Төменгі сол бұрышынан басталып, тек жоғары немесе оңға қарай жылдамдықпен қозғалатын жолдар оң жақ жоғарғы бұрышында аяқталады (мұнда r оңға, ал m + n − r жоғары жылдамдықтар кез келген ретпен (немесе керісінше) жасалуы керек, ал жолдың жалпы ұзындығы m + n болады). Төменгі сол бұрышты (0, 0) деп атаңыз. (0, 0) нүктесінен басталып (k, m−k) нүктесінде аяқталатын жолдар бар, себебі k оңға және m−k жоғары жылдамдықтар жасалуы керек (және жолдың ұзындығы m). Сол сияқты, (k, m−k) нүктесінен басталып (r, m+n−r) нүктесінде аяқталатын жолдар бар, себебі барлығы r−k оңға және (m+n−r) − (m−k) жоғары жылдамдықтар жасалуы керек, ал жолдың ұзындығы r−k + (m+n−r) − (m−k) = n болуы керек. Осылайша, (0, 0) нүктесінен басталып, (r, m+n−r) нүктесінде аяқталып, (k, m−k) нүктесі арқылы өтетін жолдар бар. Бұл (0, 0) нүктесінен басталып, (r, m+n−r) нүктесінде аяқталатын барлық жолдардың ішкі жиыны болып табылады, сондықтан k = 0-ден k = r-ге дейін қосымшаласақ (нүкте (k, m−k) квадраттың ішінде болуы керек), (0, 0) нүктесінен басталып, (r, m+n−r) нүктесінде аяқталатын жолдардың жалпы санын аламыз.
paths that start on the bottom left vertex and, moving only upwards or rightwards, end at the top right vertex (this is because r right moves and m+n r up moves must be made (or vice versa) in any order, and the total path length is m + n). Call the bottom left vertex (0, 0). There are paths starting at (0, 0) that end at (k, m−k), as k right moves and m−k upward moves must be made (and the path length is m). Similarly, there are paths starting at (k, m−k) that end at (r, m+n−r), as a total of r−k right moves and (m+n−r) − (m−k) upward moves must be made and the path length must be r−k + (m+n−r) − (m−k) = n. Thus there are
paths that start at (0, 0), end at (r, m+n−r), and go through (k, m−k). This is a subset of all paths that start at (0, 0) and end at (r, m+n−r), so sum from k = 0 to k = r (as the point (k, m−k) is confined to be within the square) to obtain the total number of paths that start at (0, 0) and end at (r, m+n−r).
Гипергеометриялық ықтималдық үлестірімі
Екі жақ сол жақтағы өрнекке бөлінгенде және қосындысы 1-ге тең болғанда, онда қосындының мүшелерін ықтималдықтар деп қарастыруға болады. Соның нәтижесінде пайда болатын ықтималдық үлестірімі – гипергеометриялық үлестірім. Яғни, бұл n қызыл және m көк шарлары бар ыдыстан алмастырусыз r рет тартылған қызыл шарлар санының ықтималдық үлестірімі.