Stage 4: Advanced Techniques·Combinatorics & Counting

Hard#18668 min readMathDynamic ProgrammingCombinatoricsLeetCode

Rearrange Sticks With K Visible

Unsigned Stirling numbers DP

Stirling numbers of the first kind. Pure combinatorial DP.

Published Apr 16, 2026

Problem

There are n uniquely-sized sticks in a row. You look from the left; a stick is visible if no taller stick stands before it.

Return the number of permutations of n sticks such that exactly k sticks are visible from the left, modulo 10^9 + 7.

Input

n = 3, k = 2

Output

Explanation

Of 6 permutations: [1,3,2],[2,3,1],[2,1,3] have exactly 2 visible sticks. 3 permutations.

Input

n = 5, k = 5

Output

Explanation

Only the sorted ascending order [1,2,3,4,5] has all 5 visible.

Input

n = 20, k = 11

Output

647427950

Intuition

Focus on the shortest stick (height 1). It can only be visible if it is placed first (leftmost). Otherwise, it hides behind any taller stick to its left.

If stick 1 is placed first: the remaining n - 1 sticks must produce k - 1 visible sticks. That is f(n-1, k-1).
If stick 1 is placed in any of the other n - 1 positions: it is invisible, and the remaining n - 1 sticks must produce exactly k visible sticks. That is (n - 1) * f(n-1, k).

Recurrence: f(n, k) = f(n-1, k-1) + (n-1) * f(n-1, k).

This is exactly the unsigned Stirling numbers of the first kind |s(n, k)|. Base cases: f(0, 0) = 1, f(n, 0) = 0 for n > 0, f(0, k) = 0 for k > 0.

Approach

Brute Permutation

TimeO(n!)

SpaceO(n)

Generate all permutations, count visible sticks in each, tally those with exactly k. Only for tiny n.

impl Solution {
    pub fn rearrange_sticks(n: i32, k: i32) -> i32 {
        let n = n as usize;
        let k = k as usize;
        let mut perm: Vec<usize> = (1..=n).collect();
        let mut count = 0u64;
        loop {
            let vis = Self::visible(&perm);
            if vis == k {
                count += 1;
            }
            if !Self::next_perm(&mut perm) {
                break;
            }
        }
        (count % 1_000_000_007) as i32
    }

    fn visible(p: &[usize]) -> usize {
        let mut mx = 0;
        let mut cnt = 0;
        for &x in p {
            if x > mx {
                cnt += 1;
                mx = x;
            }
        }
        cnt
    }

    fn next_perm(a: &mut [usize]) -> bool {
        let n = a.len();
        if n <= 1 { return false; }
        let mut i= n - 2;
        while i < n && a[i] >= a[i + 1] {
            if i == 0 { return false; }
            i -= 1;
        }
        let mut j = n - 1;
        while a[j] <= a[i] { j -= 1; }
        a.swap(i, j);
        a[i + 1..].reverse();
        true
    }
}

Rust · runnable

function rearrangeSticks(n: number, k: number): number {
  const perm = Array.from({ length: n }, (_, i) => i + 1);
  let count = 0;
  const visible = (p: number[]): number => {
    let mx = 0, cnt = 0;
    for (const x of p) { if (x > mx) { cnt++; mx = x; } }
    return cnt;
  };
  const nextPerm = (a: number[]): boolean => {
    let i = a.length - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;
    if (i < 0) return false;
    let j = a.length - 1;
    while (a[j] <= a[i]) j--;
    [a[i], a[j]] = [a[j], a[i]];
    let l = i + 1, r = a.length - 1;
    while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; }
    return true;
  };
  do { if (visible(perm) === k) count++; } while (nextPerm(perm));
  return count % 1_000_000_007;
}

TypeScript · runnable

Stirling DP

TimeO(n · k)

SpaceO(n · k)

Recommended

Fill the f(n, k) table bottom-up with modular arithmetic.

impl Solution {
    pub fn rearrange_sticks(n: i32, k: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = n as usize;
        let k = k as usize;
        if k > n { return 0; }

        let mut dp = vec![vec![0i64; k + 1]; n + 1];
        dp[0][0] = 1;

        for i in 1..=n {
            for j in 1..=k.min(i) {
                dp[i][j] = (dp[i - 1][j - 1] + (i as i64 - 1) * dp[i - 1][j]) % MOD;
            }
        }

        dp[n][k] as i32
    }
}

Rust · runnable

function rearrangeSticks(n: number, k: number): number {
  const MOD = 1_000_000_007n;
  if (k > n) return 0;

  const dp: bigint[][] = 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(k, i); j++) {
      dp[i][j] = (dp[i - 1][j - 1] + BigInt(i - 1) * dp[i - 1][j]) % MOD;
    }
  }

  return Number(dp[n][k]);
}

TypeScript · runnable

Trace

n = 3, k = 2. Build the DP table:

i	j=0	j=1	j=2
0	1	0	0
1	0	1	0
2	0	1	1
3	0	2	3

dp[3][2] = 3.

Edge cases

k = n — only sorted ascending. Answer is 1.
k = 1 — only the tallest stick is visible. The tallest must be first; the rest can be in any order = (n-1)!. Equivalently |s(n,1)| = (n-1)!.
k = 0 — impossible for n > 0. Answer is 0.
Large n, k — n = 1000, k = 500 is within the O(nk) DP.

Takeaway

"How many permutations have property P?" often reduces to a classical combinatorial recurrence. Here, the "visible sticks" question maps exactly to unsigned Stirling numbers of the first kind — a well-studied family that also counts permutations by cycle count.

The focus-on-the-smallest-element trick generalizes: whenever elements are distinguishable by size, reasoning about the extremal element's placement often yields a clean two-case recurrence.

Medium#62

Unique Paths

dp[i][j] = dp[i-1][j] + dp[i][j-1]. Grid DP starting point.

Hard#1569

Ways to Reorder Array to Get Same BST

Recursive decomposition + nCr. Beautiful problem for your background.

Hard#2514

Count Anagrams

Multinomial coefficients. Precompute factorial + modular inverse.