Encuentra$k$ - las tuplas satisfacen$j=n_2+2n_3+\cdots+(k-1)n_k$ si$n_1+\cdots+n_k=n$.

Question

Deje$n_i \in N$,$i=1,\ldots,k$ y tal que$n_1+\cdots+n_k=n$. Arreglar$j \in N$.

Me gustaría encontrar todas las$k$ - tuplas (o el algoritmo de cómo encontrar$k$ - tuplas) satisface $$ j = n_2 +2n_3 + \ cdots + (k-1) n_k $$

Cualquier ayuda será muy apreciada.

Gracias.

Answer 1

Presumiblemente $n$, $j$ y $k$ se dan.

Vamos a llamar a $A_{(n,j,k)}$ este conjunto de $k$-tuplas y vamos a escribir $a_k = (a_{k-1},m)$ a significar un $k-1$-tupla con el número de $m$ anexa a hacer una $k$-tupla.

En la práctica, $n$ es un límite superior en $n_2+\cdots+n_k$ desde $n_1$ puede ser alterado para hacer la diferencia. Claramente $n_k \le n$$n_k(k-1) \le j$.

A continuación, de forma recursiva $$A_{(n,j,k)} = \bigcup_{n_k=0}^{\min(n,\lfloor j/(k-1) \rfloor)} \left\{ (a_{k-1} \in A_{(n-n_k,j-n_k(k-1),k-1)} , n_k) \right\} $$ where $A_{(n,j,k)} = \emptyset$ when $n \lt 0$ or $j \lt 0$ or $j \gt n(k-1)$, and where $A_{(n,0,1)} = \{(n)\}$ when $n \ge 0$.

Usted puede usar esto para generar el $k$-tuplas. Al final, usted puede ahorrar algo de esfuerzo por señalar que $A_{(n,j,2)} = \{(n-j,j)\}$ al$0 \le j \le n$, $A_{(n,j,k)} = \{(n,0,\ldots,0)\}$ al$n \ge 0$$j=0$.