Marked partitions and combinatorial analogs of the Sylvester identity

F. V. Weinstein

Published 2008-05-12, updated 2015-07-19Version 5

Let $n>0$ be an integer. A partition of degree $n$ is a decomposition $n=i_1+i_2+\dots+i_q$, where $0<i_1\leq i_2\leq \dots\leq i_q$ are integers. The numbers $i_1,i_2,\dots,i_q$ are called the parts of the partition. Let $k\>1$ and $\lambda\>0$ be integers. The partition is said to be a $(\lambda,k)$--partition if $i_1\>k$ and $i_{a+1}-i_a\>\lambda$ for all $a\in[1,q-1]$. The main result of the article is a construction of the bijective maps for $\lambda=2$ or $\lambda=3$ and any $k$ between the set of $(1,k)$-partitions of a given degree and the sets of the $(\lambda,k)$--partitions of the same degree, some special parts of which are marked. These bijections lead to combinatorial identities. I construct one such map for $\lambda=3$, and another one for simultaneously $\lambda=2$ and $\lambda=3$. For $\lambda=3$, the maps thus defined are different. The corresponding identity for $\lambda=3$ can be presented analytically. In this form, for $k=1$, it coincides with the classical Sylvester identity. For $\lambda=2$, the result also implies an interesting identity.