提示: 欢迎访问OurACM平台。
Problem 1570 集合划分问题

Accept: 405    Submit: 1166
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

n个元素的集合{1,2,...,n}可以划分若干个非空子集。例如,当n=4时,集合{1,2,3,4}可以划分为15个不同的非空子集如下:

 
{{1},{2},{3},{4}},
{{1,2},{3},{4}},
{{1,3},{2},{4}},
{{1,4},{2},{3}},
{{2,3},{1},{4}},
{{2,4},{1},{3}},
{{3,4},{1},{2}},
{{1,2},{3,4}},
{{1,3},{2,4}},
{{1,4},{2,3}},
{{1,2,3},{4}},
{{1,2,4},{3}},
{{1,3,4},{2}},
{{2,3,4},{1}},
{{1,2,3,4}}

给定正整数n(1<=n<=20),计算出n个元素的集合{1,2,...,n} 可以化为多少个不同的非空子集。

Input

多组输入数据,每组数据1行,表示元素个数n.

Output

对于每组数据,输出一行一个数,表示不同的非空子集的个数。

Sample Input

2 4

Sample Output

2 15

Source

FOJ月赛-2008年3月

Submit  Back  Status  Discuss