6.1 Основные комбинаторные принципы
Решение многих комбинаторных задач основывается на двух фундаментальных правилах, называемых правилами суммы и произведения. Правило суммы . Если X 1 и X 2 – непересекающиеся конечные множества, содержащие n 1 и n 2 элементов соответственно, то объединение X 1 U X 2
содержит n 1 + n 2 элементов.
Сформулированное правило можно распространить на случай произвольного числа слагаемых: если множества X 1 ,X 2 ,…,X k образуют разбиение множества X , то n = n 1 + n 2 +…+ n k , где n=|X| – число элементов множества X , а n i =|X i | – число элементов (мощность) множества X i , i = 1, 2,…, k . Напомним, что разбиением множества X называется набор его непересекающихся подмножеств, объединение которых дает все исходное множество X .
Правило суммы можно приспособить и для подсчета числа элементов объединения двух множеств с непустым пересечением:
В самом деле, множества X 1 \X 2 и X 1 ∩X 2 образуют разбиение множества X 1 , поэтому
Кроме того, множества X 1 \X 2 , X 2 \X 1 и X 1 ∩X 2 образуют разбиение множества X 1 U X 2 , так что
, приходим к утверждению (1).
Пример . Найдем количество положительных целых чисел, меньше или раных 1000, которые делятся на 3 или на 5.
Количество элементов множества S положительных целых чисел,
меньших 1000, которые делятся на 3, равно 1000 3 или 333. Количество элементов множества Т положительных целых чисел, меньших 1000, которые
делятся на 5, равно 1000 5 или 200. Элементами множества S∩T являются целые числа, меньшие 1000, которые делятся на 5 и на 3, и поэтому делятся
на 15. Следовательно,
= 333 + 200 − 66 = 467
Пример . Предположим, что на курсе из 100 студентов 60 человек изучают математику, 75 — историю, а 45 человек — и то, и другое.
а) Сколько студентов изучают математику или историю?
Пусть универсум U — группа из 100 студентов, М — множество студентов, изучающих математику, Н — множество студентов, изучающих историю. Тогда количество студентов, изучающих математику или историю,
б) Сколько студентов не изучают ни математику, ни историю?
Количество студентов, не изучающих ни математику, ни историю,
Существует альтернативный метод решения приведенных выше задачи, который является более информативным. Рассмотрим его на следующем примере.
Пример . Предположим, что из 100 студентов курса 50 изучают химию, 53
— математику, 42 — физику, 15 — химию и физику, 20 занимаются физикой
и математикой, 25 — математикой и химией и 5 студентов изучают все три предмета.
а) Сколько студентов изучают хотя бы один из трех перечисленных предметов?
б) Сколько студентов не изучают ни один из трех перечисленных предметов? в) Сколько студентов изучают только математику?
г) Сколько студентов изучают физику или химию, но не изучают математику?
д) Сколько студентов не изучают ни математику, ни химию?
Поскольку 5 человек изучают все три предмета, а 15 человек — химию
и физику, остаются 10 человек, изучающих химию и физику, но не изучающих математику. Аналогично, 25 — 5 = 20 человек занимаются математикой и химией, но не физикой, и 20 — 5 = 15 человек изучают математику и физику, но не изучают химию. Данную ситуацию изображает диаграмма Эйлера, приведенная на следующем рисунке слева
Поскольку 50 студентов изучают химию и 35 из них уже учтены, то оставшиеся 15 изучают только химию. Аналогично, 53 студента занимаются математикой и 40 из них уже учтены. Поэтому 13 человек изучают только математику. Наконец, 42 студента изучают физику, и 30 из них уже учтены, поэтому 12 человек изучают только физику.
а) Суммируя количество людей, принадлежащих семи непересекающимся подмножествам, получаем 90 тех, кто изучает хотя бы один из трех предметов.
б) Поскольку 90 из 100 студентов изучают хотя бы один предмет, то 10090 = 10 человек не изучают ни один из этих трех предметов.
в) Из диаграммы Эйлера следует, что 13 человек изучают только математику. г) Тридцать семь студентов занимаются химией или физикой, но не изучают математику.
д) Из диаграммы Эйлера, изображенной на предыдущем рисунке справа, следует, что 75 человек изучают математику или физику. Поэтому 100 — 75 = 25 студентов не изучают ни математику, ни физику. □
Пример . Сколько имеется путей из вершины a в вершину b в сети, показанной на следующем рисунке (движение возможно только вправо или вверх)?
Обозначим множество всех путей из a в b через L ab и разобьем его на два непересекающихся подмножества:
L acb – пути, проходящие через вершину c; L adb – пути, проходящие через вершину d.
Имеем L ab = L acb + L adb . Очевидно, что интересующее нас количество
путей зависит только от размеров решетки, поэтому обозначим через l m,n количество путей в сети, имеющей m горизонтальных и n вертикальных
вершин. Тогда последнее равенство можно записать в виде l 4,5
l m , n = l m − 1, n + l m , n − 1 .
количество путей на рисунке:
+ l 4,3 ) = l 2,5 + 3 l 3,4
+ l 4,4 = ( l 2,5 + l 3,4 ) + ( l 3,4
+ l 2,4 ) + 3 ( l 2,4 + l 3,3 ) = l 1,5
= l 1,5 + 4 ( l 1,4 + l 2,3 ) + 3 ( l 2,3 + l 3,2 ) = l 1,5
+ 4 l 1,4 + 10 l 2,3
Другое фундаментальное правило дает, доказанная ранее Теорема . Мощность декартового произведения двух конечных множеств равна произведению их мощностей A × B = A B .
Обобщение ее на декартово произведение n множеств называется правилом произведения . Рассмотрим упорядоченные наборы ( a 1 , a 2 ,…, a k ) заданной длины k . Предположим, что элемент a 1 из множества X 1 может быть выбран n 1 способами, т.е. X 1 = n 1 . При уже выбранном элементе a 1 ,
элемент a 2 из множества X 2 может быть выбран n 2 способами, т.е. X 2 = n 2 . При фиксированных a 1 и a 2 элемент a 3 из множества X 3 может быть выбран
n 3 способами, т.е.
= n 3 и т.д. При фиксированных a 1 , a 2 ,…, a k–1 элемент
a k из множества
может быть выбран n k способами. Тогда число
различных упорядоченных наборов равно произведению n 1 × n 2 × . × n k . Это означает, что
Это правило часто называют комбинаторным принципом умножения. Доказательство. Будем доказывать теорему методом математической индукции. Базис индукции . Пусть n=2 . В этом случае все элементы
множества Х 1 х Х 2 , т. е. упорядоченные пары ( х 1 , х 2 ), можно расположить в виде прямоугольной таблицы со строками — элементами Х 1 и столбцами — элементами Х 2 . В этой таблице, очевидно, будет |X 1 | x |X 2 | элементов.
Индуктивный переход . Предположим справедливость утверждения теоремы для n . Покажем, что для n+1 оно будет тоже справедливо. В самом деле, добавляя еще одно множество в декартово произведение, видим, что
В случае, когда X 1 =X 2 =…=X k эта формула принимает вид X k = X k . В этом
случае множество X называется алфавитом, его элементы – буквами, а элементы декартова произведения X k , т.е. упорядоченные пары из k букв ( x 1 , x 2 ,…, x k ) называют словами в алфавите X . Число k называется длиной слова.
Пусть |X|=m , тогда формулу X k = X k можно сформулировать
число слов длины k в алфавите из m букв равно m k .
Пример . Битовая строка – это строка, состоящая из элементов множества <0, 1>, т.е. каждый из элементов имеет значение 0 или 1. Сколько существует битовых строк длины 5? Сколько существует битовых строк длины k ?
Поскольку каждый символ строки может иметь значение 1 или 0, то существует два варианта выбора для каждой позиции. Следовательно, существует 2 x 2 x 2 x 2 x 2 = 2 5 битовых строк длины 5. По аналогичным соображениям, имеется 2 k битовых строк длины k .
Пример . Используя правило произведения и правило суммы, найдем число различных трехзначных чисел, не содержащих одинаковых цифр, и число различных трехзначных чисел, содержащих хотя бы две одинаковые цифры Пусть a 1 , a 2 , a 3 – цифры трехзначного числа. Первую цифру a 1 можно выбрать девятью способами (в качестве нее можно взять любую цифру, кроме нуля); при фиксированной первой цифре вторую цифру a 2 можно выбрать также девятью способами (в качестве нее можно взять любую цифру, кроме a 1 ); наконец, при фиксированных первой и второй цифрах третью цифру можно выбрать восемью способами. По правилу произведения число трехзначных чисел, не содержащих одинаковых цифр, равно
Всего имеется 900 различных трехзначных чисел (от 100 до 999). Каждое из них либо содержит две одинаковые цифры, либо нет. Следовательно, имеется 900 – 648 = 252 различных трехзначных числа, содержащих хотя бы две одинаковые цифры.
Третьим важным принципом является правило взаимно однозначного соответствия (правило биекции или правило равенства): множества A и B имеют одинаковое количество элементов | A | = | B | тогда и только тогда, когда между ними можно установить взаимно однозначное соответствие.
В качестве примера применения этого принципа подсчитаем количество всевозможных подмножеств множества M, состоящего из n элементов. Так это количество не зависит от природы элементов множества М, возьмем M=<1,2,…,n>. Произвольному подмножеству A M поставим в соответствие двоичное слово α 1 α 2 . α n по следующему правилу:
α i = 0 , еслиi A
Это соответствие взаимно однозначное. Отсюда число всех подмножеств n – элементного множества равно числу двоичных слов длины n , т.е. равно 2 n . Пример . Сколькими способами можно разложить 10 монет разной стоимости по двум карманам?
Формализуя задачу, отметим, что два кармана дадут два подмножества 10 – элементного множества; объединение множеств монет, лежащих в этих двух карманах, дает все множество; пересечение этих множеств пусто. Это значит, что те монеты, которые лежат в одном кармане, полностью определяют содержимое второго кармана.
Используя правило биекции, можем сказать, что требуемых способов столько, сколько подмножеств в 10 – элементном множестве. Т.о. можем написать ответ: 2 10 =1024.
Напомним также принцип Дирихле, который мы формулировали следующим образом. Пусть f : А —> В — функция, причем как A , так и В — конечные множества. Предположим, что А состоит из n элементов: a 1 , а 2 ,… a n . Принцип Дирихле гласит, что если |А|>|В| , то по крайней мере одно значение f встретится более одного раза. Проще говоря, найдется пара элементов a i ≠ a j , для которых f ( a i ) = f ( a j ) .
Пример . Показать, что если в прямоугольнике со сторонами 6 и 8 сантиметров помещены пять точек, то существуют две точки, расстояние между которыми не более 5 сантиметров.
Разделим исходный прямоугольник на четыре прямоугольника, размером 3 на 4 сантиметра каждый. Поскольку пять точек должны находиться либо внутри, либо на границах четырех прямоугольников, то хотя бы две точки должны быть либо внутри, либо на границе одного и того же прямоугольника размера 3 х 4. Но любые такие точки находятся на расстоянии не более 5 сантиметров.
myubi.tv
Сколько битовых строк длины 10 содержат равное количество нулей и единиц?
Please enable JavaScript
(d) Равное количество нулей и единиц в строке длины 10 означает, что существует пять нулей и пять единиц.
Сколько существует 10-значных битовых строк?
Первая цифра может быть любой из 5 цифр, а две другие могут быть любой из 10 цифр, поэтому ответ будет 5 · 10 · 10 = 500.
Сколько существует битовых строк длины 4?
Сколько возможны битовых строк длины 4, содержащих 2 единицы и 2 нуля? Объяснение: строки <0011, 0110, 1001, 1100, 1010 и 0101>. 4. Если битовая строка содержит только <0, 1>, то при длине 5 в ней не более 2 единиц.
Сколько двоичных строк длины 10 содержат ровно 4 нуля?
= (10 × 9 × 8 × 7)/4! = 210. б) не более четырех единиц? Мы складываем количество битовых строк длины 10, содержащих ноль единиц, одну единицу, две единицы, три единицы и четыре единицы.
Сколько 10-битных строк содержат 6 или более единиц?
Сколько битовых строк длины 10 начинаются и заканчиваются на 1?
Сколько битовых строк длины n содержат ровно r единиц?
Битовая строка длины n, содержащая ровно r единиц, будет иметь ровно n−r 0.
Сколько битовых строк содержат ровно пять нулей?
Сколько битовых строк содержит ровно пять нулей и четырнадцать единиц, если за каждым 0 должны сразу следовать две единицы? В чем мне нужна помощь: на этот вопрос ответ 126-битные строки.
Сколько битовых строк длины 10 содержат не менее трех единиц и не менее трех нулей?
Сколько существует битовых строк длины 7?
в) Сколько строк битов длины семь содержат три последовательных нуля? Пусть an обозначает количество таких строк длины n. 0,0,0,1,3,8,20,47,107,238,520,1121,2391,…. Отсюда a7 = 47-битные строки длиной семь которые содержат три последовательных 0.
Сколько битовых строк длины четыре не имеют двух последовательных единиц, объясненных с помощью соответствующей древовидной диаграммы?
Сколько битовых строк длины четыре не содержат двух последовательных единиц? Однако правильное решение оказывается 8.
Сколько двоичных строк длины n, не начинающихся с 10, возможно?
Итак, если вы суммируете все это, вы получите 512 строк что имеет смысл, потому что 210=1024..
Сколько 19-битных строк содержат не менее 4 нулей?
(C) аналогичен (b), но «не менее четырех» означает четыре или более. Таким образом, вы хотите вычислить количество битовых строк, которые имеют четыре, пять, шесть,…, до 10 единиц, а затем сложить их вместе (или есть более простой способ сделать это, если мы понимаем, что не более трех противоположно как минимум четырем?)
Сколько 8-битных двоичных строк имеют ровно 3 нуля?
Сколько 8-битных строк содержит три нуля подряд и пять единиц? Ответ = 6!/5!
Сколько 8-битных строк имеют вес 5, т.е. содержат ровно пять единиц и начинаются с подстроки 101?
Есть (53)=10 восемь-битовые строки веса пять, начинающиеся со 101 (ваш A)
Сколько существует строк из строчных букв длины 4 или меньше?
475 254 строки (исключая пустую строку)
Что такое 8-битная строка?
Байт представляет собой строку из 8 бит.
Сколько существует строк длины 10 букв a B и C, содержащих ровно 4 as?
Таким образом, наш окончательный ответ: 1+8+40+160=209 возможных строк.
Сколько битовых строк длины 8 либо начинаются с 01, либо заканчиваются на 01?
4 ответа. Мы интерпретируем начало с 1 или окончание на 01 как означающее, что битовые строки, удовлетворяющие обоим условиям, подходят. Судя по вашему правильному анализу, есть 27-битные строки которые начинаются с 1.
Сколько битовых строк длины восемь либо начинаются с битов 11, либо заканчиваются битами 00?
Правильный ответ: «Вариант 3“.
Сколько существует различных битовых строк длины 8, содержащих строку 0000?
См. также викторину о том, что такое географическая информационная система (ГИС)
Сколько существует троичных длин строк?
Ответ и объяснение: i) Каждая цифра в троичной строке может быть выбрана тремя способами, поэтому 315=14,348,907 3 15 = 14 , 348 , 907 троичных строк длины 15.
Сколько существует битовых строк длины 14, содержащих ровно пять нулей?
Сколько битовых строк содержит ровно пять нулей и 14 единиц, если за каждым 0 должны сразу следовать две единицы? Поскольку данная битовая строка содержит пять нулей и четырнадцать единиц, требуемая длина битовой строки равна 19.
Сколько строк можно составить, упорядочив буквы продавцов, если никакие две буквы s не идут подряд?
возможные строки SALESPERSONS без последовательных букв S. Таким образом, есть 2 540 160 строк ПРОДАВЦОВ без последовательных S..
Сколько существует различных битовых строк длины семь, оканчивающихся на 10?
Я думаю, что для строк, начинающихся с 10, у нас было бы 7−2=5 бит на выбор, поэтому 32 возможных битовых строки длины 7, которая начинается с 10.
Сколько битовых строк длины 12 содержат равное количество нулей и единиц?
Шаг 5. (d) Равное количество нулей и единиц в строке длины 12 означает, что существует шесть нулей и шесть единиц.
Сколько существует перестановок буквы Abcdefgh?
Следовательно, есть 40320 перестановка буквами «a b c d e f g h».
Сколько можно составить слов длины 8, содержащих ровно одну гласную?
Ответ 217×8×(51). Это потому, что мы можем выбрать одну гласную (51) способами. Остальные 7 можно заполнить 21 буквой (согласной) с повторением.
Сколько существует битовых строк длины 6 или меньше?
Посмотрите также, как части клетки работают вместе, чтобы клетка функционировала должным образом.
Сколько существует различных битовых строк длины n?
Поскольку бит состоит либо из числа 1, либо из 0, существует только два способа заполнения первого слота или 2n способов. Поскольку битов восемь, ответ будет 28 или 256.
Сколько битовых строк длины n не имеют одинаковых последовательных битов?
Есть 2n битовых строк длины н. Количество битовых строк с NO 2 последовательными нулями равно = 2n− (количество битовых строк с последовательными нулями)
Сколько существует 10-значных строк из 0 и 1, не содержащих последовательных нулей?
Ответ: 10-значные строки из 0 и 1, которые не содержат ни одного последовательного 0, являются 144.
Какое возможное количество двоичных кодов можно сгенерировать, используя N битов?
Максимальное десятичное значение для N бит.
| Количество бит | Максимальное количество состояний |
|---|---|
| 32 | 4,294,967,296 (4 г) |
Сколько существует битовых строк длины 9?
Сколько битовых строк длины 9 содержат ровно три единицы? 10∗10∗10∗96=531441000 Но тогда эти первые 1 не обязательно должны быть первыми 3 цифрами. Они могут быть и в другом месте строки цифр.
Как найти количество строк длины N,что не содержат S как подстроку?
Дано строку что может содержать только буквы A,B,C, тогда количество всех строк длины N из етих букв будет 3^N,тогда ответ на задачу : 3^N — (количество строк что имеют подстрочку S). Как эффективно посчитать количество строк что не содержат подстроки S? А да забыл сказать S содержит только буквы A,B.
Нам не подходит одна строка AB, тогда количество 3^2 — 1 = 8.Так же написал brute force алгоритм на котором можно проверить тестики:
Пусть PS[] — префиксы строки S длиной от 1 до lenS-1
F[k][j] — количество хороших строк длиной k , оканчивающихся на PS[j] (в том числе F[k][0] , не оканчивающиеся на префиксы)
8.10. Битовые строки
Битовые строки представляют собой последовательности из 1 и 0. Их можно использовать для хранения или отображения битовых масок. В SQL есть два битовых типа: bit(n) и bit varying(n), где n — положительное целое число.
Длина значения типа bit должна в точности равняться n; при попытке сохранить данные длиннее или короче произойдёт ошибка. Данные типа bit varying могут иметь переменную длину, но не превышающую n; строки большей длины не будут приняты. Запись bit без указания длины равнозначна записи bit(1), тогда как bit varying без указания длины подразумевает строку неограниченной длины.
Замечание: При попытке привести значение битовой строки к типу bit(n), оно будет усечено или дополнено нулями справа до длины ровно n бит, ошибки при этом не будет. Подобным образом, если явно привести значение битовой строки к типу bit varying(n), она будет усечена справа, если её длина превышает n бит.
Синтаксис констант битовых строк описан в Подразделе 4.1.2.5, а все доступные битовые операторы и функции перечислены в Разделе 9.6.
Пример 8-3. Использование битовых строк
Для хранения битовой строки используется по 1 байту для каждой группы из 8 бит, плюс 5 или 8 байт дополнительно в зависимости от длины строки (но длинные строки могут быть сжаты или вынесены отдельно, как описано в Разделе 8.3 применительно к символьным строкам).