In the context of mining for frequent patterns using the standard level-wise algorithm, the
following question arises: given the current level and the current set of frequent patterns,
what is the maximal number of candidate patterns that can be generated on the next level?
We answer this question by providing a tight upper bound, derived from a combinatorial
result by J. Kruskal (1963) and G. Katona (1968). Our result is useful for reducing the
number of database scans.

In the context of mining for frequent patterns using the standard levelwise algorithm, the
following question arises: given the current level and the current set of frequent patterns,
what is the maximal number of candidate patterns that can be generated on the next level?
We answer this question by providing tight upper bounds, derived from a combinatorial
result from the sixties by Kruskal and Katona. Our result is useful to secure existing
algorithms from a combinatorial explosion of the number of candidate patterns.