Permheap

Revision en1, by RazvanD, 2017-02-01 19:15:29

Given an integer n you need to calculate the number of distinct permutations {1, 2, 3, ..., n} such that the permutation represents a linear max heap.

In other words for each position from 1 to n: p[i] > p[2*i] and p[i] > p[2*i+1]

Example: Input: 4 Output: 3

I need help solving this problem, at least a hint please.

Tags heap, permutations, combinatorics, linear heap

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English RazvanD 2017-02-01 19:15:29 335 Initial revision (published)