Математический форум 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/ |