# Polyominoes

### From charlesreid1

Consider the plane

A cell is a unit square in , and a polyomino is a finite connected union of cells having no cut point.

A column of polyominoes is the intersection between the polyomino and an infinite vertical strip of cells.

The area of a polyomino is a count of its cells.

The height of a polyomino is the number of rows. The width of a polyomino is the number of columns.

## Contents

## Classes of Polyominoes

Classes of polyominoes include:

- Ferrer diagrams
- Staircase polyominoes
- Bar chart polyominoes
- Column-convex polyominoes
- Directed polyominoes

### Ferrers Diagrams

The polyomino is constructed by gluing successively taller columns together, only moving east and north (or, alternatively, east and south).

These are defined by two non-intersecting paths having only north or east steps.

The perimeter of these polyominoes are enumerated by the Catalan numbers. Their generating functions according to area, width, and height are related to q-Bessel functions and q-Catalan numbers.

### Staircase Polyominoes

Staircase polyominoes begin with a height of 1 on the far left. These usually increase or decrease in height by 1 unit at a time, but that varies from author to author.

### Bar Chart Polyominoes

Bar chart polyominoes consist of columns of varied height, but sharing a common baseline, glued together side by side.

### Column Convex Polyominoes

A column convex polyomino is one in which all columns are connected. Drawing a series of vertical lines should result in only two points of intersection with the polyomino at any given point.

# Related

# Flags

The Art of Computer ProgrammingArt of Computer Programming
Part of the 2017 CS Study Plan.
Mathematical Foundations: AOCP/Infinite Series AOCP/Harmonic Numbers Puzzles/Exercises:
AOCP/Combinatorics
AOCP/Combinatorial Algorithms AOCP/Five Letter Words AOCP/Generating Permutations and Tuples
· Template:AOCPFlag · e |

Combinatorics
Ordinary generating functions
Enumerating Permutations: String Permutations Generating Permutations: Cool
Longest Increasing Subsequence Cards (poker hands with a deck of 52 playing cards)
· Template:CombinatoricsFlag · e |