8
$\begingroup$

Problem: Given $n \in \mathbb{Z}_+$ and a set $A \subset \{ 1,\ldots,n \}$ sorted in ascending order, find the number of permutations $\sigma \in S_n$ such that $A$ is a longest increasing subsequence of $\sigma$.

($A$ need not be the only longest increasing subsequence of $\sigma$.)

A solution might be expressed as a formula or an algorithm.

This question is inspired by this puzzle on Puzzling SE. Can you get a solution efficient enough to answer that question? Clearly, checking all $n!$ permutations is out of the question, as each one requires $O(n\log n)$ time by a clever Patience Sort algorithm (or $O(n^2)$ by dynamic programming).

$\endgroup$
2
  • 6
    $\begingroup$ The RSK algorithm gives a bijection between permutations and ordered pairs of Young Tableaux. This bijection plays nicely with longest increasing subsequences. This might lead to an answer. Read The surprising mathematics of longest increasing subsequences for more info. $\endgroup$
    – Mike Earnest
    Commented Sep 19, 2023 at 19:56
  • 1
    $\begingroup$ Page 82 of the book Mike Earnest cites provides a nice asymptotic result. For sufficiently large $n$, the length of the longest increasing subsequence of a random permutation of $\{1,2,\dots,n\}$ may be expressed (loosely) as $2 \sqrt{n} + \xi \, n^{1/6}$, where the random variable $\xi$ is very likely to be between $-6$ and $3$, with a mode of around $-2$. $\endgroup$
    – Jim Ferry
    Commented Sep 28, 2023 at 14:58

0

Reset to default

You must log in to answer this question.