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

[Someone]

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

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

Вот эту сумму

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

$\binom{15}{0}+\binom{15}{2}+\binom{15}{4}+\binom{15}{6}+\binom{15}{8}+\binom{15}{10}+\binom{15}{12}+\binom{15}{14}$

с тем, что получится после использования формулы бинома Ньютона в равенстве $(1-1)^{15}=0$ и переноса отрицательных членов в правую часть. Выпишите результат этих действий здесь. Биномиальные коэффициенты вычислять не надо, оставьте их в виде $\binom{15}{k}$. А также посмотрите, что получится из равенства $(1+1)^{15}=2^{15}$. Увидите, почему это даёт число всех помеченных графов. И поймёте, почему вот это есть ерунда:

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

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

[VfuVfn]

Итак:
$(1-1)^{15}=\binom{15}{0}1^{15}-\binom{15}{1}1^{14}1+\binom{15}{2}1^{13}(-1)^{2}-\binom{15}{3}1^{12}1^{3}+\binom{15}{4}1^{11}(-1)^{4}-\binom{15}{5}1^{10}1^{5}+\binom{15}{6}1^{9}(-1)^{6}-\binom{15}{7}1^{8}1^{7}+\binom{15}{8}1^{7}(-1)^{8}-\binom{15}{9}1^{6}1^{9}+\binom{15}{10}1^{5}(-1)^{10}-\binom{15}{11}1^{4}1^{11}+\binom{15}{12}1^{3}(-1)^{12}-\binom{15}{13}1^{2}1^{13}+\binom{15}{14}1^{1}(-1)^{14}-\binom{15}{15}1^{0}1^{15}$
Переносим:
$\binom{15}{0}1^{15}+\binom{15}{2}1^{13}(-1)^{2}+\binom{15}{4}1^{11}(-1)^{4}+\binom{15}{6}1^{9}(-1)^{6}+\binom{15}{8}1^{7}(-1)^{8}+\binom{15}{10}1^{5}(-1)^{10}+\binom{15}{12}1^{3}(-1)^{12}+\binom{15}{14}1^{1}(-1)^{14}=\binom{15}{1}1^{14}1+\binom{15}{3}1^{12}1^{3}+\binom{15}{5}1^{10}1^{5}+\binom{15}{7}1^{8}1^{7}+\binom{15}{9}1^{6}1^{9}+\binom{15}{11}1^{4}1^{11}+\binom{15}{13}1^{2}1^{13}+\binom{15}{15}1^{0}1^{15}$
Ну с этим понятно вроде понятно.
Ерунда - понятно почему, потому что n я считал количество вершин, а не ребер.
а вот как вы дошли от графа до бинома ньютона, я вот даже не думал в эту сторону,тупо считал .

[Someone]

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

а вот как вы дошли от графа до бинома ньютона

Да как-как… Сопоставил два выражения и увидел, что они одинаковые. И что из этого следует, что графов (с заданным числом вершин) с чётным числом рёбер столько же, сколько графов с нечётным числом рёбер.

[VfuVfn]

не, ну это ж удивление и восхищение было.
Спасибо.

[kavadele]

А какой ответ в итоге, можно узнать? Решаю такую же задачку, хочу сравнить ответ.
У меня 16384.

[whitefox]

Ответ был приведён — половина от $2^{15}.$ Советую тему, всё таки, прочитать, похоже, вы решали каким-то другим методом.

[kavadele]

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

Ответ был приведён — половина от $2^{15}.$ Советую тему, всё таки, прочитать, похоже, вы решали каким-то другим методом.

Я прочитала, не все поняла (про бином Ньютона), но главное, за что благодарю, - за наводку на казалось бы очевидную мысль, что четных и нечетных одинаковое число. Я гуманитарий, буквально на днях начавший учиться теории графов, простите уж меня)
Так и решала, нашла 2k, затем половину от него.