3
$\begingroup$

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.

  • 0
    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)$.2012-04-26

1 Answers 1

2

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 have not heard about it, though.

  • 0
    For reference: The wikipedia page on multinomial coefficients http://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients2012-04-30