Motzkin Number
Count Motzkin paths of length n exactly, with M(0)=M(1)=1 and a 1,000-index resource limit.
Description
Motzkin numbers count paths with up, down and horizontal steps that stay above their baseline.
Motzkin numbers count paths with up, down and horizontal steps that stay above their baseline. The path length determines the exact combinatorial count.1
The tool returns value. The indexing and output conventions below determine how to read these values.
When to use Motzkin Number
Use this for the following task: Count Motzkin paths of length n exactly, with M(0)=M(1)=1 and a 1,000-index resource limit. Use the input and output conventions below to reproduce the intended mathematical quantity.
How to use Motzkin Number and understand its results
- Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
- Enter n according to the field table, then run the tool.
- Read value. Preserve exact decimal strings and the stated indexing or coefficient order.
- Keep exact decimal strings for subsequent integer arithmetic; distinguish them from any explicitly approximate numeric result.
| Input field | Meaning | Value type and bounds | Requirement |
|---|---|---|---|
| n | Path length (resource limit 1000) | integer; minimum 0; maximum 1000 | Required |
Return one for the first two indexes, then advance an exact two-term BigInt recurrence with integer division.
M(0)=M(1)=1; (n+2)M(n)=(2n+1)M(n−1)+3(n−1)M(n−2) The symbols and boundary conditions refer to the supplied fields and the implementation described above.
| Output field | Meaning | Value type |
|---|---|---|
| value | Motzkin number | string (integer/arbitrary) |
{
"input": {
"n": 6
},
"output": {
"value": "51"
}
}Limitations and assumptions
The nonnegative path length is at most 1000. Paths are counted rather than enumerated; these are not large Schröder path counts.
Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.
Alternative or Complementary methods
Choose Large Schröder Number when you need its operation: Return the large Schröder number S(n) for paths of semilength n, with S(0)=1 and S(1)=2; n is capped at 1,000. Choose Fuss–Catalan Number for the complementary operation: Return the exact p-ary tree Fuss–Catalan number C(pn,n)/((p−1)n+1), with p≥2 and pn≤5,000 as a computation resource limit.
Background reference: OEIS A001006.
References
-
OEIS A001006 — OEIS Foundation
Similar or alternative tools
- Large Schröder Number
Return the large Schröder number S(n) for paths of semilength n, with S(0)=1 and S(1)=2; n is capped at 1,000.
- Fuss–Catalan Number
Return the exact p-ary tree Fuss–Catalan number C(pn,n)/((p−1)n+1), with p≥2 and pn≤5,000 as a computation resource limit.