disclaimer first: i’m not a mathematician, so everything i say here might be incredibly wrong and/or obsolete. i just think this whole topic is really interesting and wanted to share my thoughts.

this weekend i thought about my job and the fact that my employer is merging with another company. this way i ended up in a huge developer team (or ‘pool’ as we call it) of 30 developers with just two team leads (disclaimer: i’m not one of them) that one way or another need to lead those thirty people. now how do you keep up with all work-related and also semi-personal relations in such big teams? it’s impossible to have one on ones with everyone each week - but huge team meetings with all 30 people end up in absolute chaos if not strictly moderated which might leave some colleagues unhappy.

then i remembered maths. seriously. i remembered partitions (of a set)[0]. considering $M$ as the set of all developers, we want to find an $n$ and an $m$ to which all arbitrarily fixed-size (with $n$ being the size of a partition and $m$ being the amount of partitions) partitions of $M$ that are minimal for a given $M, n, m$[1]. so in short: we want the difference between $n$ and $m$ be as small as possible.

so practically this is really easy: since we’ve got a set with a cardinality of 30, we can either take 5 partitions with a size of 6 or vice versa. but is there an efficient algorithm or formula to describe this? i probably slept through my math classes in university and/or forgot about it, but this can’t be a new problem, could it?

that was the first problem, the second would be: consider shuffling (randomly or manually) the elements of each partition - we have two questions:

by the way, my goal with this was to generate subgroups of developers to meet up every week with one of the team leads. we want everyone in our pool to know and work with everyone else but keep the amount of time needed by the leads as low as possible. the exact example would be: i (kristof) am one of the elements in the original set - how many manually or random shuffles does it take for me to be in a group with everyone else at least once?

now this is where it’s getting really interesting, i just found something: there is something called ‘restricted part size’ and ‘restricted number of parts’ which can be combined. and here we go (taking [4] for granted). i’m going to dissect the wikidia subsection[2] here: the first sentence (By taking conjugates, the number $pk(n)$ of partitions of $n$ into exactly $k$ parts is equal to the number of partitions of $n$ in which the largest part has size $k$.) we can easily take an example of: we have a set of 23 elements (obviously prime), we can just take 24 elements and later remove on of the ‘last’ partition: we’ve then got four partions of size 6 (or 6 partitions of size 4 - now the sentence makes sense, right?) and then remove one element of any partition which leaves us with three partitions of size 6 and one of size 5 (let’s recheck this: $(3 \cdot 6) + 5 = 23$). nice, the things i wrote actually do make sense. so let’s just take the formula $$p(n) = \sum_{k = 0}^n p_k(n)$$ and almost keep on reading. what even is $p(k)$ here? easy: $$ p_{k}(n) = p_{k}(n-k)+p_{k-1}(n-1)$$

this might look weird but what it says is: add elements te every partition an element until we’re out of elements, then the ‘last’ partition has one element less. looks hard, is actually quite simple.

the next thing that just jumps into our face is the next formula: $$\sum_{n \geq 0} p_k(n) x^n = x^k \cdot \prod_{i = 1}^k \frac{1}{1 - x^i}$$

it’s easy to see that $n$ is of non-fixed size, while $k$ is actually fixed. and we’re just iterating through each possible fixed-size $n$, which - as we probably remember - is the amount of different partitions for a set $M$. so what we’re doing here is calculating the amount of distinct and unique permutations of partitions of a fixed size for an arbitrary set $M$. this sentence is long, and awesome, and totally unncessessary, but i like it. and when i’m ready for it, i’ll probably put this whole thing into actual code and see what i end up with and then maybe i can answer the questions stated above.

[update] you can find the code i’m writing (in c++ for whatever reason) here: https://github.com/lakrizz/experiments/

sources

  1. https://en.wikipedia.org/wiki/Partition_of_a_set
  2. stating the obvious: $m,n \in \mathbb{N}$ (if i’m missing other obvious rules here give me a shoutout)
  3. https://en.wikipedia.org/wiki/Partition_%28number_theory%29#Restricted_part_size_or_number_of_parts
  4. also: $m,n \in \mathbb{N}_{+}$
  5. what you might want to know is what partitions actually are: distinct subsets of variable size of a given set.