# Find a map on a power set with certain combinatorial properties

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.

• Do you mean $c: \mathcal{P}\{1,2,\dots,k\} \to \mathbb{Q}$? Jul 22 '16 at 15:37
• Absolutely, thanks! 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\})=c(\{1\})+c(\{2\})$$

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

$$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\})$$

• 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? Jul 22 '16 at 15:53
• @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. Jul 22 '16 at 16:01
• Thanks, I have done so: math.stackexchange.com/questions/1867713/… Jul 22 '16 at 16:29