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 Programming notes from reading Donald Knuth's Art of Computer Programming
Part of the 2017 CS Study Plan.
Mathematical Foundations: AOCP/Infinite Series · AOCP/Binomial Coefficients · AOCP/Multinomial Coefficients AOCP/Harmonic Numbers · AOCP/Fibonacci Numbers Puzzles/Exercises:
Volume 2: Seminumerical Algorithms
Volume 3: Sorting and Searching AOCP/Combinatorics · AOCP/Multisets · Rubiks Cube/Permutations
AOCP/Combinatorial Algorithms · AOCP/Boolean Functions AOCP/Five Letter Words · Rubiks Cube/Tuples AOCP/Generating Permutations and Tuples
|
 |
Combinatorics
Combinatorial Structures - Order Does Not Matter Ordinary generating functions
Labelled Structures - Order Matters Enumerating Permutations: String Permutations Generating Permutations: Cool · Algorithm M (add-one) · Algorithm G (Gray binary code)
Combinatorics Problems Longest Increasing Subsequence · Maximum Value Contiguous Subsequence · Racing Gems Cards (poker hands with a deck of 52 playing cards)
|