Пусть есть таблица размером n столбцов*2 строки, в каждой строке могут быть записаны в произвольном порядке различные цифры от 1 до n. Каждую возможную запись такой таблицы назовем комбинацией. Если в одном столбце окажется 2-е одинаковые цифры, назовем это дублем. Обозначим количество комбинаций, содержащих 0 дублей - , 1 дубль- , 2 дубля -, 3 дубля -, 4 дубля -,......., n дублей -, где индекс n обозначает, что в таблице n столбцов, а индекс 2 указывает на то, что таблица содержит 2 строки. Верхний индекс i пробегает значения 1-n и символизирует комбинации включающие i дублей.
Очевидно, что количество всех возможных комбинаций заполнения таблицы равно , с другой стороны очевидно, что
Выразить значения через переменные n,2,i или показать, что это невозможно.
Замечание: равно количеству возможных латинских таблиц, состоящих из 2х строк и n столбцов.
Нетривиальная задача про дубли
- buratino.2016
- Сообщений: 273
- Зарегистрирован: 07 сен 2015, 21:00
Нетривиальная задача про дубли
Последний раз редактировалось buratino.2016 27 ноя 2019, 18:03, всего редактировалось 1 раз.
Причина: test
Причина: test
Нетривиальная задача про дубли
, где - субфакториал.buratino.2016 писал(а):Source of the post Выразить значения T_{n,2}^i через переменные n,2,i или показать, что это невозможно.
Последний раз редактировалось 12d3 27 ноя 2019, 18:03, всего редактировалось 1 раз.
Причина: test
Причина: test
- buratino.2016
- Сообщений: 273
- Зарегистрирован: 07 сен 2015, 21:00
Нетривиальная задача про дубли
Спасибо, но что-то у меня не сходится с Вашей формулой. Например должно быть.
Может я не понял Вашу формулу? Какие значения она дает для этих величин?
По Вашей формуле у меня получилось соответственно:
проверка моих значений:
Может я не понял Вашу формулу? Какие значения она дает для этих величин?
По Вашей формуле у меня получилось соответственно:
проверка моих значений:
Последний раз редактировалось buratino.2016 27 ноя 2019, 18:03, всего редактировалось 1 раз.
Причина: test
Причина: test
- buratino.2016
- Сообщений: 273
- Зарегистрирован: 07 сен 2015, 21:00
Нетривиальная задача про дубли
Извиняюсь, я неправильно посчитал субфакториал. подставил его табличные значения- всё работает, только значения для !0 в таблице не было. Оно не определено? Если не определено, то как искать
Как Вы нашли решение? Не с помощью мат. пакетов случайно?
Как Вы нашли решение? Не с помощью мат. пакетов случайно?
Последний раз редактировалось buratino.2016 27 ноя 2019, 18:03, всего редактировалось 1 раз.
Причина: test
Причина: test
- buratino.2016
- Сообщений: 273
- Зарегистрирован: 07 сен 2015, 21:00
Нетривиальная задача про дубли
И ещё вопрос, что такое ? То, что это неполная гамма функция я прочел, но неполная сверху или неполная снизу? и почему такое странное обозначение? Что значит -1 после запятой в скобках?
Последний раз редактировалось buratino.2016 27 ноя 2019, 18:03, всего редактировалось 1 раз.
Причина: test
Причина: test
- buratino.2016
- Сообщений: 273
- Зарегистрирован: 07 сен 2015, 21:00
Нетривиальная задача про дубли
Нашел, что субфакториал нуля: , что вполне согласуется с представленным решением. Также выяснил, что - это неполная сверху гамма-функция, где зафиксирован верхний предел интегрирования.
Осталось непонятным как уважаемый 12d3 нашел решение.
Осталось непонятным как уважаемый 12d3 нашел решение.
Последний раз редактировалось buratino.2016 27 ноя 2019, 18:03, всего редактировалось 1 раз.
Причина: test
Причина: test
- buratino.2016
- Сообщений: 273
- Зарегистрирован: 07 сен 2015, 21:00
Нетривиальная задача про дубли
12d3, я понял как Вы решили эту задачу. Вы были знакомы с задачей о беспорядках, далее, первую строку можно записать способами. С каждым из способов существуют случаи содержащие дубли. дублей можно выбрать способами. С каждым из способов решается задача о беспорядках для чисел не являющихся дублями, решение дает способов. Итого: способов. И никакие мат. пакеты не нужны )
С триплетами уже посложнее.
Кстати, Вам просила передать привет Omega, она приглашает Вас на форум: http://mathhelpplanet.comhttp://mathhelpplanet.com
С триплетами уже посложнее.
Кстати, Вам просила передать привет Omega, она приглашает Вас на форум: http://mathhelpplanet.comhttp://mathhelpplanet.com
Последний раз редактировалось buratino.2016 27 ноя 2019, 18:03, всего редактировалось 1 раз.
Причина: test
Причина: test
Нетривиальная задача про дубли
Да, все верно, только с задачей о беспорядках я ознакомился в момент решения. Омега я тоже передаю привет, но от предложения, пожалуй, откажусь. Разонравились немножко магические квадраты и иже с ними.
Последний раз редактировалось 12d3 27 ноя 2019, 18:03, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Олимпиадные задачи»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 2 гостей