Главное меню

Что такое сочетания? Какая формула сочетаний в комбинаторике?

Автор Богдан_Р, Март 14, 2024, 20:08

« назад - далее »

Богдан_Р

Помогите решить Что такое сочетания? Какая формула сочетаний в комбинаторике?.

Brurarl

Сочетания это когда выбирается некое количество различных элементов k из множества с n  элементами. Например есть множество из n = четырех ягод: {клубника, малина, смородина, крыжовник}
И нам для пирожка надо выбрать k = две разные ягоды и вот мы выбираем сочетающиеся ягоды: {клубника и малина}; {клубника и смородина}; {клубника и крыжовник}; {малина и смородина}; {малина и крыжовник}; {смородина и крыжовник}. Причем не важно в каком порядке мы их взяли в пирожке они перемешаются и просто будет двойной вкус. Таким образом можем получить 6 различных по вкусу пирожков. Так вот такое количество различных наборов называется количеством сочетаний.
Но в задачах с другими формулировками  можно интерпретировать, как сочетания и свести её к выбору k-элементов из n
Например 3 куста надо посадить, но ямок выкопано 5 штук. Сколько способов?
Если ямки пронумеруем {1; 2; 3; 4; 5}, то нам предстоит выбрать наборы по 3 ямки, в которые будем сажать кусты. можем выбрать ямки {1; 2; 3} или {2; 4; 5}  и т.д. пока не переберем все возможные варианты. Причем так же не важно в каком порядке будем выбирать ямки, они будут заняты одинаковыми кустами. Посчитав все эти варианты получим количество сочетаний.
Но каждый раз перебирать долго, сложно. Можно ошибиться, особенно если количество большое.
Для этого существует обозначение количества сочетаний: "С из n по k" и считается по определенной формуле С(из n по k) = n! / (k!•(n-k)!
Например: когда выбирали ягоды из n=4 по  k=2
C²₄ = 4! / (2!•(4-2)!) = 1•2•3•4 / ( 1•2 • 1•2) = 2•3 = 6
А в задаче про: из n=5 ямок выбрать по k=3 ямки для 3 кустов
C³₅ = 5! / (3!•(5-3)!) =  1•2•3•4•5 / (1•2•3 • 1•2) = 4•5 / 2 = 10 способов выбрать 3 ямки из 5