Parcial de Combinatoria Algebraica

Marzo 4, 2003

Problemas

1. Decimos que una permutación a_{1} … a_{n} es alternante si a_{1} < a_{2} > a_{3} < a_{4} > · · ·. Sea E_{n} el número de permutaciones alternantes de [n].

(a) Demuestre que

2E_{n+1} = ∑_{k=0}^{n} \binom{n}{k}E_{k}E_{n−k}.

(b) Concluya que

∑_{n≥0} E_{n} \frac{x^{n}}{n!} = tan x + sec x.

(c) Use el resultado de la parte (b) para dar una demostración combinatoria de la identidad

1 + tan^{2} x = sec^{2} x.

2. Sean n y k enteros positivos. Sea a_{k}(n) el número de particiones de n en partes que no son múltiplos de k. Sea b_{k}(n) el número de particiones de n donde ninguna parte aparece k o más veces. Demuestre que a_{k}(n) = b_{k}(n).

3. Sea P un poset finito y sea k el tamaño máximo de una anticadena de P. Sean A y B dos anticadenas de P de k elementos. Sean C el conjunto de elementos maximales y D el conjunto de elementos minimales del poset A∪B (con el orden inducido por P). Demuestre que C y D son anticadenas de P de k elementos.

4. Encuentre el número de posets P de n elementos tales que, para cada entero positivo i con 1 ≤ i ≤ n − 1, P tiene exactamente dos ideales de i elementos. Dibuje los posets P y J(P) que se obtienen en el caso n = 4.

5. Sea P un poset de n elementos numerado naturalmente. Si f_{k} es el número de cadenas de J(P) de k + 1 elementos, el f-polinomio de J(P) es:

f_{J(P)}(x) = ∑_{k} f_{k}x^{k}.

Podemos ver las extensiones lineales de P como permutaciones de [n]. Si w_{k} es el número de extensiones lineales de P con k descensos, el W -polinomio de P es:

W_{P} (x) = ∑_{k} w_{k}x^{k}.

Demostrar que

W_{P} (\frac{x}{x + 1}) = \frac{f_{J(P)}(x)}{(x + 1)^{n}} .

¿Qué dice esta afirmación cuando x → ∞? Nota. Una numeración natural de P es una numeración de los elementos de P con los números 1, …, n tal que, si i < j en el poset, entonces el número asignado al elemento i es menor que el número asignado a j.