Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 16:24 
Не в сети
Начинающий
Зарегистрирован:
21 апр 2017, 15:53
Сообщений: 11
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Ноли в старших разрядах тоже считаем, то есть числа вроде 0000, 0001, 0010, 0011, 0100, 0101, 0110 и 0111 тоже считаем четырёхзначными и считаем, что в числе 0000 четыре ноля, в числах: 0001, 0010 и 0100 по три ноля, в числах 0011, 0101 и 0110 по два ноля, а в числе 0111 один ноль. Числа двоичные, то есть в каждом разряде может быть только или 0, или 1. Вопрос : сколько всего может быть различных n-значнымх двоичных чисел, содержащих ровно по m нолей (или ровно по m единиц)? Я в принципе решил "в лоб" перебором всех числе заданной разрядности и счётом, количества нулевых бит в каждом и инкрементом счётчика при равенстве сосчитанного значения заданному m. Но этот грязный хак не работает для разрядностей выше 63-х бит (разрядность типа минус один). А есть ли решение получше? Настоящая задача такая: раскрыть скобки в [math]{\left(a-b\right)}^{n}[/math] и вычислить коэффициент при каждом [math]\left(a^m\right)*\left(b^{n-m}\right)[/math]. Знаки коэффициентов - не проблема, проблема в модулях. Или я фигнёй маюсь и при n=64 модуль хотя бы одного коэффициента превысит [math]2^{63}[/math]? Возьмём куб разности, он равен (a-b)*(a-b)*(a-b) (именно эти скобки и раскрываем), если только раскрыть скобки, то получим: a*a*a-a*a*b-a*b*a+a*b*b-b*a*a+b*a*b+b*b*a-b*b*b, каждый член соответствует одному числу: a*a*a - 000, a*a*b - 001, a*b*a - 010, a*b*b - 011, b*a*a - 100, b*a*b - 101, b*b*a - 110, b*b*b - 111, то есть ноли соответствуют множителям a, единицы - множителям b, если произведения одинаковых множителей заменить степенями, то количество нолей - показатель степень a, количество единиц - показатель степени b, а если потом сгруппировать члены с одинаковыми наборами показателей, то количество различных чисел с заданным количеством нолей равно модулю коэффициента при члене.


Последний раз редактировалось taras 21 апр 2017, 16:34, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 16:31 
Не в сети
Профи
Аватара пользователя
Зарегистрирован:
31 дек 2016, 03:01
Сообщений: 448
Откуда: Минск, Беларусь
Cпасибо сказано: 23
Спасибо получено:
101 раз в 98 сообщениях
Очков репутации: 20

Добавить очки репутацииУменьшить очки репутации
Вы "в лоб" с помощью компьютерной программы считали?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 16:35 
Не в сети
Начинающий
Зарегистрирован:
21 апр 2017, 15:53
Сообщений: 11
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Ну не вручную же. Конечно софтину написал. Точнее это только одна подпрограмма в ней.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 16:39 
Не в сети
Профи
Аватара пользователя
Зарегистрирован:
31 дек 2016, 03:01
Сообщений: 448
Откуда: Минск, Беларусь
Cпасибо сказано: 23
Спасибо получено:
101 раз в 98 сообщениях
Очков репутации: 20

Добавить очки репутацииУменьшить очки репутации
taras писал(а):
Вопрос : сколько всего может быть различных n-значнымх двоичных чисел, содержащих ровно по m нолей (или ровно по m единиц)?
Для обоих задач:

[math]C_{n}^{m}[/math] - число сочетаний из [math]n[/math] элементов по [math]m[/math] элементов (Вы выбираете из [math]n[/math] разрядов числа [math]m[/math] разрядов, где будут стоять [math]0[/math] (или [math]1[/math]).

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 16:42 
Не в сети
Начинающий
Зарегистрирован:
21 апр 2017, 15:53
Сообщений: 11
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
А как считается это [math]C_n^m[/math]? А то я в комбинаторике полный ноль, причём левый.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 16:51 
Не в сети
Профи
Аватара пользователя
Зарегистрирован:
31 дек 2016, 03:01
Сообщений: 448
Откуда: Минск, Беларусь
Cпасибо сказано: 23
Спасибо получено:
101 раз в 98 сообщениях
Очков репутации: 20

Добавить очки репутацииУменьшить очки репутации
[math]C_{n}^{m} =\frac{ n! }{ m! \cdot \left( n-m \right)! }[/math]

[math]n![/math] - фактор числа [math]n[/math], [math]n[/math] - целое неотрицательное число.

По определению.

[math]0!=1[/math],

если [math]n[/math] - натуральное число, то [math]n![/math] - это призведение натуральных чисел от [math]1[/math] до [math]n[/math].

Например:
[math]1!=1[/math];

[math]2!=1 \cdot 2=2[/math];

[math]3!=1 \cdot 2 \cdot 3=6[/math];

[math]4!=1 \cdot 2 \cdot 3 \cdot 4=24[/math].

Вообще-то я думал, что раз вы такую задачу ставите, то с элементами комбинаторики и числом сочетаний Вы знакомы.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 16:58 
Не в сети
Профи
Аватара пользователя
Зарегистрирован:
31 дек 2016, 03:01
Сообщений: 448
Откуда: Минск, Беларусь
Cпасибо сказано: 23
Спасибо получено:
101 раз в 98 сообщениях
Очков репутации: 20

Добавить очки репутацииУменьшить очки репутации
[math]\left( a+b \right)^n=\sum\limits_{k=0}^{n} C_{n}^{k}\,a^k\,b^{n-k}[/math] (как эта формула точно называется не помню. Кажется, "формула Бернулли для многочлена").

Для Вашей задачи

[math]\left( a-b \right)^n=\sum\limits_{k=0}^{n} \left( -1 \right)^{n-k} \,C_{n}^{k}\,a^k\,b^{n-k}[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 17:13 
Не в сети
Профи
Аватара пользователя
Зарегистрирован:
31 дек 2016, 03:01
Сообщений: 448
Откуда: Минск, Беларусь
Cпасибо сказано: 23
Спасибо получено:
101 раз в 98 сообщениях
Очков репутации: 20

Добавить очки репутацииУменьшить очки репутации
В обоих мною записанных формулах в предыдущем сообщении коэффициенты (слева направа) по модулю соответственно равны:

[math]C_{n}^{0}[/math], [math]C_{n}^{1}[/math], [math]C_{n}^{2}[/math], [math]\ldots[/math], [math]C_{n}^{k}[/math], [math]\ldots[/math], [math]C_{n}^{n-2}[/math], [math]C_{n}^{n-1}[/math], [math]C_{n}^{n}[/math].

Сумма этих коэффициетов (по модулю) равна [math]2^n[/math] (для этого в первой мною записанной формуле в предыдущем сообщении надо положить [math]a=b=1[/math]).


Последний раз редактировалось _Sasha_ 21 апр 2017, 17:14, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 17:14 
Не в сети
Начинающий
Зарегистрирован:
21 апр 2017, 15:53
Сообщений: 11
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
n! не лезет в тип уже при n=21, сами коэффициенты вроде растут медленнее, так что "в лоб" как раз похоже и лучше.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сколько всего таких чисел
СообщениеДобавлено: 21 апр 2017, 17:28 
Не в сети
Профи
Аватара пользователя
Зарегистрирован:
31 дек 2016, 03:01
Сообщений: 448
Откуда: Минск, Беларусь
Cпасибо сказано: 23
Спасибо получено:
101 раз в 98 сообщениях
Очков репутации: 20

Добавить очки репутацииУменьшить очки репутации
Для вычисления числа сочетаний [math]C_{n}^{m}[/math], где [math]m=1,2, \ldots ,n-1[/math] можете воспользоваться рекурсивной формулой:

[math]C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}[/math],

[math]C_{n}^{0}=C_{n}^{n}=1[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2, 3  След.  Страница 1 из 3 [ Сообщений: 25 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Сколько всего комбинаций можно составить из 5 чисел, если..

в форуме Комбинаторика и Теория вероятностей

Akeron

13

2691

11 июл 2015, 00:28

Сколько всего теорий всего может быть?

в форуме Размышления по поводу и без

vladicxjo

4

485

10 янв 2019, 04:05

Сколько таких слов?

в форуме Комбинаторика и Теория вероятностей

youi

9

263

25 апр 2020, 11:59

Сколько таких слов?

в форуме Комбинаторика и Теория вероятностей

youi

16

501

25 май 2020, 11:02

Докажите, что таких чисел бесконечно много

в форуме Интересные задачи участников форума MHP

Xenia1996

0

180

23 ноя 2022, 00:42

Найдите количество таких чисел в пределах

в форуме Алгебра

Ilya83

1

237

04 июл 2018, 17:05

Сколько всего магических сумм? Формула

в форуме Размышления по поводу и без

Avgust

18

1082

24 ноя 2019, 22:31

Сколько всего букетов можно составить из 10различных цветов?

в форуме Комбинаторика и Теория вероятностей

nurmaganbetdauren

4

268

11 окт 2020, 19:21

Сколько всего учеников, которые учатся на отлично или хорошо

в форуме Комбинаторика и Теория вероятностей

ibra2010

1

268

14 сен 2016, 20:54

Задача: сколько чисел

в форуме Комбинаторика и Теория вероятностей

Scofield

9

1792

22 дек 2014, 18:07


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 17


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

Найти:
Перейти:  
cron

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved