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

[VfuVfn]

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

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

так я не понимаю:
а) -1 - означает что ребра нет?
б) почему 1 и - 1 - означает есть ребро и нет?
в) что такое n - количество вершин?

как вы связали бином ньютона - вот это интереснее всего... я не думал в эту сторону вообще)

[whitefox]

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

с общим числом просто $2^{\frac{n(n-1)}{2}}$

Верно.

А с биномом так: $(1+1)^{15}=\sum\limits_{k=0}^{15}\binom{15}k.$
А с учётом $\binom{15}k=\binom{15}{15-k}$ получим $(1+1)^{15}=2\sum\limits_{k=0}^{7}\binom{15}k.$
Сумма $\sum\limits_{k=0}^{7}\binom{15}k$ ничто не напоминает?

[VfuVfn]

простите, нет. и почему единицы в биноме тоже не напомнило ничего :(

[whitefox]

Пожалуйста, напишите здесь в виде формулы сумму биномиальных коэффициентов, что вы суммируете. Их, кажется, восемь?

[Someone]

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

-1 - означает что ребра нет?

Не означает.

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

почему 1 и - 1 - означает есть ребро и нет?

Не означает.

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

в) что такое n - количество вершин?

Просто проделайте то, что я предлагал. Потом вспомните, какую сумму Вы вычисляли первоначально, чтобы найти количество графов с чётным числом рёбер, и сравните её (сумму) с тем, что получилось после указанных мной манипуляций.

[VfuVfn]

я суммирую такие слагаемые:
$\binom{15}{0}+\binom{15}{2}+\binom{15}{4}+\binom{15}{6}+\binom{15}{8}+\binom{15}{10}+\binom{15}{12}+\binom{15}{14}$

[DeBill]

VfuVfn
Очень хорошо!
Обозначим их сумму $A$, а сумму остальных биноминальных к-тов - через $B$.
Из подсказок, которыми мы Вам дружно задурили голову, (из бинома) следует
$A-B=0, A+B=2^{15}$. Найдите $A$.

[VfuVfn]

ура!прояснило.
спасибо.

[DeBill]

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

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

б) почему 1 и - 1 - означает есть ребро и нет?

(почти): каждой единичке в здоровенной сумме соответствует граф с нечетным числом ребер (т.е., с четным числом отсутствующих), и наоборот! Ну, а то, что вся сумма нулевая, еще раз говорит о том что их (четных и нечетных) поровну. Ну, и т.д.

[VfuVfn]

Для $n >2$ так? ведь если n =2, то сумма получает 1 - 1 - 1 + 1, но графа 2 с ребром и без.

[Someone]

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

Для $n >2$ так? ведь если n =2, то сумма получает 1 - 1 - 1 + 1, но графа 2 с ребром и без.

Вот как Вам

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

прояснило

А что обозначает $n$ в этих формулах — не поняли. И что за сумма.

[DeBill]

VfuVfn
Someone
Ну, это частично, моя вина: сбой в обозначениях - у VfuVfn

$n$ - число вершин. А у меня - число ребер. Звиняюс...

[VfuVfn]

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

[Someone]

DeBill, буква $n$ впервые появилась в вашем сообщении и обозначала число рёбер в полном графе. А потом VfuVfn начал путать, и так до сих пор и не разобрался в вопросе. Видимо, потому, что поленился сделать то, что ему настойчиво рекомендовалось: сравнить свою сумму ${15\choose 0}+{15\choose 2}+{15\choose 4}+\ldots+{15\choose 14}$ с той суммой, которая получается из бинома. Он даже не понял, что что именно надо подставлять в бином, чтобы получить число всех помеченных графов, и что подставлять, чтобы сравнить число помеченных графов с чётным и с нечётным числом рёбер.

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

1 и -1 - четные и нечетные ребра соответственно

Нет. Это просто $1$ и $-1$. Их надо подставить в бином, скобки раскрыть, отрицательные члены перенести в другую часть и сравнивать полученное равенство с вашей суммой.

[VfuVfn]

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

DeBill, буква $n$ впервые появилась в вашем сообщении и обозначала число рёбер в полном графе. А потом VfuVfn начал путать, и так до сих пор и не разобрался в вопросе. Видимо, потому, что поленился сделать то, что ему настойчиво рекомендовалось: сравнить свою сумму ${15\choose 0}+{15\choose 2}+{15\choose 4}+\ldots+{15\choose 14}$ с той суммой, которая получается из бинома. Он даже не понял, что что именно надо подставлять в бином, чтобы получить число всех помеченных графов, и что подставлять, чтобы сравнить число помеченных графов с чётным и с нечётным числом рёбер.

ну что ж, раз вы так настойчивы, поясню.
Я не воспользовался вашим указанием про перенос слагаемых, потому что это именно указание, а не совет. Возможно вам его достаточно для понимания, мне, увы, нет. От того, что вы повторили его 2 раза мне яснее и понятнее не стало, уж поверьте.
Ваша цитата:

Цитата:

Просто проделайте то, что я предлагал. Потом вспомните, какую сумму Вы вычисляли первоначально, чтобы найти количество графов с чётным числом рёбер, и сравните её (сумму) с тем, что получилось после указанных мной манипуляций.

. Подходя формально, что я должен сравнить))

Спасибо вам за помощь.

-- 10.02.2016, 17:10 --

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