Chapter 11Applications of Slicing to Combinatorics

11.1 Introduction

A combinatorial problem usually requires enumerating, counting, or ascertaining existence of structures that satisfy a given property c11-math-0001 in a set of structures c11-math-0002. We now show that slicing can be used for solving such problems mechanically and efficiently. Specifically, we give an efficient (polynomial time) algorithm to enumerate, count, or detect structures that satisfy c11-math-0003 when the total set of structures is large but the set of structures satisfying c11-math-0004 is small. We illustrate the slicing method by analyzing problems in integer partitions, set families, and the set of permutations.

Consider the following combinatorial problems:

  1. (Q1)  Count the number of subsets of the set c11-math-0005 (the set {c11-math-0006}), which have size c11-math-0007 and do not contain any ...

Get Introduction to Lattice Theory with Computer Science Applications now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.