2014 dxdy logo

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

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


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


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



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


29/10/14
31
Someone в сообщении #1098125 писал(а):
Дык, распишите $(a+b)^n=\ldots$, подставьте в равенство $a=1$, $b=-1$, перенесите отрицательные члены в другую часть…

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

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

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


19/12/10
1546
VfuVfn в сообщении #1098123 писал(а):
с общим числом просто $2^{\frac{n(n-1)}{2}}$
Верно. :D

А с биномом так: $(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$ ничто не напоминает?

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


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

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


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

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


23/07/05
17973
Москва
VfuVfn в сообщении #1098126 писал(а):
-1 - означает что ребра нет?
Не означает.
VfuVfn в сообщении #1098126 писал(а):
почему 1 и - 1 - означает есть ребро и нет?
Не означает.
VfuVfn в сообщении #1098126 писал(а):
в) что такое n - количество вершин?
Просто проделайте то, что я предлагал. Потом вспомните, какую сумму Вы вычисляли первоначально, чтобы найти количество графов с чётным числом рёбер, и сравните её (сумму) с тем, что получилось после указанных мной манипуляций.

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


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

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


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

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


29/10/14
31
ура!прояснило.
спасибо.

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


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

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

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


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

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


23/07/05
17973
Москва
VfuVfn в сообщении #1098313 писал(а):
Для $n >2$ так? ведь если n =2, то сумма получает 1 - 1 - 1 + 1, но графа 2 с ребром и без.
Вот как Вам
VfuVfn в сообщении #1098133 писал(а):
прояснило
А что обозначает $n$ в этих формулах — не поняли. И что за сумма.

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


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

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

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


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

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


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

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

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


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


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

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

-- 10.02.2016, 17:10 --

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

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

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



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

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


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

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