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

combinatoricscomputer sciencepermutations

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.

Best Answer

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$

Related Solutions

[Math] How to partition a set into k subsets, given minimum subset size is limited by some constant

You're looking for triples of three numbers (which I'm going to list in nondecreasing order) that sum to 36, and where each one is at least 5.

Instead you can look for triples of three numbers $p \le q \le r$ that sum to $36 - 15 = 21$, where each is nonnegative, and then the numbers you originally sought were $p+5, q+5, r+5$. (i.e., there's a 1-1 correspondence between the collection of partition-sizes that you seek and the collection of $(p, q, r)$ with $0 \le p \le q \le r$ and $p+q+r = 21$.)

These latter triples can be divided into those with $p = 0$, where the remaining numbers sum to 21; those where $p = 1$, and the remaining numbers sum to $20$...but both are at least $1$, those where $p = 2$, and the remaining numbers sum to $19$, but both are at least $2$, etc.

But the same trick applies to those: pairs of numbers, in nondecreasing order, summing to to $19$, but both being at least $2$ have the same count as pairs of (nondecreasing) numbers, summing to $15$, but both being at least $0$.

Let's write $$ C(n, k) $$ for the number of $n$-element sets of nonnegative numbers, in increasing order, that sum to exactly $k$. Then what I've said above shows that the number you're looking for is $C(3, 21)$, and that

$$ C(3, 21) = C(2, 21) + C(2, 21-3\cdot 1) + C(2, 21-3\cdot 2) + \ldots + C(2, 21-3\cdot 7) $$

Now how large is $C(2, k)$? It, too, satisfies a recurrence: the first number is either $0$ (in which case the remaining number must sum to 21), or it's 1, in which case the remaining number must be at least 1 and sum to 20, i.e., the count of which is the same as numbers that are at least 0 and sum to 19, etc. $$ C(2, k) = C(1, k) + C(1, k-2 \cdot 1) + C(1, k-2 \cdot 2) + \ldots + C(1, k-2 \cdot (k/2)) $$ where the $k/2$ in the last term should be rounded down [i.e., if $k$ is odd, then we end with $C(1, 1)$ rather than $C(1, -1)$. ]

Now how large is $C(1, s)$ for any nonnegative $s$? It's exactly $1$.

That means that $C(2, k)$ is exactly $\lfloor \frac{k+1}{2} \rfloor$.

So $$ C(3, 21) = \lfloor \frac{22}{2} \rfloor + \lfloor \frac{19}{2} \rfloor + \lfloor \frac{16}{2} \rfloor + \lfloor \frac{13}{2} \rfloor + \lfloor \frac{10}{2} \rfloor + \lfloor \frac{7}{2} \rfloor + \lfloor \frac{4}{2} \rfloor + \lfloor \frac{1}{2} \rfloor \\ = 11+9 + 8 + 7 + 5 + 3 + 2 = 45. $$

This seems surprisingly low to me, but I don't see any obvious error (except that my "round down $(k+1)/2$" answer for $C(1, k)$ could be off by one), so I'm going to go ahead and submit it as an answer, and if not an answer, at least a suggested path for you to follow in getting to the correct answer.

Let me just sanity check by writing them down...there aren't that many.

12, 12, 12
11, 12, 13
11, 11, 14
10, 13, 13
10, 12, 14
10, 11, 15
10, 10, 16
9, 13, 14
9, 12, 15
9, 11, 16
9, 10, 17
9, 9, 18
8, 14, 14
8, 13, 15
8, 12, 16
8, 11, 17
8, 10, 18
8, 9, 19
8, 8, 20
7, 14, 15
7, 13, 16
7, 12, 17
7, 11, 18
7, 10, 19
7, 9, 20
7, 8, 21
7, 7, 22
6, 15, 15
6, 14, 16
6, 13, 17
6, 12, 18
6, 11, 19
6, 10, 20
6, 9, 21
6, 8, 22
6, 7, 23
6, 6, 24

Hunh. I seem to get 38. So I probably DID have an off-by-one error in my formula for $C(2, k)$. Anyhow, the answer is 38, and you can work out my off-by-one error by back-tracing, if it pleases you do to so.

Breaking a set into continuous subsets such that number of $1$’s are greater than number of $0$’s

I think you want to use a recursive algorithm. Call a sublists starting at $B[1]$ a "prefix" and a sublist ending at $B[N]$ a "suffix." For each possible way of diving the list into a suffix and a prefix, if the prefix is heavy, recursively count the number of ways of dividing the suffix into heavy sublists. (Remember to count the division into just the suffix itself.) Add up all of these, and add $1$, for the division consisting of just the original list.

Best Answer

Related Solutions

[Math] How to partition a set into k subsets, given minimum subset size is limited by some constant

Breaking a set into continuous subsets such that number of $1$’s are greater than number of $0$’s

Related Question