Number of Ways to Rearrange Sticks With K Sticks Visible

hard dp combinatorics

Problem

You have n sticks of distinct lengths 1..n. Line them up in a row. A stick is "visible" from the left if every stick before it is shorter (a stick is visible exactly when it is taller than all sticks to its left). Count the number of arrangements in which exactly k sticks are visible, modulo 10^9+7.

Inputn = 3, k = 2

Output3

The arrangements [1,3,2], [2,3,1], and [2,1,3] each leave exactly 2 sticks visible from the left. These are the unsigned Stirling numbers of the first kind.

def rearrange_sticks(n, k):
    MOD = 10**9 + 7
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(1, min(i, k) + 1):
            visible = dp[i - 1][j - 1]
            hidden = dp[i - 1][j] * (i - 1)
            dp[i][j] = (visible + hidden) % MOD
    return dp[n][k]

function rearrangeSticks(n, k) {
  const MOD = 1000000007n;
  const dp = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(0n));
  dp[0][0] = 1n;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= Math.min(i, k); j++) {
      const visible = dp[i - 1][j - 1];
      const hidden = dp[i - 1][j] * BigInt(i - 1);
      dp[i][j] = (visible + hidden) % MOD;
    }
  }
  return Number(dp[n][k]);
}

class Solution {
    public int rearrangeSticks(int n, int k) {
        final long MOD = 1000000007L;
        long[][] dp = new long[n + 1][k + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                long visible = dp[i - 1][j - 1];
                long hidden = dp[i - 1][j] * (i - 1) % MOD;
                dp[i][j] = (visible + hidden) % MOD;
            }
        }
        return (int) dp[n][k];
    }
}

int rearrangeSticks(int n, int k) {
    const long long MOD = 1000000007LL;
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, k); j++) {
            long long visible = dp[i - 1][j - 1];
            long long hidden = dp[i - 1][j] * (i - 1) % MOD;
            dp[i][j] = (visible + hidden) % MOD;
        }
    }
    return (int) dp[n][k];
}

Explanation

We line up sticks of lengths 1..n and count how many orderings leave exactly k sticks visible from the left, where a stick is visible when it is taller than everything before it. The cleanest way to count this is to focus on the shortest stick (length 1) and ask where it goes.

Let dp[i][j] be the number of ways to arrange i sticks so that exactly j are visible. The base case is dp[0][0] = 1: one empty arrangement with zero visible sticks.

Now place the shortest of the i sticks. It can only ever be visible if it sits in the very first position (nothing to its left). That single choice contributes dp[i-1][j-1]: arrange the other i-1 sticks with j-1 visible, then prepend the shortest as the j-th visible one. Otherwise the shortest stick is hidden — it can slot into any of the i-1 gaps after some taller stick, contributing dp[i-1][j] * (i-1) because it never changes the visibility of the rest. Adding the two gives the recurrence dp[i][j] = dp[i-1][j-1] + (i-1) * dp[i-1][j], taken mod 10^9 + 7. These are exactly the unsigned Stirling numbers of the first kind.

Example: n = 3, k = 2. Building the table gives dp[3][2] = dp[2][1] + 2 * dp[2][2] = 1 + 2 * 1 = 3, matching the three valid arrangements [1,3,2], [2,3,1], and [2,1,3].

The answer is dp[n][k]. Filling the grid touches every (i, j) pair once, so the work is O(n · k).

Time: O(n · k) Space: O(n · k)