Algorithm to get the number of sorted combinations? Lets have a set of number S = {A,B,C,...,n} where A < B < C .... < n
how many ways can you sort their combinations?
Take this small example:
If the set is {1,2,8} (so n = 3) i can sort their combination in ascending order like this: 1,2,1+2,8,1+8,2+8,1+2+8 which is equal to: A,B,C,A+B,A+C,B+C,A+B+C
BUT if my set of numbers is 1,3,4 then my array will be equal to: A,B,A+B,C,A+C,B+C,A+B+C  as you can see A+B will be greater or smaller sometimes.
So for N = 3 theres the follow possible combinations:
{A,B,C,A+B,A+C,B+C,A+B+C} and {A,B,A+B,C,A+C,B+C,A+B+C} theres only 2
Is there an algorithm that can take out for me this combinations(dont brute force)?
How many combinations are in N, 
i want to know how many "combinations" can i get, so for N = 3 its 2 for N = 3 its ???.
Thanks.
 A: This is not a complete answer, but in order to get you started:
At least for small $N$ you can read off the cases from the Hasse diagram. E.g. for your example $N=3$ we have
$$\begin{matrix}
  & & & & A+B+C \\
  & & & \huge\diagup & \\
  & & B+C \\
  & & \huge| & & \\
  & & A+C \\
  & \huge\diagup & & \huge\diagdown \\
C & &  & & A+B \\
  & \huge\diagdown & & \huge\diagup & \\
  & & B & & \\
  & & \huge| & & \\
  & & A & & \\
\end{matrix}$$
(where I've broken the symmetry because the hack I'm using to draw the diagram with MathJax has limitations around padding).
You can immediately see that the only incomparable elements are $A+B$ and $C$, and there are two ways to order two elements.
For $N=4$ it's more complicated:
$$\begin{matrix}
  & &   &                & \mkern-36mu A+B+C+D \mkern-36mu & & & & \\
  & &   &                & \huge| & & \\
  & &   &                & B+C+D & & & & \\
  & &   &                & \huge| & & \\
  & &   &                & A+C+D & & & & \\
  & &   & \huge\diagup & & \huge\diagdown & & \\
  & & C+D &                & & & A+B+D \\
  & &   & \huge\diagdown & & \huge\diagup & & \huge\diagdown \\
  & &   &                & B+D & & & & A+B+C \\
  & & & \huge\diagup & & \huge\diagdown & & \huge\diagup \\
  & & A+D & & & & B+C \\
  & \huge\diagup & & \huge\diagdown & & \huge\diagup \\
D & &  & & A+C \\
  & \huge\diagdown & & \huge\diagup & & \huge\diagdown \\
  & & C & & & & A+B \\
  & &   & \huge\diagdown & & \huge\diagup & \\
  & &   &                & B & & \\
  & &   &                & \huge| & & \\
  & & & & A & & \\
\end{matrix}$$
The choices are not all independent. E.g. $A+B$ vs $C$ is the same choice as $C+D$ vs $A+B+D$, because there's an obvious symmetry: $x < y$ iff $A+B+C+D - x > A+B+C+D - y$. (You may wish to add $0$ to the diagrams to emphasise the symmetry).
More subtlely, the choices are no longer binary. $D$ is incomparable to the entire chain $A + C < B + C < A + B + C$, so there are four places we can insert it into the chain, and they make it collapse in different ways.


*

*If $D < A + C$ we're left with two decisions: $A + B$ vs $C < D$; and $A+D$ vs $B+C$.

*If $A + C < D < B + C$ we're left with two decisions: $C$ vs $A+B$ and $B+C$ vs $A + D$.

*If $B + C < D < A + B + C$ we're left with one decision: $C$ vs $A+B$.

*If $A + B + C < D$ we again have the one decision $C$ vs $A+B$.


All of the remaining decisions are independent, so there are 14 possible chains.

I did the above diagrams by hand. If you want to construct them algorithmically then you can do a transitive reduction from a set of simple but not minimal relations. Calling the values $A_1, A_2, \ldots A_N$:


*

*For each element $A_i + A_j + \ldots + A_m$, we remove in turn each variable $A_j$ and replace it with $A_k$ choosing the smallest $k > j$ such that $A_k$ is not already included. Then $A_i + A_j + \ldots + A_m < A_i + A_k + \ldots + A_m$.

*For each element $A_i + A_j + \ldots + A_m$ which doesn't include $A_1$, we add $A_1$. Then $A_i + A_j + \ldots + A_m < A_1 + A_i + A_j + \ldots + A_m$.


This gives a sparse graph, so the transitive reduction can be done in $2^N N$ time.
However, if you want to automate this rather than have a manual step, it may be simpler to construct the full transitive closure in $2^{3N}$ time (or slightly faster if you want to use a more complex matrix multiplication algorithm) and read off the incomparable pairs directly rather than reconstructing them from the forks in the transitive reduction.
