Partitions with maximal length

95 Views Asked by At

Suppose $L$ is a non-empty finite set of positive integers, and let $d=\max L$. For a positive integer $n$, define an $L$-partition of $n$ to be any sequence $a_1,a_2,\ldots,a_m$ of elements of $L$ such that $a_1+a_2+\cdots+a_m=n$, and define $m$ to be the length of such an $L$-partition. Clearly, if $n$ has an $L$-partition, then there will be one of maximal length. Assuming that $n$ has an $L$-partition, I would like to have an upper bound on the number of $L$-partitions of maximal length, ideally as a simple function of $d$. As basic example, if $1\in L$, then clearly there is only one partition of maximal length for any positive integer $n$, $1+1+\cdots+1=n$ (with $n$ 1's). A less trivial example is $L=\lbrace 5,6,7,8\rbrace $, $n=24$. Then $5+5+6+8$, $5+5+7+7$, $5+6+6+7$ and $6+6+6+6$ all have maximal length.