Primero, permítanme demostrar que todo lo $P(n,k)=0$ para $n\geq k$, lo que sigue a partir de un simple lema:
Lema. En cualquier secuencia de $k\geq 1$ enteros $m_1, m_2, \dots, m_k$, existe una larga suma de un múltiplo de $k$.
Prueba. Definir $s_i := (m_1+m_2+\dots+m_i)\bmod k$, incluyendo a $s_0=0$. Por el principio del palomar, entre los enteros $s_0, s_1, s_2, \dots, s_k\in\{0, 1,\dots,k-1\}$, no existen dos iguales, digamos, $s_i=s_j$ para algunos $i<j$. A continuación, $m_{i+1}, m_{i+2}, \dots, m_j$ formulario requerido larga. QED
Ahora, permítanme hablar de la computación $P(n,k)$ fijos $k$.
Para cualquier entero positivo $n$ y cualquier $S\subset \mathbb{Z}_k$, vamos a $Q(n,S)$ denotar el número de $n$-tuplas de $\mathbb{Z}_k^n$ tales que la suma de cualquiera de vacío larga no es en $S$.
Entonces
$$Q(n,S) = \sum_{t\in \mathbb{Z}_k\setminus S} Q(n-1,S\cup (S-t)),$$
donde $S-j := \{ s-t\mid s\in S\}$.
Además, por definición, tenemos $$Q(0,S) = 1.$$
En otras palabras, si corregimos y arbitraria de la indexación de los subconjuntos de $\mathbb{Z}_k$, y deje $\bar{Q}(n) := [Q(n,S_1),Q(n,S_2),\dots,Q(n,S_{2^k})]^T$, luego
$$\bar{Q}(n) = M\cdot \bar{Q}(n-1) = M^n\cdot \bar{Q}(0),$$
donde $M$ es $2^k\times 2^k$ matriz con $M_{ij}$ igual al número de $t\in \mathbb{Z}_k\setminus S_i$ tal que $S_j = S_i \cup (S_i - t)$. Claramente, $\bar{Q}(0)=[1,1,\dots,1]^T$.
De ello se deduce que para cualquier $S$, la secuencia de $(Q(n,S))_{n\geq 0}$ cumple una orden de $2^k$ recurrencia lineal, y, en particular, lo hace $k^n P(n,k) = Q(n,\{0\})$. Esto, sin embargo, no es tan emocionante como sabemos que la secuencia de $(k^n P(n,k))_{n\geq 0}$ estabiliza a $0$ comenzando con $n=k$. Aún así, las citadas fórmulas permiten calcular $P(n,k)$ rutinariamente, al menos para las pequeñas $k$.
Ejemplo de $k=2$. Fijemos la indización: $S_1 = \emptyset$, $S_2=\{0\}$, $S_3=\{1\}$, e $S_4=\{0,1\}$. Entonces
$$M = \begin{bmatrix}
2 & 0 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 0
\end{bmatrix}$$
con el polinomio mínimo $x^4 - 3x^3 + 2x^2$. Por lo tanto, para $n\geq 4$
$$Q(n,S) = 3Q(n-1,S) - 2Q(n-2,S).$$
En particular, $(2^n P(n,2))_{n\geq 0} = (1,1,0,0,0,\dots)$, es decir, $P(n,2)=0$ para $n\geq 2$ como ya sabemos.
Ejemplos de $k\leq 10$.
\begin{split}
(2^n P(n,2))_{n\geq 0} &= (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, \dots), \\
(3^n P(n,3))_{n\geq 0} &= (1, 2, 2, 0, 0, 0, 0, 0, 0, 0, \dots), \\
(4^n P(n,4))_{n\geq 0} &= (1, 3, 6, 2, 0, 0, 0, 0, 0, 0, \dots), \\
(5^n P(n,5))_{n\geq 0} &= (1, 4, 12, 16, 4, 0, 0, 0, 0, 0, \dots), \\
(6^n P(n,6))_{n\geq 0} &= (1, 5, 20, 44, 10, 2, 0, 0, 0, 0, \dots), \\
(7^n P(n,7))_{n\geq 0} &= (1, 6, 30, 96, 90, 36, 6, 0, 0, 0, \dots), \\
(8^n P(n,8))_{n\geq 0} &= (1, 7, 42, 174, 240, 84, 28, 4, 0, 0, \dots), \\
(9^n P(n,9))_{n\geq 0} &= (1, 8, 56, 288, 690, 336, 168, 48, 6, 0, \dots), \\
(10^n P(n,10))_{n\geq 0} &= (1, 9, 72, 440, 1344, 984, 336, 144, 36, 4, 0, \dots).
\end{split}
P. S. he añadido estos valores a la OEIS como la secuencia de A309106.
