# Combinatorial Mystery Function

Has anyone heard of a function $f$: $\mathbb{Z}^{n^+} \to \mathbb{Z}^{n^+}$, such that if $S= \{{a_1,a_2,...,a_n}\},f(S):=\sum\limits_{s_k \subset S, |s_k|=n-1,s_k \not= s_j} f(s_k)$ and $f(n)=n$? For example, $f(1,2,3)=f(1,2)+f(2,3)+f(3,1)=f(1)+f(2)+f(2)+f(3)+f(3)+f(1)=12.$ It is obvious that with k distinct elements we have $f(a_1,a_2,...,a_k)=(k-1)!\sum\limits_{n=1}^k a_n$ but it gets trickier with more variance. $f(1,1,2,3)=f(1,2,3)+f(1,1,2)+f(1,1,3)=12+1+3+1+4=21$.

I'm just having trouble pinning this function down. I hope you can forgive my slightly abusive notation.

-
I'm not sure I understand your definition. Is your function defined to be $\{a\} = a$ for one argument, $\{a,a,\ldots,a\} = \{a\}$ for all equal arguments, and $\{a_1,a_2,\ldots,a_n\} = \{a_2,\ldots,a_n\} + \{a_1,a_3,\ldots,a_n\} + \cdots + \{a_1,a_2,\ldots,a_{n-1}\}$ otherwise? –  Rahul Narain Apr 25 '12 at 3:43
@Rahul, not quite. That would give $f(1,1,2,3)=f(1,2,3)+f(1,2,3)+f(1,1,3)+f(1,1,2)$ but since two of the terms on the right are identical you only include one of them. $f(1,1,2,3)=f(1,2,3)+f(1,1,3)+f(1,1,2)$. –  Gerry Myerson Apr 25 '12 at 4:10
You could start with giving a proper definition of your function: state its domain and codomain (the latter is probably the natural numbers), and say what value it takes at an arbitrary element of its domain. Also choose a better notation than braces, which is very confusing when you are in fact dealing with sets. –  Marc van Leeuwen Apr 25 '12 at 9:13
Thanks! I fixed the abusive notation. –  Alexander L Apr 26 '12 at 2:54
I doubt there's a useful formula covering all cases. Perhaps you could work it out for some special cases such as $f(a,a,b,b,c,c,\dots,z,z)$ and $f(a,a,\dots,a,b,b,\dots,b)$. –  Gerry Myerson Apr 26 '12 at 6:00

If your set contains $a_1, \dots, a_m$ with multiplicities $e_1, \dots, e_m$ respectively, your function gives
$$\begin{multline} \sum_{k}\binom{e_1+e_2+\dots + e_m -1}{e_1,e_2,\dots,e_{k-1},e_k-1,e_{k+1},\dots,e_m}a_k \\ = \frac{1}{e_1+e_2+\dots+e_m}\binom{e_1+e_2+\dots + e_m}{e_1,e_2,\dots,,e_m} \sum_{k}a_ke_k, \end{multline}$$
which can be verified (preferably in the first form) by induction or by counting how many ways there are to reduce the multiset to a singleton $a_k$.
I was confused at first about the notation, so I sat down and tried again and got $\frac{(e_1+e_2+...+e_n -1)!}{e_1!e_2!...e_n!}$. Which I'm guessing is the same as your result. Thanks! –  Alexander L Apr 27 '12 at 4:13