Find total number of groups formed

198 Views Asked by At

This is smaller problem of a bigger question.

Example:
if $N= 3$,

then answer is $5$ as groups would be $\{(1),(2),(3)\},\{(1),(2,3)\},\{(1,2),(3)\},\{(1,3),(2)\},\{(1,2,3)\}$

Problem I am facing $\to$ To make a generalized formula for this?

with $n=1$ it is $1$, i.e. $\{(1)\}$

with $n=2$ it is $2$ i.e. $\{(1),(2)\},\{(1,2)\}$, i.e. $2$ can either be clubbed with $1$ or taken separately in $\{(1)\}$

with $n=3$, it is $5$, i.e. $3$ can either be clubbed with $1$ or with $2$ or taken separately in its first grouping in $n=2$ taken separately or with $(1,2)$ in its second grouping

with $n=4$, it is $15$. I cannot make out generalized formula for this.