Solution Found!
Let S be a given set. If, for some k > 0, S1, S2,......Sk
Chapter 2, Problem 8TE(choose chapter or problem)
Problem 8TE
Let S be a given set. If, for some k > 0, S1, S2,......Sk are mutually exclusive nonempty subsets of S such that
, then we call the set {S1,S2,... ,Sk} of a partition of S. Let Tn denote the number of different partitions of {1,2,.. n} Thus, T1 = 1 (the only partition being S1 = {1}) and T2= 2 (the two partitions being {{1,2,}}, {{1}, {2}}).
(a) Show, by computing all partitions, that T3 = 5, T4= 15.
(b) Show that
and use this equation to compute T10
Questions & Answers
QUESTION:
Problem 8TE
Let S be a given set. If, for some k > 0, S1, S2,......Sk are mutually exclusive nonempty subsets of S such that
, then we call the set {S1,S2,... ,Sk} of a partition of S. Let Tn denote the number of different partitions of {1,2,.. n} Thus, T1 = 1 (the only partition being S1 = {1}) and T2= 2 (the two partitions being {{1,2,}}, {{1}, {2}}).
(a) Show, by computing all partitions, that T3 = 5, T4= 15.
(b) Show that
and use this equation to compute T10
ANSWER:
Step 1 of 2
(a)
Let \(S\) be a given set. If, for some \(k>0, S_{1}, S_{2}, \ldots \ldots \ldots . S_{k}\) are mutually exclusive nonempty subsets of \(S\) such that
\(\bigcup_{i=1}^{k} S_{i}=S\)
Let \(T_{n}\) denote the number of different partitions of \(1,2,3, \ldots \ldots, n\).
Thus, \(T_{1}=1\) (the only partition being \(S_{1}=\{1\}\) ) and \(T_{2}=2\) (the two partitions being \(\left.S_{1}=\{\{1,2,\}\},\{\{1\},\{2\}\}\right)\),
We are asked to compute all partitions that \(T_{3}=5, T_{4}=15\).
\(T_{3}=5\)
The five partitions \(T_{3}=5\) by considering all partition of the elements \(\{1,2,3\}\)
\(\{\{1,2,3\}\},\{\{1\},\{2\},\{3\}\},\{\{1\},\{2,3\}\},\{\{2\},\{1,3\}\},\{\{3\},\{1,2\}\}\)
Giving a count of five different partitions.
The five partitions \(T_{4}=15\) by considering all partition of the elements \(\{1,2,3,4\}\)
\(\{\{1\},\{2\},\{3\},\{4\}\},\{\{1,2,3,4\}\},\{\{1\},\{2,3,4\}\},\{\{2\},\{1,3,4\}\},\{\{3\},\{1,2,4\}\}\)
\(\{\{4\},\{1,2,3\}\}, \ldots \ldots \ldots \ldots .,\{\{1,2\},\{3,4\}\}\)
Giving a count of fifteen different partitions.