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
17975
Москва
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
2318
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
2318
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
17975
Москва
VfuVfn в сообщении #1098313 писал(а):
Для $n >2$ так? ведь если n =2, то сумма получает 1 - 1 - 1 + 1, но графа 2 с ребром и без.
Вот как Вам
VfuVfn в сообщении #1098133 писал(а):
прояснило
А что обозначает $n$ в этих формулах — не поняли. И что за сумма.

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


10/01/16
2318
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
17975
Москва
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  След.

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



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

Сейчас этот форум просматривают: DariaRychenkova


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

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