Prove that the total number of arrangements of objects by taking any number of objects from $n$ different objects is $\lfloor e \times n! - 1 \rfloor$, where $e$ is the natural base.

I tried it by making cases that either we choose $1$ object in $\dbinom {n}{1} $ way and arrange it in $1$ way or two objects and so on, obtaining $$ \sum_{r=0}^n \dbinom {n}{r} \times r! $$

However, the quantity that we have to prove it equal to is entirely different.

Any help will be appreciated.

  • 2
    $\begingroup$ You should perhaps include the term where $r=0$. $\endgroup$ – hardmath Jul 4 '15 at 15:31

Hint: write the terms in your sum as $n!$ times something. Note that the sum of the somethings is close to the power series for $e$

  • $\begingroup$ The sum can be written as $n! \times \displaystyle \sum_{r=0}^n \dfrac {1}{(n-r)!} $ But how is this equal to $\lfloor e \times n! -1 \rfloor $ ? $\endgroup$ – Henry Jul 4 '15 at 17:16
  • $\begingroup$ $\sum_{r = 0}^n \frac{1}{(n-r)!} = \sum_{k = 0}^n \frac{1}{k!}$, which is surprisingly close to $\sum_{k = 0}^\infty \frac{1}{k!}$ $\endgroup$ – Austin Mohr Jul 4 '15 at 17:33
  • $\begingroup$ @AustinMohr Yes, I do realize that it is the Mc' Laurin series for $e$, but why is it exactly equal to $\lfloor e \ n! - 1 \rfloor $ and not some other quantity like $\lfloor e \ n! - 2 \rfloor $ Where did that $-1$ come from ? $\endgroup$ – Henry Jul 4 '15 at 17:49
  • 1
    $\begingroup$ The -1 comes from the fact that your original sum started at $r=1$. I believe that was the correct reading of the problem. You do not count the empty set as a subset for this purpose. If you do count it, the $-1$ goes away. $\endgroup$ – Ross Millikan Jul 4 '15 at 23:09

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.