Solution 1st:

a[i][j] renotes the possible number of the previous j sequences with n = i

(we set a[k][0] = 1 (0 < k <= n), which implies NULL is thought of one possible sequence)

we init that a[1][1] = a[1][0] = 1;

yeild:

a[i][0] = a[i - 1][0];

a[i][j] = a[i][j - 1] + a[i - 1][j]; (1 <= j <= i - 1)

a[i][i] = a[i][i - 1];

the answer wo want to get is a[n][n].

 1#include<iostream>
 2using namespace std;
 3
 4#define MAXN 20
 5
 6int main()
 7{
 8    // init
 9    int a[MAXN][MAXN];
10    a[1][1] = a[1][0] = 1;
11
12    // input the total number pushed into the stack(0 < n && n < 20)
13    int n, i, j;
14    cin >> n;
15
16    // run
17    for(i = 2; i <= n; i++)
18    {
19        a[i][0] = a[i - 1][0];
20        for(j = 1; j <= i - 1; j++)
21        {
22            a[i][j] = a[i][j - 1] + a[i - 1][j];
23        }
24        a[i][j] = a[i][j - 1];
25    }
26
27    // ouput the number of possible sequences poped from the stack
28    cout << a[n][n] << endl;
29    
30    return 0;
31}

denote a[n] the number of possible sequences poped from the stack,

denote i the number of the set si poped before the first number pushed '1' poped, 

and denote i the number of the set sj poped after the first number pushed '1' poped,

then we can easily get the conlusion that no number in seti is bigger than any number in setj,

we can depart the sequence into two part and caculate them respectively,

hence the possible number is a[i] * a[j] (0 <= i <= n - 1), i.e.

      a[n] = a[0]*a[n - 1] + a[1]*a[n - 2] + …… + a[n - 2]*a[1] + a[n - 1]*a[0]