Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Апрель 2010   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Дискретная математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный хостинг на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Профессор
Рейтинг: 5138
∙ повысить рейтинг » 		Гаряка Асмик
Статус: Специалист
Рейтинг: 3213
∙ повысить рейтинг » 		_Ayl_
Статус: Практикант
Рейтинг: 1860
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Дискретная математика

Номер выпуска:183
Дата выхода:20.04.2010, 16:30
Администратор рассылки:Alexey G. Gladenyuk, Управляющий
Подписчиков / экспертов:93 / 49
Вопросов / ответов:2 / 5

Вопрос № 177853: ув эксперты вот пару задач: 1) доказать равенство ∑k=0n∑r=0n-kCknCrn-k =3n 2)найти сумму ∑k=0n(k2 Вопрос № 177854: 1)Сколько различных словарей надо издать,чтобы можно было переводить с любого из данных n языков на любой другой язык этого же множества? 2)Сколькими способами можно раставить белые фигуры:2 коня, 2 слона,2 ладьи, ферзя и короля на первой линии ш...

Вопрос № 177853:

ув эксперты вот пару задач:
1) доказать равенство ∑k=0n∑r=0n-kCknCrn-k =3n
2)найти сумму ∑k=0n(k2-1+1/(k+1))Cnk

Отправлен: 15.04.2010, 16:07
Вопрос задал: Кусмарцев Андрей Валерьевич, 3-й класс
Всего ответов: 2
Страница вопроса »

Отвечает coremaster1, 8-й класс :
Здравствуйте, Кусмарцев Андрей Валерьевич.
Решение задачи 2) на рисунке:

Ответ отправил: coremaster1, 8-й класс
Ответ отправлен: 15.04.2010, 17:07
Номер ответа: 260824

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 260824 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Отвечает Лиджи-Гаряев Владимир, Студент :
    Здравствуйте, Кусмарцев Андрей Валерьевич.

    ∑k=0n∑r=0n-kCknCrn-k =3n

    По формуле бинома Ньютона
    3n=(2+1)n=∑k=0nCkn*2n-k*1k=∑k=0nCkn*2n-k (*)

    2n=(1+1)n=∑k=0nCkn (**)

    Т.к. Ckn - независит от к, то
    ∑k=0n∑r=0n-kCknCrn-k=∑k=0n(Ckn*∑r=0n-kCrn-k)=∑k=0n(Ckn*2n-k)=3n

    Ответ отправил: Лиджи-Гаряев Владимир, Студент
    Ответ отправлен: 19.04.2010, 17:40
    Номер ответа: 260915

    Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 260915 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Вопрос № 177854:

    1)Сколько различных словарей надо издать,чтобы можно было переводить с любого из данных n языков на любой другой язык этого же множества?
    2)Сколькими способами можно раставить белые фигуры:2 коня, 2 слона,2 ладьи, ферзя и короля на первой линии шахматной доски?
    3) Имеется n абонентов. Сколькими способами можно одновременн соединить три пары?

    Отправлен: 15.04.2010, 16:17
    Вопрос задал: Кусмарцев Андрей Валерьевич, 3-й класс
    Всего ответов: 3
    Страница вопроса »

    Отвечает F®ost, Младший модератор :
    Здравствуйте, Кусмарцев Андрей Валерьевич.
    Решение первой задачи:
    Аmn=m(m-1)(m-2)...(m-n+1)=m!/(m-n)!
    где n - количество всех языков, m - количество языков, участвующих в переводе: например, всего 5 языков, а перевод делается с одного на другой, т.е. n=5, m=2. Получается, что для А25=5!/(5-2)!=20 различных словарей.

    Решение второй задачи:
    Аn(m1, m2,... mk)=n!/(m1!×m2!×...mk!)
    где n - количество клеток шахматного поля, а m1,... mk - количество фигур, участвующих в расстановке.
    Отсюда А8(2,2,2)=8!/(2!×2!×2!)=5040 различных способов.



    -----
    От вопроса к ответу, от проблемы к решению

    Ответ отправил: F®ost, Младший модератор
    Ответ отправлен: 15.04.2010, 16:40
    Номер ответа: 260823
    Беларусь, Минск
    Тел.: 375292792018
    Организация: Минский Промтранспроект
    Адрес: ул. В.Хоружей, 13, г. Минск, Беларусь
    Адрес сайта: Минский Промтранспроект

    Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 260823 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Отвечает coremaster1, 8-й класс :
    Здравствуйте, Кусмарцев Андрей Валерьевич.
    Задача 1.
    В условии не сказано прямо, что возможен только непосредственный перевод.
    Если допустить промежуточные переводы, например с языка 1 на язык 2, с языка 2 на язык 3 и т.д., то достаточно n словарей.
    Если же промежуточные переводы запрещены, то каждый язык должен быть связан словарём со всеми остальными, и нужно n*(n - 1) словарей.

    Задача 3.
    Первую пару можно выбрать C(n, 2) способами (количество сочитаний из n по 2), вторую пару - C(n - 2, 2), третью - C(n - 4, 2).
    Остаётся учесть перестановки трёх пар и получаем ответ: C(n, 2)*C(n - 2, 2)*C(n - 4, 2)/3! = 1/48 * n!/(n - 6)!

    Ответ отправил: coremaster1, 8-й класс
    Ответ отправлен: 15.04.2010, 19:46
    Номер ответа: 260830

    Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 260830 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Отвечает Гордиенко Андрей Владимирович, Профессор :
    Здравствуйте, Кусмарцев Андрей Валерьевич.

    1. Рассмотрим первую задачу. Представим себе, что не налагается никаких ограничений на количество языков множества, на которые осуществляется перевод (рассматриваем многоязычные словари). Тогда для того, чтобы перевести с одного языка (будем называть такой язык первым) на любой другой язык множества (будем называть такие языки вторыми) необходим один словарь. Например, если множество состоит из русского, белорусского, украинского и польского языков, то для того, чтобы выполнить перевод с русского языка на любой из других языков, достаточно одного словаря. Таким словарем может быть русско-белорусско-украинско-польский словарь. Порядок следования вторых языков значения не имеет. Для того, чтобы перевести с белорусского языка на любой из других языков, тоже достаточно одного языка. И т. д. Поскольку в качестве первого может выступать любой из n языков множества, достаточно n словарей. Нетрудно убедиться, что это количество сл оварей является минимально необходимым для организации перевода.

    Если речь идет о двуязычных словарях, то для перевода с одного языка на любой другой из множества n языков необходимо два словаря, а для охвата всей совокупности возможных пар языков необходимо найти количество всех упорядоченных пар из множества, состоящего их n элементов. Т. е. общее количество потребных словарей равно An2 = n!/(n – 2)! = n(n – 1).

    Определим, в каком случае количество двуязычных словарей не меньше количества многоязычных словарей:
    n ≤ n(n – 1), n ≤ n2 – n, n2 ≥ 2n, n ≥ 2.
    Поскольку по смыслу задачи условие n ≥ 2 выполняется всегда, то утверждение, что минимальное количество словарей равно n, обосновано, о чем говорилось выше.

    2. Рассмотрим вторую задачу. Напомним, что один слон может ходить только по белым полям, второй – только по черным. Возможны два варианта:
    1) на расположение слонов не накладывается никаких ограничений, т. е. на доске может быть два однопольных слона. Тогда введем обозначения 1 – король, 2 – ферзь, 3 – ладья, 4 – слон, 5 – конь. Если исходить из начальной расстановки фигур на доске, то ее можно закодировать следующим восьмизначным числом 35412453 и искать количество N способов расстановки фигур по известной формуле для числа разбиений множества, состоящего из n = 8 элементов, на подмножества из n1 = 1 (один король), n2 = 1 (один ферзь), n3 = 2 (две ладьи), n4 = 2 (два слона), n5 = 2 (два коня) элементов:
    N = 8!/(1!1!2!2!2!) = 5040;
    2) на расположение слонов накладывается естественное ограничение, состоящее в том, что слоны не могут занимать поля одного цвета. Тогда искомое количество способов оказывается в 7/4 раза меньшим и равным 5040 ∙ 4/7 = 2880.

    3. Третья задача сводится к нахождению числа N разбиений n – угольника на различные треугольники, или к нахождению ч исла сочетаний из n элементов по 3:
    N = Cn3 = n!/(3!(n – 3)!).

    С уважением.
    -----
    Пусть говорят дела

    Ответ отправил: Гордиенко Андрей Владимирович, Профессор
    Ответ отправлен: 15.04.2010, 21:09
    Номер ответа: 260836

    Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 260836 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2010, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2010.6.14 от 03.03.2010
    В избранное