Let A be a set, let n be a natural number and let $\langle B_0,B_1,...,B_{n-1} \rangle$ series with $n$ length of subsets of set A. We say $\langle B_0,B_1,...,B_{n-1} \rangle$ is dismental of set A if satisfies the following conditions:
$\bigcup \{B_i:i\in \Bbb{N}^{<n}\}=A$
$\forall{i,j} \in \Bbb{N}^{<n}$ if $i\neq j$ then $B_i \cap B_j = \emptyset$
The question:
Let $n,k$ be natural numbers and let $A$ be a set with $k$ elements. How many $n$-dismentals of $A$ exists? prove your answer.
EDITED: It is not forbidden to use $\emptyset$ than once, for example: $\langle \{2 \},\{1,3\} \rangle$ , $\langle \{1,3 \},\{2\} \rangle$ and $\langle \{1,2,3 \}, \emptyset \rangle$ are three examples of 2-dismentals of $A=\{1,2,3\}$. One more example, $\langle \{4 \},\emptyset,\{5\} \rangle$ and $\langle \emptyset,\emptyset,\{4,5\} \rangle$ are two examples of 3-dismentals of $A=\{4,5\}$
According to drhab solution, We will prove using induction that $n^k$ is the answer.
Claim: For all k and for all n exists $n^k$ dismentals of set A.
Proof: We will prove by induction method on number of the elements in A. i.e $|A|=k$. Let k is a natural number.
- Base case k=0:
Let n a natural number, then exists $n^0=1$ dismentals of A. so A is an emptyset then we could have in a series just an emptyset in each dismentals. each element will be an emptyset for n-dismentals.
- Induction step:
We assume our claim is correct for |A|=k and will prove it for |A|=k+1. let n be a natural number. if n<=k then we mark set $Z=A - \{n\}$. According to our assumption exists $n^k$ dismentals of A and $A=Z\cup \{n\}$ so for since $\{n\}$ we got this is true for $n^{k+1}$.
My questions is:
In case n>k, how can we end the proof?
Is it correct to formulate the claim as I wrote? i.e for all k, for all n.....
My first thinking:
Let $p_{n,k}$ denote the number of $n$-dismentals of set $A$ that has $k$ elements.
Then evidently: $$p_{1,k}=1\tag1$$
Next to that we have:$$p_{n+1,k}=\sum_{i=0}^k\binom{k}{i}p_{n,k-i}\tag2$$
To understand: if $B_n$ is taken to be a set that has $i$ elements then here are $\binom{k}{i}$ choices for $B_n$ and $\langle B_0,\dots,B_{n-1}\rangle$ must be a dismental of the set $A-B_n$ that has $k-i$ elements. There are $p_{n,k-i}$ such dismentals.
Question is now: can we find a closed form for $p_{n,k}$ on base of $(1)$ and $(2)$?
Looking at it for small $k$ a conjecture arises, and it is indeed easy to prove with induction that:$$p_{n,k}=n^k\tag3$$
This makes me think that a more elegant route must exist, and giving it a second thought in this light I found the answer under the line:
My second thinking:
Constructing a $n$-dismental $\langle B_0,\dots,B_{n-1}\rangle$ of $A$ boils down to dividing the set $A$ in $n$ disjoint and covering subsets (why on earth didn't I see that immediately...). That means that for each of the $k$ elements of $A$ there are $n$ choices. That tells us immediately that $(3)$ is correct.
addendum:
Induction works like this.
Let $E(n)$ be the statemement that $p_{n,k}=n^k$ for every nonnegative integer $k$.
Then $E(1)$ is true according to $(1)$.
It remains to be proved that $E(n)\implies E(n+1)$.
If for every nonnegative integer $k$ indeed $p_{n,k}=n^k$ (i.e. $E(n)$ is a true statement) then for an arbitrary fixed $k$ we find: $$p_{n+1,k}=\sum_{i=0}^k\binom{k}{i}p_{n,k-i}=\sum_{i=0}^k\binom{k}{i}n^{k-i}=\sum_{i=0}^k\binom{k}{i}1^kn^{k-i}=(n+1)^k$$and conclude that $E(n+1)$ is a true statement.