¿Qué es lo que cuenta esta secuencia?

Question

Al resolver (un sistema de) un sistema de ecuaciones lineales nivel por nivel recursivamente, estoy encontrando algunas ecuaciones redundantes para el nivel $n\geq5$ . La razón por la que surgen los despidos es porque $P(n)\neq P(n-1)+P(n-2)$ para $n\geq5$ . Las redundancias vienen dadas por la secuencia : $$ 0,0,0,0,1,1,3,4,7,10,16,21,32,43,60,80,110,\dots~. $$

Aquí, $P(n)$ es el número de particiones del entero $n$ . La secuencia viene dada por $P(n-1)+P(n-2)-P(n)$ para $n\geq1$ .

Una función generadora para la secuencia anterior es $$ 1 - (1-q-q^2)\prod_{n=1}^\infty {1\over (1-q^n)}~. $$

¿Se encuentra esta secuencia (o cualquier otra estrechamente relacionada) en algún contexto de la combinatoria? ¿Qué se cuenta?

(He buscado esto en OEIS; hay algunas secuencias que coinciden hasta el $16$ arriba, pero no está de acuerdo después).

Answer 1

Dejemos que $C_k$ sea el conjunto de particiones de $n$ que contiene $k$ .

Siguiendo el punto de @MaxAlekseyev tenemos, $$P(n-1)+P(n-2)-P(n)=|C_1|+|C_2|-P(n),$$ $$=|C_1\cap C_2|+|C_1\cup C_2|-P(n)$$ Es el número de particiones que contienen tanto 1 como 2, menos el número de particiones que no contienen ni 1 ni 2.

Este número es no negativo ya que a cualquier partición que no contenga ni 1 ni 2, escribiéndolo en orden no creciente como $t_1,\dots, t_k$ podemos asociar la partición $t_1,\dots,t_k-3,2,1$ que sí contiene 1 y 2 (y este mapa es uno a uno).

Así, para todos los $n$ , $P(n-1)+P(n-2)-P(n)$ es contar exactamente

cuántas particiones de $n$ contienen tanto 1 como 2, y no son de la forma $t_1,\dots,t_{k-1},t_k-3,2,1$ (eliminando $t_k-3$ si es 0) donde $t_1\ge\dots\ge t_k\ge 3$ .

Para $n=5$ Esto incluye sólo uno: $2+1+1+1$ .

Answer 2

Observe que $P(n-1)$ cuenta el número de particiones de $n$ que contienen $1$ , mientras que $P(n-2)$ cuenta el número de particiones de $n$ que contienen $2$ .

De ello se desprende que $P(n-1)+P(n-2)-P(n)$ es igual a la diferencia entre el número de particiones de $n$ que contienen $\{1,2\}$ y el número de particiones de $n$ que no contienen ni $1$ ni $2$ .