1.4 K-сочетания из n-элементов

Основы перечислительной комбиаторики

1.4 K-сочетания из n-элементов

модуль 1.4 шаг 3

В магазине продаются открытки 10 видов. Сколькими способами можно купить в нем восемь различных открыток?

Решение



1
2
3
4
5
6
7
8
9

 
def soch(n, k):
    if n == k:
        return 1
    if k == 1:
        return n
  
    return soch(n-1, k-1) + soch(n-1, k)
 
print(soch(10, 8))

или

мошность (по k из n) =мошность ( по (n-k) из n )

=> (по 8 из 10) = ( по 2 из 10 )

=> ( по 2 из 10 ) = (по 1 из 9 ) + (по 2 из 9) => 9 + (по 2 из 9) => 9 + (9!/ 7!*2!) или продолжаем пока k != n

=> (по 1 из 9 ) + (по 1 из 8) + (по 1 из 7 ) + (по 1 из 6 ) + (по 1 из 5 ) + (по 1 из 4 ) + (по 1 из 3 ) + (по 1 из 2 ) + (по 1 из 1 )

=> 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 +1 = 45

Ответ

45

модуль 1.4 шаг 4

Сколькими способами можно расставить 15 одинаковых шашек на доске размерами 9×9?

Решение



1
2
3
4
5
6
7
8

 
def fact(n):
    if n==0:
        return 1
    return fact(n-1)*n
print(fact(0))
def choose(n,k):
    return fact(n)/(fact(k)*fact(n-k))
print(choose(81,15))

Ответ

8144022047817960

модуль 1.4 шаг 5

Нужно сгенерировать все возможные k-сочетания из n элементов.

Формат входных данных: Два числа k и n через пробел. Для них гарантированно выполняется условие: \(0\leqslant{ k}\leqslant{n}\).

Формат выходных данных: Необходимое число строк, в каждой из которых содержится k чисел из диапазона от 0 до n-1 включительно, разделенных пробелом.

Sample Input 1:



1

 
2 3

Sample Output 1:



1
2
3

 
0 1
0 2
1 2

Sample Input 2:



1

 
1 1

Sample Output 2:



1

 
0

Решение



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 
from itertools import *
input_text = input().split()
k = int(input_text[0])
n = int(input_text[1])
if n>=k:
    if k==1 and n==1:
        print(0)
    else:
        se = list()
        for t in range(0, n):
            se.append(t)
 
        res = list(combinations(se, k))

        for i in range(0, len(res)):
            rr = list(res[i])
  
            print(*rr, sep=' ')


 


1
2
3

 
k, n = STDIN.readline.split.map(&:to_i)
result = (0..n-1).to_a.combination(k).to_a
result.each { |line| puts line.join(' ') }

Ответ

программа python

модуль 1.4 шаг 11

Предлагаем вам самим поупражняться в комбинаторных доказательствах.

Докажите комбинаторно тождество Вандермонда:

\[\binom{n+m}{k}=\sum\limits_{i=0}^{k}\binom{n}{i}\cdot\binom{m}{k-i}.\]

Решение

Ответ

модуль 1.4 шаг 14

В магазине продаются открытки 10 видов. Сколькими способами можно купить в нем 8 открыток?

Решение



1
2
3
4
5
6
7
8
9

 
def soch(n, k):
    if n == k:
        return 1
    if k == 1:
        return n
  
    return soch(n-1, k-1) + soch(n-1, k)
 
print(soch(10+8-1, 8))

Ответ 24310

модуль 1.4 шаг 15

Сколько существует шестизначных чисел, сумма цифр которых не превосходит 47?

Решение



1
2
3
4
5
6
7
8
9
10
11
12

 
a=[]
b=0
c=0
for i in range(100000, 1000000):
    a+=str(i)
    for j in range(len(a)):
        b+=int(a[j])
    if(b<=47):
        c+=1
    b=0
    a=[]
print(c)

Ответ

899076

модуль 1.4 шаг 16

Сколько существует бинарных (т.е. состоящих из цифр 0 и 1 ) строк длины n, содержащих k единиц, в которых никакие две единицы не стоят рядом?

Решите задачу в общем случае, а в качестве ответа введите количество таких строк для n = 42 и k = 7.Сколько существует шестизначных чисел, сумма цифр которых не превосходит 47?

Решение

1 решение.

Так как между единицами должен быть ноль, то можно рассматривать слова в алфавите {‘10’, ‘0’}. Эти слова только один случай не рассматривают: когда слово кончается на единицу; рассмотрим его отдельно.

Пусть \(x\) — количество нулей в слове. У нас слово длины nn, а ‘10’ занимает два места.

Получается \(2k+x=>x=n-2k\)

Получается длина в новом алфавите будет \(k+n-2k=n-k\).

Посчитаем количество слов такой длины \(C_{n-k}^k\).

Посчитаем количество слов, когда в конце стоит ‘1’. Т.е мы будет рассматривать слова, где нулей столько же, но букв ‘10’ на одну меньше

Получается \(2k-2+x=n-1=>x=n+1-2k\)

Длина \((k-1)+(n+1-2k)=n-k\).

Посчитаем количество слов длины такой \(C_{n-k}^{k-1}\)

Суммарно \(C_{n-k}^k+C_{n-k}^{k-1}=C_{n-k+1}^{k}\).

\(C_{42-7+1}^{7}=8347680\).

2 решение.

Возьмём все единцы и расставим между ними нули. Всего единиц k, значит, чтобы расставить между ними нули, нужно k-1 ноль.

Остаёться n-(k-1) неиспользованных нулей.

Их можно положить между единицами, причём ещё в начало и конец. Т.е k+1 место. Причём в одно место можно положить несколько нулей

\[\bar{C}_{k+1}^{2k+1}=C_{k+1+n-2k+1-1}^{n-2k+1}=C_{n-k+1}^{n-k+1-(n-2k+1)}=C_{n-k+1}^{k}\]

Ответ

8347680