Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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
For reference: The wikipedia page on multinomial coefficients… – Phira Apr 30 '12 at 20:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.