Proof of recursive relationship between binary permutations.

Question

I'm tring to figure out a relationship between binary permutations.

I note $\sigma_{i, k} $ the set of all binary permutations with $i$ $0$ and $k-i$ $1$.

I think it is true to say that : $$\sigma_{i, k+1} = (\{1\}+\sigma_{i, k}) \bigcup (\{0\}+\sigma_{i-1, k}). $$

where $+$ denotes the concatentation (exactly as done in python).

With a binary tree, it is quite intuitive visually but im' struggling to find a formal proof.

Does anyone know a solution or problem related ?

Thank you in advance !

Answer 1

I think I have the solution.

$\{1\}+\sigma_{i,k}$ is the set of all binary permutations of $i$ $0$ among $k+1$ elements begining with $1$.

$\{0\}+\sigma_{i-1,k}$ is the set of all binary permutations of $i$ (the former $i-1$ and the one we added at the begining) $0$ among $k+1$ elements begining with $0$.

We have then that $(\{1\}+\sigma_{i,k})\bigcup (\{0\}+\sigma_{i-1,k})$ is the set of all the permutations of $i$ 0 among $k+1$ elements.