-2
$\begingroup$

Let $2\leq k\leq r\leq n$ are positive integers and $r=kt$. I construct sets such that $\cup_{i=1}^n A_i=\{1,2,3,\dots,n\}=X$, this union is disjoint and if $x\in A_i$ and $y\in A_j$ for all $i\leq j$, then $x<y$. I put one condition such that any $t$ sets will contain $k$ elements and the others will be single elements. How can I count the number of such sets?

Example: Let $n=8$, $r=6$, $k=2$ and since $r=kt$, $6=23$, $t=3$. then We can spilts $9$ different ways with above conditions as in the following: $$1=\{A_1=\{1,2\},A_2=\{3,4\},A_3=\{5,6\},A_4=\{7\},A_5=\{8\}\}$$ $$2=\{A_1=\{1,2\},A_2=\{3,4\},A_3=\{5\},A_4=\{6,7\},A_5=\{8\}\}$$ $$3=\{A_1=\{1,2\},A_2=\{3,4\},A_3=\{5\},A_4=\{6\},A_5=\{7,8\}\}$$ $$4=\{A_1=\{1,2\},A_2=\{3\},A_3=\{4,5\},A_4=\{6,7\},A_5=\{8\}\}$$ $$5=\{A_1=\{1,2\},A_2=\{3\},A_3=\{4,5\},A_4=\{6\},A_5=\{7,8\}\}$$ $$6=\{A_1=\{1,2\},A_2=\{3\},A_3=\{4\},A_4=\{5,6\},A_5=\{7,8\}\}$$ $$7=\{A_1=\{1\},A_2=\{2,3\},A_3=\{4,5\},A_4=\{6,7\},A_5=\{8\}\}$$ $$8=\{A_1=\{1\},A_2=\{2,3\},A_3=\{4,5\},A_4=\{6\},A_5=\{7,8\}\}$$ $$9=\{A_1=\{1\},A_2=\{2,3\},A_3=\{4\},A_4=\{5,6\},A_5=\{7,8\}\}.$$

$\endgroup$

1 Answer 1

1
$\begingroup$

Because $t$ sets contain $k$ elements each, there are $n-kt$ singletons and $t+n-kt$ sets overall. Each partition is completely determined by choosing the $t$ sets, and there are $\binom{t+n-kt}{t}$ ways to do that. For your example, this is $$\binom{3+8-6}{2}=\binom{5}{2}=10.$$ You are missing the one with $A_1=\{1\}$ and $A_2=\{2\}$.

$\endgroup$
1
  • $\begingroup$ thank you very much. $\endgroup$
    – 1Spectre1
    Commented Oct 11, 2020 at 17:06

Not the answer you're looking for? Browse other questions tagged .