Published by Dimitris Kougioumtzis · Updated
Update a single Pascal row backward to compute C(n,k) without intermediate division.
Apply Pascal's recurrence to a short row of coefficients, updating backward to preserve previous-row values.
When to use Binomial coefficient
Counting unordered selections without factorial intermediates.
Choosing an alternative
Pascal triangle displays many coefficients; this routine targets one.
Worked example: input and state changes
Example input
30,15
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [] }Step 87: Pascal row 13, entry 6 = 1716.
State at this checkpoint
{ "values": [ 1, 12, 66, 220, 495, 792, 1716, 1716, 1287, 715, 286, 78, 13, 1, 0, 0 ], "active": [ 6 ] }Step 174: Pascal row 19, entry 8 = 75582.
State at this checkpoint
{ "values": [ 1, 18, 153, 816, 3060, 8568, 18564, 31824, 75582, 92378, 92378, 75582, 50388, 27132, 11628, 3876 ], "active": [ 8 ] }Step 260: Pascal row 25, entry 12 = 5200300.
State at this checkpoint
{ "values": [ 1, 24, 276, 2024, 10626, 42504, 134596, 346104, 735471, 1307504, 1961256, 2496144, 5200300, 5200300, 4457400, 3268760 ], "active": [ 12 ] }Step 347: Binomial coefficient = 155117520.
State at this checkpoint
{ "values": [ 1, 30, 435, 4060, 27405, 142506, 593775, 2035800, 5852925, 14307150, 30045015, 54627300, 86493225, 119759850, 145422675, 155117520 ], "active": [ 15 ] }
Expected final state
Binomial coefficient = 155117520.
Complexity and input bounds
Family: Number theory. Time complexity: O(nk).
Space complexity: O(k) working coefficients.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Two integers n,k from 0 to 30. Returns zero when k > n.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Backward updates matter; ordered selection or selection with repetition requires different formulas.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 | // n and k each 0–30. Returns C(n,k), or 0 when k > n. These bounds fit signed 32-bit arithmetic. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(n, k) { if (k > n) { return 0; } let dp = Array(256).fill(0); dp[0] = 1; for (let i = 1; i <= n; i++) { let end = i; if (end > k) { end = k; } for (let j = end; j >= 1; j--) { dp[j] += dp[j - 1]; } } return dp[k]; } |
Source
No original paper has been verified for this entry. This source is a reference text or teaching reference, not an asserted original publication.
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition)
Donald E. Knuth (1997). Reference book.