combinatorics-calculator
Scannednpx machina-cli add skill a5c-ai/babysitter/combinatorics-calculator --openclawFiles (1)
SKILL.md
1.6 KB
Combinatorics Calculator Skill
Purpose
Calculate combinatorial values with modular arithmetic support for competitive programming applications.
Capabilities
- Factorial and inverse factorial precomputation
- nCr, nPr with modular arithmetic
- Catalan, Stirling, Bell numbers
- Lucas theorem implementation
- Inclusion-exclusion principle application
- Generating functions
Target Processes
- combinatorics-counting
- number-theory-algorithms
- dp-pattern-matching
Combinatorial Functions
Basic Counting
- Factorial: n!
- Permutations: P(n,r) = n!/(n-r)!
- Combinations: C(n,r) = n!/(r!(n-r)!)
Special Numbers
- Catalan numbers
- Stirling numbers (first and second kind)
- Bell numbers
- Derangements
Advanced Techniques
- Lucas theorem (for large n, small p)
- Inclusion-exclusion
- Burnside's lemma
- Generating functions
Input Schema
{
"type": "object",
"properties": {
"operation": {
"type": "string",
"enum": ["nCr", "nPr", "factorial", "catalan", "stirling", "lucas", "precompute"]
},
"n": { "type": "integer" },
"r": { "type": "integer" },
"mod": { "type": "integer" },
"precomputeLimit": { "type": "integer" }
},
"required": ["operation"]
}
Output Schema
{
"type": "object",
"properties": {
"success": { "type": "boolean" },
"result": { "type": "integer" },
"code": { "type": "string" },
"formula": { "type": "string" }
},
"required": ["success"]
}
Source
git clone https://github.com/a5c-ai/babysitter/blob/main/plugins/babysitter/skills/babysit/process/specializations/algorithms-optimization/skills/combinatorics-calculator/SKILL.mdView on GitHub Overview
This skill computes combinatorial values using modular arithmetic for competitive programming. It supports precomputation of factorials and inverse factorials, enables nCr and nPr under a modulus, and covers Catalan, Stirling, Bell numbers, Lucas theorem, inclusion-exclusion, and generating functions.
How This Skill Works
Precompute factorials and inverse factorials up to your limit, then use modular arithmetic to compute nCr and nPr. The tool also implements advanced combinatorics formulas (Catalan, Stirling, Bell numbers) and techniques like Lucas theorem and inclusion-exclusion, operating under a chosen modulus.
When to Use It
- When you need binomial coefficients nCr modulo p for large n.
- When counting permutations with restrictions using modular counts (nPr under mod).
- When solving problems involving Catalan, Stirling, or Bell numbers modulo p.
- When n is large relative to p and Lucas theorem is required.
- When applying inclusion-exclusion or generating-function methods under a modulus.
Quick Start
- Step 1: Choose an operation (e.g., nCr) and a prime modulus.
- Step 2: Set precomputeLimit to cover your max n and run precompute.
- Step 3: Call the operation with the required n, r, and mod.
Best Practices
- Precompute factorials and inverse factorials up to the maximum n you expect.
- Use a prime modulus to enable modular inverses and Lucas theorem.
- Validate inputs and handle edge cases (r=0, r=n) explicitly.
- Prefer the precomputed formulas over repeated factorial calculations to optimize time.
- Test with known small cases to verify correctness before scaling up.
Example Use Cases
- Compute C(1e6, 5) mod 1e9+7 for CP problem.
- Evaluate nPr with large n and small p using precomputed inverses.
- Find Catalan number C_n mod p for n up to 1000.
- Count partitions with Stirling numbers of the second kind modulo p.
- Apply inclusion-exclusion to count distinct subsets under a modulus.
Frequently Asked Questions
Add this skill to your agents
