Introduction E9F5FC

Questions FFFFC0

• View
• Edit
• History
• Print

Does the sequence [A074932][1] in Sloane's Online Encyclopedia of Integer Sequences equal this formula?

{$ a(n) = \sum_{i=0}^{n}\sum_{j=0}^{n}\binom{n}{i}\binom{n}{j}i^j $}

I calculated the values {$a(0),\dots,a(8)$} and they match the terms for this sequence.

My formula {$a(n)$} counts the number of functions whose range and domain are subsets of {${1,...,n-1}$}. Which is to say, let {$\mathbf{Set}_n$} be the category whose objects are sets with elements taken from {${1,...,n}$}, and whose arrows are functions from one set to another. Then $2^{n-1}$ counts the number of objects, and $a(n)$ counts the number of arrows.

For example, if n=4, then we can construct the following table illustrating the number of functions possible for various domains and codomains:

{$\begin{matrix} & codomain: \varnothing & \{x\} & \{x,y\} & \{x,y,z\}\\domain: \varnothing & 0^0\equiv 1 & 1^0 & 2^0 & 3^0 \\ \{a\} & 0^1 & 1^1 & 2^1 & 3^1 \\ \{a,b\} & 0^2 & 1^2 & 2^2 & 3^2\\ \{a,b,c\} & 0^3 & 1^3 & 2^3 & 3^3\end{matrix} $}

And by the binomial theorem we count multiplicities (pairs of subsets) as follows:

{$\begin{matrix}1 & 3 & 3 & 1 \\ 3 & 9 & 9 & 3 \\ 3 & 9 & 9 & 3 \\ 1 & 3 & 3 & 1\end{matrix}$}

Multiplying the entries:

{$\begin{matrix}1 & 3\cdot1^0 & 3\cdot2^0 & 1\cdot3^0 \\ 0 & 9\cdot1^1 & 9\cdot2^1 & 3\cdot3^1 \\ 0 & 9\cdot1^2 & 9\cdot2^2 & 3\cdot3^2\\ 0 & 3\cdot1^3 & 3\cdot2^3 & 1\cdot3^3\end{matrix}$}

Adding them all up we get {$a(4)=170$}.

I'm trying to understand the Yoneda lemma. So I'm trying to better understand {$\mathbf{Set}$}, the category of sets. That's why I'm studying {$\mathbf{Set}_n$}. My background is in algebraic combinatorics, so I'm curious what these numbers might mean, where they arise and how they are interpreted.

Curiously, Sloane's encyclopedia doesn't list this sequence $a(n)$ as such but it likely equals A074932, which is gotten by summing the absolute values of the coefficients of the Sidi polynomial as in [this table][2]. I don't know anything about the Sidi polynomial or the Euler derivative. So I'm grateful if somebody might ascertain whether these are the same sequences, and also, explain how and why they are related.

• [1]: https://oeis.org/A074932
• [2]: https://oeis.org/A075513/table

Applying the binomial theorem to the sum over j in your formula results in the first formula listed on the OEIS page. – MTyson