Математический форум Math Help Planet
http://mathhelpplanet.com/

Вопрос по задаче из комбинаторики
http://mathhelpplanet.com/viewtopic.php?f=62&t=56162
Страница 1 из 1

Автор:  02Artem02 [ 18 окт 2017, 22:50 ]
Заголовок сообщения:  Вопрос по задаче из комбинаторики

Помогите по задаче из комбинаторики
Есть такая таблица трех рядов

2 4 6 8 10 12
4 16 64 256 1024 4096
2 6 20 70 126 ?

С первым рядом все понятно – это последовательность четных чисел, начиная с 2
Второй ряд тоже прост – это 2 в степени соответствующего значения из первого ряда
А вот третий создает вопрос. Суть задачи такова: есть только два значения 1 и 0, как например, в двоичной системе исчисления. Значения первого ряда - это кол-во разрядов этого двоичного числа. Значения второго ряда – кол-во чисел (или возможных комбинаций 1 и 0) для данного количества разрядов. Формулу использовал такую xxxx - кол-во комбинаций = (кол-во значений x)^(кол-во иксов), привожу для вашей проверки, т.к. не специалист по комбинаторики. Так вот значения третьего ряда это количество таких комбинаций, где в числе количество 0 равно количеству 1. Т.е. при числе с разрядом 2 мы получаем 4 комбинации: 00, 01, 10, 11. Из этих четырех только две 01 и 10 удовлетворяют условию . У четырехразрядного таких комбинаций 6 и тл. Вопрос в том, какое значение будет шестым (и вообще n-ным) в третьем ряду, именно с точки зрения математических формул, если кто встречался с подобной задачей. Данные значения третьего ряда подобраны методом перебора с помощью excel, так что в них возможны ошибки, хотя надеюсь что ряд верен.

Автор:  Avgust [ 19 окт 2017, 03:11 ]
Заголовок сообщения:  Re: Вопрос по задаче из

Третий ряд хорошо известный. Это центальные биноминальные коэффициенты:

[math]a_n=\frac{(2n)!}{(n!)^2}[/math]

2, 6, 20, 70, 252, 924, ...

https://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BD%D1%82%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B1%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D1%8D%D1%84%D1%84%D0%B8%D1%86%D0%B8%D0%B5%D0%BD%D1%82

Автор:  02Artem02 [ 19 окт 2017, 21:38 ]
Заголовок сообщения:  Re: Вопрос по задаче из

в первую очередь, прошу прошения за пятого члена третьего ряда (126), как оказалось excel меня вчера подвел (сразу я этого не заметил). Новое значение 264 (предположительно). Avgust, с вашей формулой я не согласен по той причине, что полученный с помощью нее ряд строится из последовательности натуральных чисел, т.е 1 2 3 4 5 6.... НО в задаче принципиальным условием является то, что используются только четные числа. Проблема в том, что значение n=4 должно точно соответствовать значению 6, а у вас по формуле ему будет соответствовать 70. Но т.к. в двоичной системе с разрядностью 4 "влезают" только 16 чисел, от 0 до 15, число 70 заведомо не верно. В условиях я указывал, что третий ряд это кол-во комбинаций при которых кол-во 0 = кол-ву 1. Возможно из-за того в посте моя красивая таблица из word'а превратилась в сдвинутые значения рядов это визуально не понятно.

Автор:  Avgust [ 19 окт 2017, 22:48 ]
Заголовок сообщения:  Re: Вопрос по задаче из

Проверил числа 2, 6, 20, 70, 264 по энциклопедии числовых последовательностей
https://oeis.org/search?q=2%2C+6%2C+20%2C+70%2C+264&sort=&language=&go=Search

Такой последовательности еще нет. Так что у меня большие сомнения в Вашем последнем числе 264

Автор:  3D Homer [ 19 окт 2017, 23:09 ]
Заголовок сообщения:  Re: Вопрос по задаче из

Avgust считал количество разрядов равным [math]2n[/math]. 02Artem02, если вам нужно, чтобы количество разрядов было именно [math]n[/math], то формула для третьего ряда будет [math]C_n^{n\slash2}=\binom{n}{n\slash2}=\frac{n!}{(n\slash2)^2}[/math]. Следующее значение после 70 — 252, как было сказано.

Автор:  02Artem02 [ 20 окт 2017, 20:46 ]
Заголовок сообщения:  Re: Вопрос по задаче из

3D Homer, если вы подставите в приведенную вами формулу 4 то да, она вычислит вам 6, но если вы подставите третий член первого ряда 6 , то получается 6!= 720 и (6/2)^2= 9 и общий ответ получается 80, кстати а не 70. Но даже если 70, это все равно заведомо неправильный ответ из-за того что двоичное число с разрядностью 6 не может иметь более 64 комбинаций.Я думаю, что вы не учитываете главного, что это задача из комбинаторики. Значения третьего ряда это НЕ какой-то отдельный числовой ряд это КОЛИЧЕСТВО комбинаций. Еще раз напоминаю что первый ряд это кол-во разрядов в двоичном числе. Второй ряд это кол-во комбинаций или кол-во чисел с соответствующем разрядом. И третий ряд это некая часть комбинаций из общего возможного количества, которая подчиняются определенному условию, см. в первом сообщении

Автор:  3D Homer [ 20 окт 2017, 22:09 ]
Заголовок сообщения:  Re: Вопрос по задаче из

02Artem02 писал(а):
но если вы подставите третий член первого ряда 6 , то получается 6!= 720 и (6/2)^2= 9
Прошу прощения: я пропустил факториал в знаменателе. Правильная формула [math]C_n^{n\slash2}=\binom{n}{n\slash2}=\frac{n!}{((n\slash2)!)^2}[/math].

Автор:  02Artem02 [ 22 окт 2017, 15:40 ]
Заголовок сообщения:  Re: Вопрос по задаче из комбинаторики

в таком варианте, кажется подходит

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/