Size of downsets in the pushing order and a problem of Berlekamp Original Research Article

The shifting technique is a useful tool in extremal set theory. It was successfully used and developed by Levon Khachatrian to obtain many significant results. The shifting operation also referred to as pushing gives rise to a partial order called pushing order. Here we consider the problem of determination of the size of special downsets in this order. For the analysis, the pushing order will be expressed isomorphically in terms of lattice paths and of majorization of sequences. In the case that the sequences under consideration are periodic the generating function for the numbers arising in an old combinatorial problem due to Berlekamp will be determined.