Комбинаторика (количество векторов с ограничениями на компон

[User008]

$N векторов ($x_1$, $x_2$, ... $x_n$)
Для каждого вектора заданы два значения $min_i$, $max_i. Надо найти число возможных сочетаний векторов, при том что суммы значений каждой компоненты каждого вектора принадлежит диапазону соответсвующих $min_i$, $max_i.

Например:
$V_1($x_1$, $x_2$, $x_3$), $V_2$($x_1$, $x_2$, $x_3$), $V_3$($x_1$, $x_2$, ($x_1$, $x_2$, $x_3$)
$min_1$ = 3, $max_1$ = 5
$min_2$ = 1, $max_2$ = 3
$min_3$ = 1, $max_3$ = 2

(1, 2, 1), (1, 1, 1), (1, 1, 0) удовлетворяет условию.
(2, 2, 2), (1, 1, 1), (1, 1, 0) не удовлетворяет.

Надо найти количество удовлетворяющих условию сочетаний.

[maxal]

Здесь можно рассматривать каждую компоненту независимо от остальных, а потом перемножить количество вариантов для разных компонент.

В $i$-й компоненте должно выполняться неравенство:

$$\min_i \leq y_1 + y_2 + \dots + y_N \leq \max_i$$

которое в неотрицательных целых числах имеет ровно

$$\binom{\max_i + N - 1}{N-1} - \binom{\min_i + N - 2}{N-1}$$

решений.

Остается лишь перемножить эти значения по $i=1,2,\dots,n$

[Sonic86]

User008
У вас компоненты вектора хоть целочисленные?
При $max_i = min _i, N=1$ вроде имеем задачу о рюкзаке.

maxal!
А разве этот способ годится вообще? Он же вроде только для векторов из декартова произведения $A_1 \times ... \times A_n$ годится?

[Бодигрим]

Причем здесь задача о рюкзаке? Если я верно понял постановку задачи, то при условиях $m_i:=\max_i=\min_i$, $N=1$ подходящий вектор ровно один - это $(m_1,\ldots,m_n)$.

[Sonic86]

Тогда я задачу не понял.
Вы берете вектора $V_i=(x_{i1},...,x_{in}), i=1,...,N$, каждому вектору $V_i$ соответствует пара чисел $m_i, M_i$.
Далее, вы рассматриваете суммы-векторы $S_I = (s_{I1},...s_{In})$, где $s_{Ij} = \sum\limits_{i \in I} x_{ij}, j=1,...,n$ и $I \subset {1,...,N}$. Всего $2^N$ сумм-векторов.
И потом Вы хотите найти все $I$, такие, что для всех $j$ $s_{Ij}$ ограничены сверху и снизу, но чем? Ведь не числами $m_i, M_i$, хотя бы потому, что индексов $i$ всего $N$ штук, а индексов $I$ всего $2^N$ штук. Я правильно понял? Объясните пожалуйста подробнее.
Если $m_j, M_j$ поставить в соотвествие компонентам вектора - тогда задача осмысленная. Вроде так.

При $m_j = M_j$ - это обобщение задачи о рюкзаке.
Если множество $V_i$ получается как какое-то декартово произведение множеств $A_1, ... , A_n$, тогда надо просто решить $n$ систем $m_j \leq s_{Ij} \leq M_j$ и число решений будет равно $N_1 \cdot ... \cdot N_n$, где $N_j = N(m_j \leq s_{Ij} \leq M_j)$ - число решений этой системы.

[Бодигрим]

Sonic86 в сообщении #192631 писал(а):

Вы берете вектора $V_i=(x_{i1},...,x_{in}), i=1,...,N$...

По-моему, нет. Вектора $V_i$ - не фиксированные, задается лишь их общее количество $N$.

AFAIU в задаче спрашивается, сколькими способами можно выбрать $N$ векторов $V_1,\ldots,V_N\in \mathbb{Z}^n$, таких, что $\sum_{i=1}^N V_{ij} \in [m_j,M_j] $ для всех $j=\overline{1,n}$.