Количество помеченных графов

[VfuVfn]

Привет.

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

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

[whitefox]

VfuVfn в сообщении #1098054 писал(а):

Что я делаю не так?

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

[VfuVfn]

whitefox в сообщении #1098055 писал(а):

VfuVfn в сообщении #1098054 писал(а):

Что я делаю не так?

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

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

[whitefox]

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

[VfuVfn]

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

[Someone]

VfuVfn в сообщении #1098068 писал(а):

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

А что, Ваши вычисления дают разные результаты?

[VfuVfn]

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

[Someone]

VfuVfn в сообщении #1098072 писал(а):

не пересчитывал

Напрасно.

VfuVfn в сообщении #1098072 писал(а):

но смысл я потерял

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

[VfuVfn]

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

[DeBill]

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

[VfuVfn]

DeBill в сообщении #1098087 писал(а):

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

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

[DeBill]

VfuVfn в сообщении #1098115 писал(а):

общее количество графов пополам?

Да.

VfuVfn в сообщении #1098115 писал(а):

граф без ребер куда?

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

[whitefox]

VfuVfn

Someone в сообщении #1098075 писал(а):

Это была Вам подсказка: как найти ответ, практически ничего не вычисляя.

А это была подсказка, что для нахождения правильного ответа достаточно разделить общее число графов пополам. Кстати, чему равно общее число помеченных графов с шестью вершинами?

[VfuVfn]

whitefox в сообщении #1098120 писал(а):

VfuVfn

Someone в сообщении #1098075 писал(а):

Это была Вам подсказка: как найти ответ, практически ничего не вычисляя.

Это была вам подсказка, что для нахождения правильного ответа достаточно разделить общее число графов пополам. Кстати, а чему равно общее число помеченных графов с шестью вершинами?

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

[Someone]

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