@misc{Linusson, author = {Linusson, Svante}, title = {Partitions with Restricted Block Sizes, M{\"o}bius Functions and the k-of-each Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1363}, number = {SC-94-06}, abstract = {{\newcommand{\R} {{\rm {\mbox{\protect\makebox[.15em][l]{I}R}}}} Given a list of \$n\$ numbers in \$\R \$, one wants to decide wether every number in the list occurs at least \$k\$ times. I will show that \$(1-\epsilon)n\log_3(n/k)\$ is a lower bound for the depth of a linear decision tree determining this problem. This is done by using the Bj{\"o}rner-Lov\'asz method, which turns the problem into one of estimating the M{\"o}bius function for a certain partition lattice. I will also calculate the exponential generating function for the M{\"o}bius function of a partition poset with restricted block sizes in general.}}, language = {en} }