Сочетание

В комбинаторике сочетанием из




n


{\displaystyle n}

по




k


{\displaystyle k}

называется набор




k


{\displaystyle k}

элементов, выбранных из данного множества, содержащего




n


{\displaystyle n}

различных элементов.

Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Так, например, наборы (3-элементные сочетания, подмножества,




k
=
3


{\displaystyle k=3}

) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} (




n
=
6


{\displaystyle n=6}

) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

В общем случае число, показывающее, сколькими способами можно выбрать




k


{\displaystyle k}

элементов из множества, содержащего




n


{\displaystyle n}

различных элементов, стоит на пересечении




k


{\displaystyle k}

-й диагонали и




n


{\displaystyle n}

-й строки треугольника Паскаля.

Число сочетаний

Число сочетаний из




n


{\displaystyle n}

по




k


{\displaystyle k}

равно биномиальному коэффициенту







(


n
k


)



=

C

n


k


=



n
!


k
!

(

n

k

)

!



.


{\displaystyle {n \choose k}=C_{n}^{k}={\frac {n!}{k!\left(n-k\right)!}}.}

При фиксированном




n


{\displaystyle n}

производящей функцией последовательности чисел сочетаний








(


n



)






{\displaystyle {\tbinom {n}{0}}}

,








(


n
1


)






{\displaystyle {\tbinom {n}{1}}}

,








(


n
2


)






{\displaystyle {\tbinom {n}{2}}}

, … является:







k
=



n





(


n
k


)




x

k


=
(
1
+
x

)

n


.


{\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}x^{k}=(1+x)^{n}.}

Двумерной производящей функцией чисел сочетаний является







n
=









k
=



n





(


n
k


)




x

k



y

n


=



n
=






(
1
+
x

)

n



y

n


=


1

1

y

x
y



.


{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}=\sum _{n=0}^{\infty }(1+x)^{n}y^{n}={\frac {1}{1-y-xy}}.}

Сочетания с повторениями

Сочетанием с повторениями называются наборы, в которых каждый элемент может участвовать несколько раз.
В частности, количество монотонных неубывающих функций из множества




{
1
,
2
,

,
k
}


{\displaystyle \{1,2,\dots ,k\}}

в множество




{
1
,
2
,

,
n
}


{\displaystyle \{1,2,\dots ,n\}}

равно числу сочетаний с повторениями из




n


{\displaystyle n}

по




k


{\displaystyle k}

.

Число сочетаний с повторениями из




n


{\displaystyle n}

по




k


{\displaystyle k}

равно биномиальному коэффициенту







C

n


k


¯


=

C

(
n
)


k


=

(






(


n
k


)






)

=



(



n
+
k

1


n

1



)



=



(



n
+
k

1

k


)



=
(

1

)

k





(




n

k


)



=



(
n
+
k

1
)
!


k
!

(
n

1
)
!



.


{\displaystyle {\overline {C_{n}^{k}}}=C_{(n)}^{k}=\left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{n-1}}={\binom {n+k-1}{k}}=(-1)^{k}{\binom {-n}{k}}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}.}

При фиксированном




n


{\displaystyle n}

производящей функцией чисел сочетаний с повторениями из




n


{\displaystyle n}

по




k


{\displaystyle k}

является:







k
=






(

1

)

k





(




n

k


)




x

k


=
(
1

x

)


n


.


{\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{-n \choose k}x^{k}=(1-x)^{-n}.}

Двумерной производящей функцией чисел сочетаний с повторениями является:







n
=









k
=






(

1

)

k





(




n

k


)




x

k



y

n


=



n
=






(
1

x

)


n



y

n


=



1

x


1

x

y



.


{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }(-1)^{k}{-n \choose k}x^{k}y^{n}=\sum _{n=0}^{\infty }(1-x)^{-n}y^{n}={\frac {1-x}{1-x-y}}.}

См. также

  • Комбинаторика
  • Перестановка
  • Размещение
  • Многочлен

Примечания

Ссылки

  • Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990.

Error: 404 Not Found.

3х элементные подмножества 5 элементного множества

Рассказать друзьям:
Смотреть:
Мельница (значения)