303. Permutation Coefficient Problem

Given two integers n and k, compute the permutation coefficient P(n, k) = n! / (n-k)! - the number of ways to arrange k items chosen from n distinct items, where order matters.

Input: Two lines: the first contains n, the second contains k. Output: Print a single integer - the permutation coefficient P(n, k).

0 <= k <= n <= 20

The EXTRA factor of k in this recurrence (compared to plain Pascal's triangle) is exactly what accounts for the ORDERING of the k chosen items - without it, you'd just be computing the binomial coefficient (unordered selections) instead.

Compute P(n,k), the number of ways to arrange k items chosen from n distinct items, where order matters. Brute force: Compute n!/(n-k)! directly using factorials - this works for small n but can involve computing unnecessarily large intermediate factorial values (like 20! for n=20) even when the final quotient is much smaller, unless careful cancellation is done manually. Optimised: Building the table via this dedicated recurrence (mirroring Pascal's triangle but with the extra k multiplier) avoids ever computing full factorials directly - every value stays a genuine, correctly-scaled permutation coefficient throughout the computation.

Compute n! and (n-k)! independently, each via its own loop (or recursive) multiplication from 1 up to the target, then divide the first by the second to get P(n, k). This directly matches the mathematical formula and is simple to implement, but it always computes the full n! even when k is much smaller than n, doing unnecessary multiplication work and then an extra division step. Time: O(n) Space: O(1)

Recognize that P(n, k) = n * (n-1) * ... * (n-k+1), a product of exactly k consecutive terms, and compute it with a single loop of k multiplications, skipping the computation of n! and (n-k)! and the division entirely. When k is much smaller than n (as constraints allow k <= n <= 20), this does noticeably less work than computing two full factorials. Time: O(k) Space: O(1)

Precompute a factorial table for every value from 0 up to n in a single O(n) pass (factorial[i] = factorial[i-1] * i), storing each result. Once built, any P(n, k) query is answered in O(1) as factorial[n] / factorial[n-k]. For a single one-off query this is no faster than the direct product, but since n and k are both tiny (<= 20) and such coefficient lookups are typically needed repeatedly across many test cases in a single run, precomputing once and answering every query in constant time is the most efficient approach overall. Time: O(n) preprocessing, O(1) per query Space: O(n)

1. P(n,k) = P(n-1,k) + k*P(n-1,k-1), with P(n,0)=1 for every n - this mirrors Pascal's-triangle-style DP but with an EXTRA factor of k on the diagonal term. 2. Build a 2D table indexed by n and k using this recurrence rather than computing factorials directly, avoiding needing a separate base case for (n-k)!. 3. P(n,k) equals C(n,k) multiplied by k! - a useful sanity check once both are computed.

Time: O(n * k) - filling the DP table up to row n, column k. Space: O(n * k) for the full table (reducible to O(k) with a rolling 1D array).

Test k = 0 (P(n,0) = 1), k = n (a full permutation, n!), and n = k = 20 (upper bound, where P(n,k) is large enough to need a 64-bit-safe accumulation).

Be ready to state the relationship P(n,k) = C(n,k) * k! explicitly - a good way to cross-check your permutation coefficient DP against a separately-computed binomial coefficient.