I want to find the number of ways x people can pick different amount of items from a set, where we can somewhat pinpoint which particular items each person can pick.
My case has 3 people picking up to 7 things from up to 21 items. A specific case would be 3 people picking 3 things each from 9 items.
In this case, we have a set S we want to partition into 3 parts each with a size 3. I found a formula that could help me find the number of ways to partition a set of size n, into k parts with different sizes r each.
P(n,k,r)= n!/(r!)^k⋅k!
This assumes all partitions are valid though. In this case, I want to restrict the first part of the partition to only select from a subset of parts. Similarly, I want to restrict the elements in the 2nd and 3rd part of the partition to different subsets of S. These subsets cover S but they're not disjoint.
So let's say S = {1,2,3,4,5,6,7,8,9}.
I want to know if there's a formula that can give me the number of ways I can make k partitions of size r where:
k_1 picks from {1,2,3,4,5} k_2 picks from {3,4,5,6,7,8} k_3 picks from {1,5,7,8,9}.
The closest I got is the generating function I got after trying this.
I made a program that creates a Venn diagram from the sets. Instead of trying to find each partition, it finds all partition shapes.
Part 1 of the partition can pick from what's strictly in it's set and not the others. It can pick from what's in the intersection of all of them, and what's in the intersection between it and the other two sets individually.
I can find all "shapes" the partition can make by treating it like a multi-set and using a generating function to find the number of ways the size of the partition can be made from the items.
A: {2}
A and B not C: {3,4}
A and C not B: {1}
A and B and C: {5}
So the number of shapes the partitions can make is:
(1+x)*(1+x)*(1+x)*(1+x+x^2) which gives us the coefficient 4 for x^3.
Similarly I can do that for part 2 and part 3.
I'm stuck in putting this all together. In how I can subtract the times where there would be overlap between the shapes P1, P2, and P3 make.