Розв'язник вправ по дискретній математиці/Комбінаторика

Розв'язник вправ по дискретній математиці. Комбінаторика

Задача 1

а) Яких чисел більше серед цілих чисел першої тисячі (включаючи і 1000): в записі яких є одиниця, або інших? б) Яких семизначних чисел більше: тих, в запису яких є одиниця, або інших?

Розв'язання.  

а) Є $8^{3}=512$ тризначних чисел, що не містять 1 і 0. Це вже більше половини чисел першої тисячі.

Відповідь: більше чисел, в запису яких немає одиниці;

б) Підрахуємо кількість чисел, в запису яких немає одиниці. На першому місці може стояти кожна з 8 цифр (0 і не 1), на кожному з решти - будь-яка з 9 цифр, відмінних від 1. Всього отримуємо $8*9^{6}$ чисел, що становить менше половини від кількості 9 · 10^6 всіх семизначних чисел.

Відповідь: більше чисел, в запису яких є ​​одиниця.

Задача 2

Скількома способами 3 людини можуть розділити між собою 7 однакових яблук, один апельсин, одну сливу і один мандарин?

Розв'язання.  

Формула для розподілу k однакових речей серед n різних людей: F (k, n) = C (n-1, n + k-1);

C(2,9)=9!/(7!*2!)= 36;

"Поодинокі" фрукти можуть дістатися кожному з трьох, тоді: $36*3^{3}=972$ способів.

Відповідь: 972 способів;

Задача 3

• Розв'язати завдання з leetcode.com (Count Sorted Vowel Strings). Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Example 1:  

Input: n = 1

Output: 5

Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:  

Input: n = 2

Output: 15

Explanation: The 15 sorted strings that consist of vowels only are ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]. Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:  

Input: n = 10

Output: 1001

Задача 4

• Розв'язати завдання з leetcode.com (Pairs of Songs With Total Durations Divisible by 60). You are given a list of songs where the ith song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.

Example 1:  

Input: time = [30,20,150,100,40]

Output: 3

Explanation: Three pairs have a total duration divisible by 60:

(time[0] = 30, time[2] = 150): total duration 180

(time[1] = 20, time[3] = 100): total duration 120

(time[1] = 20, time[4] = 40): total duration 60

Example 2:  

Input: time = [60,60,60]

Output: 3

Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Example 3:  

Input: time = [418,204,77,278,239,457,284,263,372,279,476,416,360,18]

Output: 1

Explanation: (457 + 263) - only one pair

Задача 5

• Розв'язати завдання з leetcode.com (62. Unique Paths). There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Example 1:  

Input: m = 3, n = 2

Output: 3

Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down

Example 2:  

Input: m = 3, n = 7

Output: 28