← Back to catalogue
Research draft

Catalan number

vr.tr.catalan-number · XCT.QTY

Let an agent explain Catalan numbers and their formula, describe the structures they count, support computing and proving identities, and relate them to computer science applications.

Thing Registry Cross-cutting context

Research draft, second pass

A second pass drafted this model: the structure a model of this thing needs, and what is known about it in the world. The line under this one says how the second half was obtained - researched against sources, or recalled without web access, in which case nothing here was read anywhere and every claim is a lead to verify. Unreviewed either way.

written by Claude from model knowledge without web access - no source was read, every claim is a lead to verify

Researched by: Claude

Purpose and description

Let an agent explain Catalan numbers and their formula, describe the structures they count, support computing and proving identities, and relate them to computer science applications.

A sequence of positive integers 1, 1, 2, 5, 14, 42 and so on, named after Eugene Catalan, given by a formula involving binomial coefficients, that counts many combinatorial structures such as correctly matched brackets, binary trees, triangulations of polygons, lattice paths that stay above the diagonal and non-crossing partitions; Catalan numbers are central in combinatorics, appear in computer science and probability, and have many known interpretations.

What it is for: A combinatorial number sequence.

It can be explain the formula; describe counted structures; support computation and proofs; relate to applications.

Distinguishing features

Binomial formula

Many interpretations

Recurrence

Generating function

What it looks like

Not physical; a sequence of integers.

How it is recognised

1, 1, 2, 5, 14, 42, 132

Counts brackets, trees, paths

Fibonacci and factorial sequences count other things

Related models

is a kind of - category

positive integer

is related to - another integer sequence entry

Fermat number

is related to - non-crossing partitions

equivalence relation

is related to - combinatorial structures

abstraction

In practice

Families and kinds

Catalan numbers as bracket counts

Catalan numbers as tree counts

Catalan numbers as path counts

generalised and q-Catalan numbers

Catalan numbers in computing

Standards and regulation

Mathematical conventions and notation

Sequence database conventions

Failure modes and hazards

Off-by-one indexing errors

Confusing Catalan numbers with other sequences

Overflow in computation

Where this came from

wikidata · CC0 1.0

Source repository Registry entry point

Drafted structure

Bundle to layer to finding to question, as the second pass will find it: 4 bundles · 8 layers · 8 findings · 16 questions.

Understand What Catalan numbers are.

Mathematics.

Formula

Formula and recurrence.

Formula

Formula.

  1. What is the formula for the nth Catalan number, and what recurrence and generating function do they satisfy? definition
  2. How does indexing differ between sources? boundary

Interpretations

What they count.

Interpretations

Interpretations.

  1. Which structures do Catalan numbers count, such as bracketings, binary trees, triangulations and Dyck paths? definition
  2. Which entry fits a specific structure? action
Compute Computing and proving.

Practice.

Calculate

Computing values.

Calculate

Computing.

  1. How is the nth Catalan number computed efficiently, and what are its asymptotics? action
  2. Which entry fits binomial coefficients? action

Prove

Proofs and bijections.

Prove

Proofs.

  1. How are the formula and bijections between Catalan structures proved? action
  2. Which references are standard? provenance
Apply Applications.

Context.

Computing

Computer science.

Computing

Computing.

  1. Where do Catalan numbers appear in parsing, data structures and algorithms? provenance
  2. Which entry fits a specific application? action

Generalise

Generalisations.

Generalise

Generalisations.

  1. What are generalised, q-Catalan and Fuss-Catalan numbers? definition
  2. Which entry fits a generalisation? action
Learn History and teaching.

Education.

History

History.

History

History.

  1. How were Catalan numbers discovered by Euler, Catalan and earlier by Mingantu? provenance
  2. Which entry fits history of combinatorics? action

Teach

Teaching.

Teach

Teaching.

  1. How can Catalan numbers be taught with counting exercises? action
  2. Which misconceptions arise? provenance

What the second pass must settle

  • Should each interpretation be a separate entry?
  • How should sequence databases be linked?
  • How should generalisations be linked?
Draft as JSON