Help proving this combinatorics identity Suppose $I_{N} := \{1,...,N\}$, $N \ge 1$, is a subset of $\mathbb{N}$ and $\mathcal{P}(I_{N})$ denotes the set of all subsets of $I_{N}$. Suppose we have a family of objects $\{f_{X}\}_{X\in \mathcal{P}(I_{N})}$ and $\{g_{X}\}_{X\in \mathcal{P}(I_{N})}$ such that $f_{\emptyset} = 1$, $g_{\emptyset} = 0$ and:
$$f_{X} = \sum_{\substack{Y \subset X \\ \text{min}X \in Y}}g_{Y}f_{X\setminus Y}$$
with $\text{min}X$ denoting the minimum element of $X$. I want to prove that:
$$f_{X} = \sum_{n\ge 1}\frac{1}{n!}\sum_{\substack{\Pi_{1},...,\Pi_{n}\neq \emptyset \\ \Pi_{1}\cup \cdots \cup \Pi_{n} = X}}\prod_{i=1}^{n}g_{\Pi_{i}}$$
where, in the above we have a sum of partitions of $X$ (thus, the unions are disjoint).
I tried using induction, but got nowhere. Of course, if $|X| =1$, the second formula leads $f_{X} = g_{X}$ which coincides with the first one. However, assuming the formula holds for some $|X'| = k < N$, I could not prove the general formula for $f_{X}$ with $|X| = k+1$ because I don't know how the formulas change when $f_{X'}$ is changed to $f_{X'\cup \{x\}} = f_{X}$. Maybe there is a better way of proving it, which I can't figure out.
 A: Use Strong induction noticing that $Y\neq \emptyset$ and so $|X\setminus Y|<|X|$. The induction step looks like
$$f_X=\sum _{\substack{Y\subset X\\ \min {X}\in Y}}g_Yf_{X\setminus Y}=g_Xf_{\emptyset}+\sum _{\substack{Y\subset X\\ \min {X}\in Y}}g_Y\sum _{n\geq 1}\frac{1}{n!}\sum _{\{\Pi _1,\cdots ,\Pi_n\}\vdash X\setminus Y}\prod _{i=1}^n g_{\Pi _i},$$
exchanging the first two sums, we get
$$f_X=g_Xf_{\emptyset}+\sum _{n\geq 1}\frac{1}{n!}\sum _{\substack{Y\subset X\\ \min {X}\in Y}}\sum _{\{\Pi _1,\cdots ,\Pi_n\}\vdash X\setminus Y}g_Y\prod _{i=1}^n g_{\Pi _i}.$$
but consider a partition of $X$ given by $\{\Pi_1,\cdots ,\Pi_n,Y\}$ notice that $Y$ has not an index associated to it, so there are $n+1$ choices for it and so we conclude that we are adding $\frac{1}{n+1}$ of considering all possible choices of indexing for $Y$ and every partition can be founded that way, this gives us $$\sum _{\substack{Y\subset X\\ \min {X}\in Y}}\sum _{\{\Pi _1,\cdots ,\Pi_n\}\vdash X\setminus Y}g_Y\prod _{i=1}^n g_{\Pi _i}=\frac{1}{n+1}\left (\sum _{\{\Pi _1,\cdots ,\Pi_{n+1}\}\vdash X}\prod _{i=1}^{n+1} g_{\Pi _i}\right ).$$ Plugging it in the expression above, we get
$$f_X=g_Xf_{\emptyset}+\sum _{n\geq 1}\frac{1}{n!}\frac{1}{n+1}\left (\sum _{\{\Pi _1,\cdots ,\Pi_{n+1}\}\vdash X}\prod _{i=1}^{n+1} g_{\Pi _i}\right )=\underbrace{g_X\cdot 1}_{\text{expr. for }n=1}+\sum _{n\geq 2}\frac{1}{n!}\sum _{\{\Pi _1,\cdots ,\Pi_{n}\}\vdash X}\prod _{i=1}^{n} g_{\Pi _i},$$
getting your identity
$$f_X=\sum _{n\geq 1}\frac{1}{n!}\sum _{\{\Pi _1,\cdots ,\Pi_{n}\}\vdash X}\prod _{i=1}^{n} g_{\Pi _i}$$
