2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Количество помеченных графов
Сообщение09.02.2016, 09:32 


29/10/14
31
Привет.

Задача следующая:Сколько всего помеченных графов на 6 вершинах, которые имеют четное число ребер?

Решаю так: Суммирую число графов с 2,4, 6, 8,10, 12, 14 ребрами (так как всего на 6 вершинах может быть 15 ребер) и плюс граф без ребер. Количество графов считаю через биноминальные коэффициенты - ${2 \choose 15}$ и тд.
Что я делаю не так?

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 09:48 
Заслуженный участник
Аватара пользователя


19/12/10
1546
VfuVfn в сообщении #1098054 писал(а):
Что я делаю не так?

Биномиальные коэффициенты не так записываете $\binom{15}2.$ :-)
Что вызывает сомнения? Ответ не сходится?

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 09:52 


29/10/14
31
whitefox в сообщении #1098055 писал(а):
VfuVfn в сообщении #1098054 писал(а):
Что я делаю не так?

Биномиальные коэффициенты не так записываете $\binom{15}2.$ :-)
Что вызывает сомнения? Ответ не сходится?

о точно)) Да ответ не сходится, получил 15929, может в арифметике косякнул.

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 10:01 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Обратили внимание, что $\binom{15}{14}=\binom{15}1?$

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 10:57 


29/10/14
31
Нет, но ведь в одном случае 14 ребер, а в другом 1...

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 11:00 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
VfuVfn в сообщении #1098068 писал(а):
Нет, но ведь в одном случае 14 ребер, а в другом 1...
А что, Ваши вычисления дают разные результаты?

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 11:04 


29/10/14
31
не пересчитывал, но смысл я потерял. я считаю количество графов в с 14 ребрами, а не с 1.

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 11:16 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
VfuVfn в сообщении #1098072 писал(а):
не пересчитывал
Напрасно.

VfuVfn в сообщении #1098072 писал(а):
но смысл я потерял
Это была Вам подсказка: как найти ответ, практически ничего не вычисляя. Вы же проделали кучу вычислений и получили неправильный ответ, потому что наврали в арифметике, что не удивительно, если считали вручную или на калькуляторе.

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 11:27 


29/10/14
31
О!Точно, можно проще считать.
я думал у меня ошибка в логике.
Всем спасибо.

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 12:02 
Заслуженный участник


10/01/16
2315
VfuVfn
А можно и не считать: дорисуем оставшиеся ребра, их нечетное число.
Значит, "четных" и "нечетных" графов - поровну. А т.к. ребро либо есть, либо его нет, то ответ ?.

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 14:35 


29/10/14
31
DeBill в сообщении #1098087 писал(а):
VfuVfn
А можно и не считать: дорисуем оставшиеся ребра, их нечетное число.
Значит, "четных" и "нечетных" графов - поровну. А т.к. ребро либо есть, либо его нет, то ответ ?.

вот теперь я точно запутался, получается надо разделить общее количество графов пополам? а граф без ребер куда?

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 14:45 
Заслуженный участник


10/01/16
2315
VfuVfn в сообщении #1098115 писал(а):
общее количество графов пополам?


Да.
VfuVfn в сообщении #1098115 писал(а):
граф без ребер куда?


0 - число четное.
Кстати, фокус с взаимнооднозначным соответствием не проходит в полном графе с четным числом ребер. Тогда можно делать так
(сравните со своим решением): подставьте в формулу бинома Ньютона $(a+b)^n = ....$ числа $a=1, b=-1$, и сравните с Вашей суммой (а еще можно подставить две единички...).

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 14:54 
Заслуженный участник
Аватара пользователя


19/12/10
1546
VfuVfn
Someone в сообщении #1098075 писал(а):
Это была Вам подсказка: как найти ответ, практически ничего не вычисляя.
А это была подсказка, что для нахождения правильного ответа достаточно разделить общее число графов пополам. Кстати, чему равно общее число помеченных графов с шестью вершинами?

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 14:58 


29/10/14
31
whitefox в сообщении #1098120 писал(а):
VfuVfn
Someone в сообщении #1098075 писал(а):
Это была Вам подсказка: как найти ответ, практически ничего не вычисляя.
Это была вам подсказка, что для нахождения правильного ответа достаточно разделить общее число графов пополам. Кстати, а чему равно общее число помеченных графов с шестью вершинами?

с общим числом просто $2^{\frac{n(n-1)}{2}}$
а вот с биномом и 1 -1 не понятно.

 Профиль  
                  
 
 Re: Количество помеченных графов
Сообщение09.02.2016, 15:03 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Дык, распишите $(a+b)^n=\ldots$, подставьте в равенство $a=1$, $b=-1$, перенесите отрицательные члены в другую часть…

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group