2
$\begingroup$

With given permutation of $1,\ldots,n$ for example (in one-line notation): 3 5 1 2 4 6.

How to find amount of ascending subsequences of length 3 in the second row of the permutation ?

There's $n!/k!(n-k)!$ of subsequences of length $k$ for the identity permutation 1 2 3 4 5 6$\cdots$n.

How to deal with this problem ?

Thanks.

  • 0
    When you write `3 5 1 2 4 6`, do you mean the permutation of $\{1,\ldots,6\}$ that sends 1 to 3, 2 to 5, 3 to 1, 4 to 2, 5 to 4, and 6 to 6? Or do you mean the cyclic permutation that sends 3 to 5, 5 to 1, 1 to 2, 2 to 4, 4 to 6, and 6 to 3? I am guessing it's the former, but better to make sure...2011-05-03
  • 0
    yes first thing. f(1)=3 f(2)=5 f(3)=1 and so on2011-05-03
  • 0
    Just so I know I'm understanding this, nC3 is the ceiling on this value, correct? And you are looking at k=3, right?2011-05-03
  • 0
    yes k=3 for any kind of permutation2011-05-03
  • 0
    I was able to write a short program to count it explicitly, is this the sort of thing you're looking for?2011-05-03
  • 0
    Generally i'm interested in formula how to find those subsequences. Not in brute-force because for n=10^5 or even more brute force i guess would run quite long.2011-05-03
  • 0
    Since you want to do it for a *given* permutation, I suspect what you want is an *algorithm*, not a "formula". Or perhaps you mean a "formula" in terms of some other easier-to-count invariants of the permutation (e.g., the number of descents/ascents).2011-05-03
  • 0
    Yes i meant something like algorithm, something what could help me counting this. Sorry for complications but im not native speaker, just student :)2011-05-03
  • 1
    Since the answer could be as big as $Cn^3$, I doubt there's a way to count them quickly.2011-05-04
  • 0
    My algorithm uses two functions: Let $h(a_i)$ be the number of elements after ai greater than $a_i$. Let $g(a_i)$ be the next element after $a_i$ that is greater than $a_i$.2011-05-09
  • 0
    Sounds good, could you post it or something ?:)2011-05-09

1 Answers 1

3

It can be done in O(n log n) time. Assume for every index that it's your mid element in subsequence.

Now having x smaller elements than your mid elements and y greater elements than your mid element you can make max(x,y) subsequences with selected mid point.

It can be also easily programmed.

Simply use segment tree or BIT.

for mid element m you want to check value of x:

-they are in range $<0;m-1>$

Value of y is:

$<0;n-1> - <0;m-1>$ where n is number of elements.

  • 0
    Good approach, but it seems larger than $O(n \log n)$. For element $i$ you have $i-1$ before it and $n-i$ after it. You have to determine how many of the $i-1$ are less than element $i$ and how many of the $n-i$ are greater. Seems like those take $i$ and $n-i$ tries respectively, and we do this once for each element, so we are $O(n^2)$2011-10-26
  • 0
    Yes, you are right, but with segment tree or binary indexed tree we can easily have answer in $O(log n)$ time for each range. So overall complexity is $O(n log n)$.2011-10-26