Partition of set with $N$ integers such that each subset has length less $K$.

Question

You are given numbers $N$ and $K$. Consider the set $S = {1, 2, 3,\ldots , N}$. An ordered tuple is a sequence of integers from this set. For example, $(2, 4, 1)$ is a tuple, and it is different from $(1, 2, 4)$. You need to partition the integers ${1, 2, 3, . . . , N}$ into ordered tuples such that each tuple has at most $K$ integers. That is, you need to get a set of tuples, such that each element of $S$ is in exactly one tuple, and each tuple has at most $K$ elements. Find the number of ways to do so.

Note that elements inside a single tuple cannot be reordered. But tuples can be reordered as a whole. For instance, if $N = 3$ i.e., $S = \{1, 2, 3\}$ — then $\{ (2, 3),(1) \}$ and $\{ (1),(2, 3) \}$ are considered the same partitions. But $\{ (3, 2),(1) \}$ is a different partition.

For example, if $N = 2$ and $K = 2$, there are exactly $3$ valid ways to partition $S$, as given below:

• $\{ (1),(2) \}$

• $\{ (1, 2) \}$

• $\{ (2, 1) \}$

Compute the number of ways to partition ${1, 2, 3,\ldots , N}$ into ordered tuples of size at most $K$ for the following instances.

$(a) N = 4,\, K = 3$

$(b) N = 5,\, K = 3$

$(c) N = 6,\, K = 3$

Answers are : $(a)\, 49 ,\, (b)\, 261,\, (c)\, 1531$

My Attempt:

I am bad at explaining but here we go.

What I attempted to do was partition $N$ into parts such that each is less than $K$.

I got $3$ such partitions for $N = 4$, $K = 3$ :

• $(2, 2)$
• $(1, 1, 2)$
• $(3, 1)$

Then there were $N!$ such ways to place the numbers into these partitions. This gives me the answer: $$4! \cdot 3 = 72$$

However that logic seems to be wrong. Can anyone suggest a better path?

(source) [$Q4$ ZIO-$2018$ India$]$

---

This is the first question that I am asking on Math.SE. I am sorry if I am being too direct in asking the question.

Answer 1

Letting $f(n,k)$ be the number of ways, a better path to compute $f(n,k)$ is recursively. Specifically, $$ f(n,k) = \binom{n-1}0\cdot 1!\cdot f(n-1,k) +\binom{n-1}1\cdot 2!\cdot f(n-2,k) + \dots+\binom{n-1}{k-1}\cdot k!\cdot f(n-k,k) $$ This follows by conditioning on the number of elements in the tuple containing $n$.

To see this in action:

• $f(0,3) = 1$. (There is nothing to partition, so there is only the empty partition).

• $f(1,3) = \binom{0}{0}1!f(0,3)=1.$

• $f(2,3) = \binom{1}01!f(1,3)+\binom{1}1\cdot 2!f(0,3)=1\cdot 1+2\cdot 1=3$

• $f(3,3) = \binom{2}01!f(2,3) +\binom212!f(1,3)+\binom223!f(0,3)=1\cdot 3+4\cdot 1+6\cdot 1=13$.

• $f(4,3) = \binom301!f(3,3)+\binom312!f(2,3)+\binom323!f(1,3)=1\cdot 13+6\cdot 3+18\cdot 1=49.$

• $f(5,3) = \binom401!f(4,3)+\binom412!f(3,3)+\binom423!f(2,3)=1\cdot 49+8\cdot 13+36\cdot 3=261.$

Answer 2

The number of ways to assign the numbers to the partitions is much more complicated than that.

For $3,1$ there are $4!$ ways to assign them because each location is distinct.

For $1,1,1,1$ (which you missed) there is only one way to assign them because you are allowed to reorder the partitions.

For $2,2$ there are $12$ ways to assign them because you can assign the first in $12$ ways, the second in two ways, but you can swap the two pairs.

Finally for $1,1,2$ (you had an extra $1$) there are $12$ ways to choose the $2$, but the $1$s are then set.

This gives the desired $49$ ways.

Your approach of $N!$ times the number of partitions of $N$ into parts of at most $K$ is close. Each one just needs to be divided by the factorial of the number of matching parts. For $N=6,K=3$ the partition $(3,3)$ contributes $\frac {6!}{2!}$, the partition $(2,2,2)$ contributes $\frac {6!}{3!}$ and $(2,2,1,1)$ contributes $\frac {6!}{2!2!}$

Answer 3

Your main problem is the distinct tuples of the same size are not ordered. So the partition $\{(1,2),(3,4)\}$ is the same as the partition $\{(3,4),(1,2)\}$.

Your second problem is that you wrote down the partitions wrong. $1,1,1,2$ adds to $5$, not $4$, and you missed the trivial partition $1,1,1,1$. So the complete list:

• $1,1,1,1 \to 4!/4! = 1$ way
• $1,1,2 \to 4!/2! = 12$ ways
• $2,2 \to 4!/2! = 12$ ways
• $3,1 \to 4! = 24$ ways

Total : $49$