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.
Description
Fuss–Catalan numbers count ordered full p-ary tree structures with a given number of internal nodes.
Fuss–Catalan numbers count ordered full p-ary tree structures with a given number of internal nodes. Binary arity recovers the ordinary Catalan numbers.1
The tool returns value. The indexing and output conventions below determine how to read these values.
When to use Fuss–Catalan Number
Use this for the following task: 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. Use the input and output conventions below to reproduce the intended mathematical quantity.
How to use Fuss–Catalan 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, arity 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 | Internal-node count (resource limit 2500) | integer; minimum 0; maximum 2500 | Required |
| arity | Tree arity p (resource limit 5000) | integer; minimum 2; maximum 5000 | Required |
Require integer arity at least two and nonnegative n, enforce p×n≤5000, then evaluate the binomial coefficient and exact BigInt division.
count = C(p×n,n)/((p−1)×n+1) The symbols and boundary conditions refer to the supplied fields and the implementation described above.
| Output field | Meaning | Value type |
|---|---|---|
| value | Fuss–Catalan number | string (integer/arbitrary) |
{
"input": {
"n": 4,
"arity": 3
},
"output": {
"value": "55"
}
}Limitations and assumptions
The count is for fixed arity and ordered trees. No tree is generated, and the combined work bound can reject inputs that separately satisfy the field bounds.
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 Narayana Number when you need its operation: Count Dyck paths of semilength n with k peaks as an exact Narayana number, using N(0,0)=1 and zero outside the counting range; indices are capped at 500. Choose Catalan Triangle Entry for the complementary operation: Return the ballot-number Catalan triangle entry T(n,k)=C(n+k,k)−C(n+k,k−1), with zero outside 0≤k≤n and indices capped at 500.
Background reference: OEIS A001764.
References
-
OEIS A001764 — OEIS Foundation
Similar or alternative tools
- Narayana Number
Count Dyck paths of semilength n with k peaks as an exact Narayana number, using N(0,0)=1 and zero outside the counting range; indices are capped at 500.
- Catalan Triangle Entry
Return the ballot-number Catalan triangle entry T(n,k)=C(n+k,k)−C(n+k,k−1), with zero outside 0≤k≤n and indices capped at 500.