Рассмотрим граф, вершинами которого являются всевозможные 3-элементные подмножества множества {1,…,n}. Ребрами соединяются те и только те подмножества, которые пересекаются ровно по двум элементам.

Чему равно суммарное число общих соседей вершин x,y по всем (неупорядоченным) парам различных вершин x,y? Запишите ответ при n=6.

задан 30 Янв '18 17:38

10|600 символов нужно символов осталось
1

Пусть вершины x, y имеют общего соседа z. Тогда получается треугольник в графе с одной выделенной стороной x-y. Выделить сторону в треугольнике можно тремя способами. Поэтому надо найти утроенное число треугольников.

Пусть x={a,b,c}, y={a,b,d} без ограничения общности. Третья вершина либо имеет вид z={a,b,e} для какого-то числа e с теми же двумя общими вершинами, и тогда всего задействовано 5 различных элементов, из которых мы выделяем два. Либо третья вершина содержит ровно один из двух элементов a, b, и тогда с точностью до симметрии мы имеем z={a,c,d}. Здесь задействовано 4 различных элемента, и какой-то один является общим для всех трёх вершин.

Выбрать тройку вершин первого типа можно $%10C_n^5$% способами. Второго типа троек будет $%4C_n^4$%. Складываем, преобразуем, умножаем на 3, и получаем общий ответ n(n-1)(n-2)(n-3)(3n-10)/4. При n=6 формула даёт 720.

ссылка

отвечен 30 Янв '18 18:42

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×548

задан
30 Янв '18 17:38

показан
604 раза

обновлен
30 Янв '18 18:42

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru