# Find an explicit map 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,\nu-1\}) + c(\{\nu+1,\dots,j\} ) \quad \forall i \leq j \in \{1,2,\dots,k\} \ .
\end{align*}

I am searching for an explicit description of a map with these properties. I have tried to define such a map using factorials and binomial coefficients.

(This is a more special version of a map I was searching for in this earlier question: Find a map on a power set with certain combinatorial properties )

#### Solutions Collecting From Web of "Find an explicit map with certain combinatorial properties"

Let’s make the additional assumption that $c(S)$ depends only on the size of $S$. Let $c_\ell=c(S)$ for any set $S$ with $\ell$ elements.

This is already enough to allow us to compute $c_\ell$ for any $\ell$. To find an explicit formula, notice that, for $\ell \geq 2$, we have
$$c_\ell=2c_{\ell-1} + 2 \sum_{n=0}^{\ell-2}c_n = 3c_{\ell-1}$$
$$c_\ell=3^{\ell -1} c_1 = 2 \cdot 3^{\ell-1}$$
for all $\ell \geq 1$.