O'Reilly logo

Introduction to Lattice Theory with Computer Science Applications by Vijay K. Garg

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required