# Combinatoric problem

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

• Are you missing a 10th arrangement in your example? Where $A_1=\{1\}$ and $A_2=\{2\}$? Oct 11 '20 at 17:43
• Yes you are right. Answer is $10$. Oct 11 '20 at 18:12
• Cross-posted and answered on MO here. 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.