Articles of algebraic combinatorics

Proving Crapo's Lemma

Let $L$ be a finite lattice with least and greatest elements $0, 1$, respectively, and let $X\subseteq L$. Let $n_k$ be the number of $k$-element subsets of $X$ with join $1$ and meet $0$. I want to show that $$\sum_k (-1)^kn_k=-\mu(0, 1)+\sum_{x\leq y, [x, y]\cap X=\varnothing}\mu(0, x)\mu(y, 1).$$ This result seem to be similar to […]

Property of a polynomial with no positive real roots

The following is an exercise (Exercise #3 (a), Chapter 3, page 28) from Richard Stanley’s Algebraic Combinatorics. Let $P(x)$ be a nonzero polynomial with real coefficients. Show that the following two conditions are equivalent: There exists a nonzero polynomial $Q(x)$ with real coefficients such that all coefficients of $P(x) Q(x)$ are nonnegative. There does not […]

Identity involving partitions of even and odd parts.

First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions of $n$ whose parts are distinct and odd. Finally, let $c(n)$ be the number of partitions of $n$ which […]

Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove this will be appreciated but a combinatorial solution is greatly preferred. Thanks for your help.