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\}\}.$$

  • $\begingroup$ Are you missing a 10th arrangement in your example? Where $A_1=\{1\}$ and $A_2=\{2\}$? $\endgroup$ Oct 11 '20 at 17:43
  • $\begingroup$ Yes you are right. Answer is $10$. $\endgroup$
    – 1ENİGMA1
    Oct 11 '20 at 18:12
  • 1
    $\begingroup$ Cross-posted and answered on MO here. $\endgroup$
    – RobPratt
    Oct 12 '20 at 0:35

A valid split will have $t$ blocks of $k$ consecutive integers and $n-kt$ singletons; for convenience let $m=n-kt$. Then a valid split is completely described by a $(t+m)$-bit string with $t$ ones and $m$ zeroes, in which a $1$ bit represents a block of length $k$, and a $0$ bit represents a singleton. In the example in the question, for instance, the first two splits listed are represented by the strings $11100$ and $11010$, respectively. Clearly there are $\binom{t+m}t=\binom{t+m}m$ such strings and hence the same number of valid splits.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.