I can't find a counting interpretation of this formula. I thought of using the binomial theorem but I don't think it applies here. So, I am not sure how to begin.

  • 1
    $\begingroup$ oeis.org/A072034 $\endgroup$
    – metamorphy
    Mar 21 '21 at 11:32
  • $\begingroup$ @metamorphy I still don't understand. $\endgroup$ Mar 21 '21 at 16:22
  • $\begingroup$ I got a very bad upper bound, something like $O(n^{n^2})$ $\endgroup$
    – Alex
    Mar 21 '21 at 17:56

I will provide a proof of the interpretation that the sum you've given counts the number of functions from $[n]$ to a subset of $[n]$ summed over all possible subsets(mentioned by @metamorphy) and also $[n] = \{1,2,...,n\}$.Consider a function $$ f : [n] \to [i] $$ Each element of $[n]$ has $i$ choices to map to. So there are $i^n$ functions in this case. Also there are $\dbinom{n}{i}$ subsets of $[n]$ of cardinality $i$ from the definition of binomial coefficients. Summing over all possible subsets you get that the number of functions from $[n]$ into a subset of $[n]$ is $$\sum_{i=0}^{n} \binom{n}{i}i^n$$

  • $\begingroup$ hi, why is $n^i$? $\endgroup$ Mar 21 '21 at 16:46
  • $\begingroup$ This is correct, but still I cannot find a good application for it. Any idea or situation where this sum could be useful? $\endgroup$
    – A. Pesare
    Mar 21 '21 at 19:16
  • $\begingroup$ @Strange is not supposed to be $i^n$ instead of $n^i$? $\endgroup$ Mar 21 '21 at 20:40
  • $\begingroup$ If $A\subseteq B\subseteq[n]$, every function from $[n]$ to $A$ is automatically a function from $[n]$ to $B$, so the sum does not count functions from $[n]$ to subsets of $[n]$: it counts ordered pairs $\langle A,f\rangle$ such that $A\subseteq[n]$ and $f:A\to[n]$. $\endgroup$ Mar 21 '21 at 21:40
  • $\begingroup$ Sorry for inconvenience ,corrected it $\endgroup$
    – Strange
    Mar 22 '21 at 2:30

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.