Сколько целых неотрицательных решений имеет уравнение? - Комбинаторика - Киберфорум

Форум программистов, компьютерный форум, киберфорум

Комбинаторика

Форум программистов и сисадминов Киберфорум

Войти

Регистрация
Восстановить пароль

Сообщество

Заказать работу

Рейтинг 4.76/34:

Рейтинг темы: голосов - 34, средняя оценка - 4.76

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978

	Сколько целых неотрицательных решений имеет уравнение? 28.06.2017, 23:38. Показов 7223. Ответов 6 Метки нет (Все метки) В связи с этой темой Игра "Перемещение" возник следующий вопрос. Сколько целых неотрицательных решений имеет уравнение x1 + ... + xn = k при условии x1 >= x2 >= ... >= xn k <= n² (дополнительно) Хорошо бы еще и сгенерировать их, но с этим проблем особых нет, где-то на форуме я уже решал подобную задачку. Хотелось бы получить их число (чтобы сразу выделить нужную память) или хотя бы не слишком грубую оценку сверху. Оценку C_n+k-1^n-1 я знаю, но она слишком груба. можно, конечно, воспользоваться при генерации структурой типа <vector>, а потом посмотреть ее size (или понаблюдать крах программы), но хотелось бы выяснить этот вопрос теоретически. 0

cpp_developer

Эксперт

20123 / 5690 / 1417

Регистрация: 09.04.2010

Сообщений: 22,546

28.06.2017, 23:38

Ответы с готовыми решениями:

Сколько решений в целых неотрицательных числах имеет уравнение
Сколько решений в целых неотрицательных числах имеет уравнение х1+х2+х3+х4+х5+12?

Сколько решений в целых числах имеет уравнение?
Сколько решений в целых числах имеет уравнение x1+x2+....+xm=n ecли все xi меньше или равно 3

Сколько существует неотрицательных целых решений уравнения
Сколько существует неотрицательных целых решений уравнения x1 + x2 + x3 + x4 + x5 + x6 + x7 = 40, таких, что x1 <= 2, x2 >= 2,...

6

Symon

$Эксперт по математике/физике$

2616 / 2230 / 684

Регистрация: 29.09.2012

Сообщений: 4,577

Записей в блоге: 13

25.07.2017, 13:26

Цитата

Сообщение от Байт

Посмотреть сообщение

Сколько целых неотрицательных решений имеет уравнение

Вот решение на Маткаде

Сколько целых неотрицательных решений имеет уравнение?

Сколько целых неотрицательных решений имеет уравнение?

Сколько целых неотрицательных решений имеет уравнение?

1

iifat

2903 / 1937 / 210

Регистрация: 05.06.2011

Сообщений: 5,714

25.07.2017, 15:56

Как вариант.
Ищем последовательности $https://www.cyberforum.ru/cgi-bin/latex.cgi?y_i=\begin{cases}x_n&,\ i=n\\x_i-x_{i+1}&,\ i<n\end{cases}$ , такие что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i=1}^niy_i=k$ .
Поскольку с Маткадом незнаком, вот, на всякий случай, на Тикле (tcl)

C
1
2
3
4
5
6
7
8
9
10
11
12
13
proc terms {sum n suffix} {
  if {$sum==0 || $n==1} {output [linsert $suffix end $sum {*}[lrepeat [expr {$n-1}] 0]]; return}
  for {set i [expr {$sum/$n}]} {$i >= 0} {incr i -1} {terms [expr $sum-$i*$n] [expr {$n-1}] [linsert $suffix end $i]}
}
 
proc output list {
  set res {}
  set r 0
  foreach e $list {incr r $e; set res [linsert $res 0 $r]}
  puts [join $res +]
}
 
terms 7 4 {}

Результат

C
1
2
3
4
5
6
7
8
9
10
11
2+2+2+1
3+2+1+1
4+1+1+1
3+2+2+0
3+3+1+0
4+2+1+0
5+1+1+0
4+3+0+0
5+2+0+0
6+1+0+0
7+0+0+0

вроде б совпадает. Плюс (не уверен, что такой уж плюс) в том, что лишних строк не возникает. Ну и матрицы необязательны, достаточно вектора.

2

@eropegov $Эксперт по математике/физике$ 505 / 465 / 100 Регистрация: 30.01.2017 Сообщений: 1,371
	27.07.2017, 10:04
	Вот. 2

iifat 2903 / 1937 / 210 Регистрация: 05.06.2011 Сообщений: 5,714
	27.07.2017, 16:18
	От чуял же, чуял, что производящая функция именно такая! Руки не дошли на бумаге проверить, а то б я... Добавлено через 9 минут Можно ещё почитать Липского, Комбинаторика для программистов. Впрочем, по этому вопросу, кажется, ничего нового в этой полезнейшей книге не сказано. 1

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	27.07.2017, 18:24
	Пятиугольные числа -- это все-таки для немного другой задачи. А здесь у нас есть условие, что число слагаемых не больше n. Здесь работают "гауссовы биномиальные коэффициенты" https://www.mccme.ru/~smirnoff/papers/qbinom3.pdf Кстати, учебный курс автора статьи по ссылке Смирнова на эту тему можно послушать на Coursera (на английском языке). https://www.coursera.org/learn... binatorics Восьмая неделя как раз посвящена гауссовым коэффициентам (q-binomial coefficients) Добавлено через 5 минут По ссылке рассматривается и пентагональная теорема Эйлера как предельный случай, когда n стремится к бесконечности. 2

Байт

Диссидент

Эксперт C

Аватар для Байт

27714 / 17332 / 3810

Регистрация: 24.12.2010

Сообщений: 38,978

27.07.2017, 22:56 [ТС]

Цитата

Сообщение от iifat

Посмотреть сообщение

ещё почитать Липского,

Любимая настольная книга...

0

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

27.07.2017, 22:56

Помогаю со студенческими работами здесь

Сколько решений имеет ребус
Написал программу, которая решает следующий ребус: ABC+DEF=XYZ Суть ребуса в том, что нужно подобрать все значения A, B, C, D, E, F, X,...

При каких действительных значениях a уравнение не имеет решений
Добрый день! Задание: При каких действительных значениях a уравнение не имеет решений: \log{}_{x^2-1} (x+a)=1 Проверьте пожалуйста... ...

Сколько решений имеет следующая система булевских уравнений
Пусть через a,b,c,d обозначены булевские переменные. Сколько решений имеет следующая система булевских уравнений. Выпишите все решения. ...

Сколько существует решений в целых числах?
Сколько существует натуральных n, меньших 1031, таких что уравнение a^2+b^2=3^n имеет решение в целых числах?

Сколько решений имеет уравнение
Добрый день, форумчане. Являюсь учеником 11 класса физико-математического лицея. Вот попалась учителю такая задача( книжка с...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

7

Ответ

Создать тему

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

Наверх