1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I'm guessing by your example the dogs can be distinguished ? $\endgroup$ – user451844 Aug 12 '17 at 20:21
  • $\begingroup$ misleading question if you have infinitely many cages than there are infinitely many arrangements.Do you want to say that we can use as many cages as we want until all the dogs are placed? $\endgroup$ – Deepesh Meena Aug 12 '17 at 20:22
  • $\begingroup$ @James presumably he intends that all cages are indistinguishable and that all dogs must go into a cage. $\endgroup$ – JMoravitz Aug 12 '17 at 20:25
  • $\begingroup$ @James I agree with you. If what JMoravitz is saying is true then that should be reflected in the OP. $\endgroup$ – Math Lover Aug 12 '17 at 20:27
  • $\begingroup$ en.wikipedia.org/wiki/Young_tableau#Tableaux ... oeis.org/A000085 $\endgroup$ – Donald Splutterwit Aug 12 '17 at 20:43
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @paw88789 it should come out to $1$ in the actual counting. I don't recall if $(-1)!!$ is actually defined as equalling $1$ (in much the same way that $0!=1$) but split off the $k=0$ term just to avoid the ambiguity. $\endgroup$ – JMoravitz Aug 12 '17 at 20:36
  • $\begingroup$ is that x/2k if it is x/2k then for 3 it will be giving a fraction which would be wrong $\endgroup$ – TubbyStubby Aug 12 '17 at 20:40
  • $\begingroup$ @TubbyStubby $\binom{x}{2k}$ is the binomial coeficcient. $\binom{x}{2k}=\frac{x!}{(2k)!(x-2k)!}$ and is certainly never a fraction. $\endgroup$ – JMoravitz Aug 12 '17 at 20:40
  • $\begingroup$ oh so it is <sup>x</sup>C<sub>2k</sub> $\endgroup$ – TubbyStubby Aug 12 '17 at 20:45
  • $\begingroup$ @TubbyStubby That is a rather messy notation to use which I discourage, but yes... that is how some textbooks notate it. $\endgroup$ – JMoravitz Aug 12 '17 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.