if a cage can hold two or one dog and you have x dogs and no shortage cages. then how to get number of combinations in which dogs can be arranged Suppose you have $x$ dogs and you are not short of cages (max cages required will be $x$). You can put either one dog or two dogs in a cage. So, how many combinations can be made with $x$ dogs?

For ex: You have $3$ dogs then total combination will be 4
  1 2 3
  (1 2) 3
  1 (2 3)
  (1 3) 2
  like wise 4 will be 10
  & 5 will be 26 and so on

so i tried and came with this:
1 + n*(n-1)/2 + n*(n-1)*(n-2)*(n-3)/23 + n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)/24 + ...
but this gives the wrong answer from 6 and beyond
so please can anyone help me solve it.
 A: For $x$ dogs, pick how many two-dog cages are needed.  This will range from $0$ to $\left\lfloor\frac{x}{2}\right\rfloor$.  Let us call the number of two-dog cages used $k$.
Given that we are using $k$ two-dog cages, pick which $2k$ dogs are being placed into two-dog cages.  Then, sort these dogs according to an arbitrary order (e.g. by number)
Next, among all dogs designated to be put in two-dog cages pick who is put in the cage with the smallest dog.  Next, pick who is put in the cage with the now smallest remaining dog.  Repeat this process until all dogs designated to be put into two-dog cages have their partners selected.
Ranging over all values of $k$ we have as a result:
$$1+\sum\limits_{k=1}^{\left\lfloor\frac{x}{2}\right\rfloor}\binom{x}{2k}(2k-1)!!$$
(double factorial notation $n!!=n(n-2)(n-4)(n-6)\cdots(2~\text{or}~1~\text{depending on if $n$ is even or odd})$.  For example $6!!=6\cdot 4\cdot 2$ and $9!!=9\cdot 7\cdot 5\cdot 3\cdot 1$)
(edit: changed index to start from $k=1$ instead to avoid having to deal with attempting to define $(-1)!!$ as equalling $1$ or using more complicated methods to write out the product)

As for an alternate solution, from the comments above we can follow the links and eventually arrive to the page for telephone numbers(mathematics) which are exactly those values you are wishing to calculate which yields some other rather nice ways to calculate the number.
One such method that they exhibit is that of recurrence relations.
$T(0)=1,T(1)=1$ and $T(n)=T(n-1)+(n-1)T(n-2)$ for all $n\geq 2$
The idea being that assuming we know the value $T(k)$ for all $k<n$, to find $T(n)$ our $n$'th dog can either be in a cage by himself which can be accomplished in $T(n-1)$ ways, or our $n$'th dog can be in a cage with another dog.  Pick which dog that is, and then the remaining $n-2$ dogs can be arranged in $T(n-2)$ ways.
