Pascal identity computes n choose k from neighboring coefficients in the previous row.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | "use strict"; // Pascal Triangle Binomial Coefficient in JavaScript // // PURPOSE // Pascal identity computes n choose k from neighboring coefficients in the previous row. A // single row is enough when updated right to left. // // METHOD // Initialize row[0] to one. For each new row, update row[j] from row[j] plus row[j-1] in // descending j order, preserving the old row values needed later. // // COMPLEXITY // O(nk) time and O(k) auxiliary space. // // CONTRACT // n >= 0 and 0 <= k <= n. All coefficients computed must fit the integer type. // Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex // counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers. // Sorted order, correct tree topology, and caller-owned data-structure invariants are // preconditions; checking them on every query would change query complexity. // Scalar and shape checks are included. Value-range checks are included where needed to // prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000 // workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python // uses arbitrary precision. Native allocation failures propagate. In-place outputs may be // partly updated after arithmetic failure. These are single-threaded, in-memory // implementations. // // LANGUAGE DETAILS // Node.js 18+: Int32Array inputs and workspaces provide compact integer storage. Automatic // lengths and checked arithmetic reject values outside signed 32-bit. Invalid inputs or // overflow throw RangeError. // // EXAMPLE // Expected return: 10. // Run: node example.js // Tests for this exact source artifact run before publication. The accompanying source // archive includes unit cases, runtime results, and source hashes. function alg_require(valid) { if (!valid) throw new RangeError("invalid algorithm input"); } function alg_checked(v) { if (!Number.isInteger(v) || v < -2147483648 || v > 2147483647) throw new RangeError("32-bit result overflow"); return v; } function alg_add(a,b) { return alg_checked(a+b); } function alg_sub(a,b) { return alg_checked(a-b); } function alg_mul(a,b) { return alg_checked(a*b); } function alg_size(n) { alg_require(Number.isInteger(n) && n>=0 && n<=4000000); return n; } function binomial(n, k) { alg_require(Number.isInteger(n) && n >= -2147483648 && n <= 2147483647); alg_require(Number.isInteger(k) && k >= -2147483648 && k <= 2147483647); alg_require(((n >= 0) && (n <= 1000000))); alg_require(((n >= 0) && (n <= 30) && (k >= 0) && (k <= n))); let row = new Int32Array(alg_size(alg_add(k, 1))); row[0] = 1; let i = 1; let j = 0; while ((i <= n)) { j = Math.min(i, k); while ((j > 0)) { row[j] = alg_add(row[j], row[alg_sub(j, 1)]); j = alg_sub(j, 1); } i = alg_add(i, 1); } return row[k]; } let n = 5; let k = 2; let result = binomial(n, k); console.log(result); |