Дискретная математика

[RawonaM]

Ага. Я знаю два варианта ответа, если кто придумал один, продолжайте искать второй В принципе вариантов можно построить бесконечное количество.

[Alone Coder]

Сходу придумал два варианта:
1. 2n-1, 2(2n-1), 4(2n-1), ...
2. Строки таблицы, заполняемой с угла.
1 3 6 10 15 ... = ((n+1)²-(n+1))/2 - 0
2 5 9 14 ... = ((n+2)²-(n+2))/2 - 1
4 8 13 ... = ((n+3)²-(n+3))/2 - 2
7 12 ... = ((n+4)²-(n+4))/2 - 3
11 ... = ((n+5)²-(n+5))/2 - 4
...

[Alone Coder]

3. Сумма цифр равна 1, 2, 3, 4, ... (разные системы счисления дают разное разбиение)

[Alone Coder]

4. Наименьший простой множитель равен m-му простому числу (где m - номер множества).

[Alone Coder]

5. Имеет m простых множителей.

[RawonaM]

Вопрос: дана таблица отношения, как визуально определить, является ли релация транзитивной?
Уже долго пытаюсь построить алгоритм в голове, получается запутанно.

Симметричность/антисимметричность, рефлексивность — это легко видно визуально и легко дополняется. А вот с транзитивностью непонятно.

[RawonaM]

Как быстро построить в голове R²?

[arseniiv]

Визуально транзитивность определить, наверно, трудно. Но есть алгоритм построения транзитивного замыкания, который можно провести над матрицей отношения, и если в результате получится то же отношение — оно транзитивно. Алгоритм имени двух забыл кого.

[Квас]

Как быстро построить в голове R²?

Возможно ли это? «Знакомые знакомых»?

[Квас]

2. Строки таблицы, заполняемой с угла.

И ещё можно по-разному заполнять: прямоугольниками разной формы или другими фигурами.

[RawonaM]

У нас в книге quasi-order названо транзитивное и антирефлексивное отношение, а на педии

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.

... The name quasi-order is also common for preorders.

Чем это можно объяснить?..

Вопрос: матрица частично упорядоченного отношения всегда может принять треугольный вид?

[RawonaM]

http://books.google.com/books?id=TSmQYJplg0cC

Тут даны определения отношений, судя по этому у нас в книге имелось в виду pseudo-order, но на педии опять же pseudo-order определен с еще одним условием:
(wiki/en) Pseudo-order

Запутался вообще.

[Квас]

У нас в книге quasi-order названо транзитивное и антирефлексивное отношение, а на педии

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.

... The name quasi-order is also common for preorders.

Чем это можно объяснить?..

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

Вопрос: матрица частично упорядоченного отношения всегда может принять треугольный вид?

Простейшие примеры вроде подтверждают. Может, по индукции? Есть конечное множество X с отношением частичного порядка. Выберем некоторый максимальный элемент a (очевидно, существует) и занумеруем его 1. По предположению индукции множество X\{a} можно занумеровать так, что i ≺ j ⇒ i ≤ j (элементы отождествляю с номерами). Получаем нумерацию, для которой матрицы диагональна.

[RawonaM]

Существенной разницы нет

В точности формулировок и терминов нет разницы??!! 

Там ошибка в определении же, похоже.

[RawonaM]

Вопрос: матрица частично упорядоченного отношения всегда может принять треугольный вид?

Простейшие примеры вроде подтверждают. Может, по индукции? Есть конечное множество X с отношением частичного порядка. Выберем некоторый максимальный элемент a (очевидно, существует) и занумеруем его 1. По предположению индукции множество X\{a} можно занумеровать так, что i ≺ j ⇒ i ≤ j (элементы отождествляю с номерами). Получаем нумерацию, для которой матрицы диагональна.

Это я вывел методом рисования на бумаге многих отношений. Просто хотелось понять, вот я дошел до этого свойства

[Квас]

Это я вывел методом рисования на бумаге многих отношений. Просто хотелось понять, вот я дошел до этого свойства

Это настоящий математический подход!

В точности формулировок и терминов нет разницы??!! 

Комильфо считать отношения порядка рефлексивными. Но если автор в определении пишет «антирефлексивный», остаётся только развести руками и читать дальше. Как Кэррол сказал: «If I find an author saying, at the beginning of his book. "Let it be understood that by the word 'black' I shall always mean 'white', and that by the word 'white' I shall always mean 'black', " I meekly accept his ruling, however injudicious I may think it.»

Ошибка в определение могла вкрасться.

В виноградовской энциклопедии насчёт псевдопорядка ничего не нашёл. Предпорядком или квазипорядком у него названо рефлексивное и транзитивное отношение.

[RawonaM]

Это я вывел методом рисования на бумаге многих отношений. Просто хотелось понять, вот я дошел до этого свойства

Это настоящий математический подход!

По-моему не очень Я еще вот что вывел: если есть наименьший элемент, то это первая строка в матрице и она будет вся заполнена. Если она не вся заполнена, нет наименьшего. Точно так же если есть наибольший элемент, то весь последний столбец заполнен. Я правда в этом еще не очень уверен. С минимальными и максимальными еще не понял.

Предпорядком или квазипорядком у него названо рефлексивное и транзитивное отношение.

Ну вот, а у нас почему-то антирефлексивное и транзитивное. Ошибка видимо. И не могу на форум курса написать...

[RawonaM]

Ну полностью упорядоченное это когда весь треугольник заполнен, видимо.

[RawonaM]

Я задавал этот вопрос выше, вот нашел ответ:

The aleph null symbol was conceived by Georg Cantor (1845-1918) around 1893, and became widely known after "Beiträge zur Begründung der transfiniten Mengenlehre"  [Contributions to the Foundation of Transfinite Set Theory] saw the light in Mathematische Annalen, Band XLVI [vol. 46], B. G. Teubner, Leipzig, 1895.

On page 492 of this prestigious journal we find the paragraph Die kleinste transfinite Cardinalzahl Alef-null [The minimum transfinite cardinal number Aleph null], and the following:

    ...wir nennen die ihr zukommende Cardinalzahl, in Zeichen, *Alef-null* ... [We call the cardinal number related to that (set); in symbol, *Alef-null*]

In a letter dated April 30, 1895, Cantor wrote, "it seemed to me that for this purpose, other alphabets were [already] over-used" (translation by Martin Davis).

In Georg Cantor, Dauben (page 179) says that Cantor did not want to use Roman or Greek alphabets, because they were already widely used, and "His new numbers deserved something unique. ... Not wishing to invent a new symbol himself, he chose the aleph, the first letter of the Hebrew alphabet...the aleph could be taken to represent new beginnings...." Avinoam Mann points out that aleph is also the first letter of the Hebrew word "Einsof," which means infinity and that the Kabbalists use "einsof" for the Godhead.

(wiki/he) אלף_אפס

ב тоже используется.

[RawonaM]

Интересная задачка: K_n — количество вариантов разбиений множества {1,2,3...n} так, что в каждой группе будет не более двух элементов. Например для {1,2,3,4,5,6} возможный вариант {{1},{2,3},{4},{5,6}}.

Найти рекурсивую формулу для K_n.

Я ниасилил То есть может быть если бы я на нее еще два часа убил, осилил бы, но времени жалко.

[RawonaM]

Никто не хочет попытаться?

Вот еще классная задача (решение я знаю, просто кому интересно):

Дано множество А из 100 чисел. Докажите, что есть непустое подмножество, чья сумма членов делится на 100.

[Квас]

Интересная задачка: K_n — количество вариантов разбиений множества {1,2,3...n} так, что в каждой группе будет не более двух элементов. Например для {1,2,3,4,5,6} возможный вариант {{1},{2,3},{4},{5,6}}.

Найти рекурсивую формулу для K_n.

Та-ак. Разбиения рассматриваемого типа назовём хорошими. Множество хороших разбиений множества {1,2,3...n} разбивается на два класса: 1) разбиения, содержащие {n}; 2) разбиения, не содержащие {n}.

Разбиения первого класса находятся в биективном соответствии с хорошими разбиениями множества {1,...n-1}, поэтому первый класс содержит K_n-1 разбиений.

Каждое из разбиений второго класса содержит единственное множество вида {n, k}, где k ≠ n. Следовательно, второй класс разбивается на n-1 подкласс в зависимости от k. Ясно, что каждый подкласс находится в биективном соответствии с множеством хороших разбиений множества {1,...,n-2}, поэтому число разбиений класса 2) равно (n-1)K_n-2.

Всего
K_n = K_n-1 + (n-1)K_n-2, n ≥ 3.
Для полного счастья: K₁=1, K₂=2.

[RawonaM]

Прикольно, спасибо Я несколько по-другому думал и мой путь уводил меня в дебри. Надеюсь таких сложных задач не будет...

[RawonaM]

Оказывается такие разбиения называются инволюциями: (wiki/en) Involution_(mathematics)

[RawonaM]

Там есть и рекуррентная формула, и прямая.