Find a map on a power set with certain combinatorial properties

72 Views Asked by At

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.

1

There are 1 best solutions below

3
On BEST ANSWER

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