The following combinatorial problem popped up in a totally uncombinatorial context:

Let $\mathcal{P}$ denote the power set of a set and let $k \in \mathbb{N}$. Is there a map $c: \mathcal{P}(\{1,2,\dots,k\}) \to \mathbb{Q}$ with the following properties: \begin{align*} &c(\emptyset)=1 \ , \\ &c(\{i,i+1,\dots,j\}) = \sum_{\nu=i}^{j} c(\{i,i+1,\dots,j\} \setminus \{\nu\}) \quad \forall i \leq j \in \{1,2,\dots,k\} \ . \end{align*}

I have tried to define such a map using factorials and binomial coefficients, but have ultimately failed with each attempt. The existence of such a map would suffice, though an explicit definition of $c$ would be very helpful as well.

  • 2
    $\begingroup$ Do you mean $c: \mathcal{P}\{1,2,\dots,k\} \to \mathbb{Q}$? $\endgroup$
    – solstafir
    Jul 22 '16 at 15:37
  • $\begingroup$ Absolutely, thanks! $\endgroup$ Jul 22 '16 at 15:48

Let's assume that the second condition holds for all subsets, that is

$$c(X)=\sum\limits_{x\in X}c(X \setminus \{x\})$$

for all $X \subset \{1,2,\dots ,k\}$.

By the definition of this map and induction, it is completely determined by it's values on one-element sets. Now, consider



$$c(\{1,2,3,4\})=c(\{2,3,4\})+c(\{1,3,4\})+c(\{1,2,4\})+c(\{1,2,3\})=\\ =6\cdot\big[c(\{1\})+c(\{2\})+c(\{3\}+c(\{4\})\big]$$

It is easy to prove by induction that $$c(X)=(|X|-1)!\sum\limits_{x\in X}c(\{x\})$$

  • $\begingroup$ Thank you! I just realized that the conditions I wrote down are not strong enough for my purposes... The second condition should actually be replaced by $$c(\{i,i+1,\dots,j\})= \sum_{\nu=i}^j (c(\{i,i+1,\dots,\nu-1\})+c(\{\nu+1,\dots,j\})) \quad \forall i \leq j \ , $$ which unfortunately doesn't work with the map you described. Since I put no condition on the map on sets which are not of the form $\{i,i+1,\dots,j\}$, there might be hope? $\endgroup$ Jul 22 '16 at 15:53
  • 1
    $\begingroup$ @Feldweg The same trick (describing in terms of values on one-element sets) should work, but the formulas seem to get a bit tougher. Probably it'd be best to make a separate question. $\endgroup$
    – lisyarus
    Jul 22 '16 at 16:01
  • $\begingroup$ Thanks, I have done so: math.stackexchange.com/questions/1867713/… $\endgroup$ Jul 22 '16 at 16:29

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.