0
$\begingroup$

Consider four marble types $\{a,b,c,d\}$, and four boxes that can have two marbles each. I have access to a maximum of 3 marbles per type and all boxes must be filled. The problem is to find the number of ways one can fill the boxes subject to the following restrictions:

  • Restriction 1: The type of marbles is irrelevant, only the individual number of repetitions is important for the counting of solutions;
  • Restriction 2: There must be at least one marble of each type;
  • Restriction 3: No box can contain two marbles of the same type;
  • Restriction 4: The same combination of marbles in a box can only appear once.

By direct inspection, one gets the only two types of solutions: $$ \textrm{solution} \, 1 = |ab| |ac| |ad| |bc| \\ \textrm{solution} \, 2 = |ab| |ac| |cd| |bd| $$ The goal is to find a general answer rather than a solution by inspection.

Solution attempt:

Since I have 8 marble slots to be used and four of them are already fixed (by Restriction 1), I have a total of 4 marble slots free. Considering now the four marble types, I'm interested in partitioning 4 marbles into $m=4$ or less parts (corresponding to the four types), all of size $n=2$ or less (since I have 2 marbles of each type left to be used). The answer is given by the coefficient of $q^4$ in the expansion of the Gaussian Binomial Coefficient $$ \binom{m+n}{n}_q = \prod^{m}_{i=1} {1-q^{m+n-i+1} \over 1-q^i} $$ which is $3$; one more than the correct answer. The three cases obtained are associated to the repetitions $$ (a,b,c,d) = \{(3,2,2,1),(2,2,2,2),(3,3,1,1)\}\,, $$ where solution 1 corresponds to $(3,2,2,1)$ and solution 2 to $(2,2,2,2)$. The third case would correspond to something of the type $$ |ab| |ab| |ac| |bd| $$ which cannot happen because of Restriction 4. I'm wondering where there is any kind of generating function which can give me the answer directly with the fourth restriction included. This would be ideal since I intended to generalise the problem to boxes of different sizes.

EDIT: Solution 2 was misspelled.

$\endgroup$
  • $\begingroup$ I don't quite understand Restriction 1 as you phrase it. My natural interpretation of it is "Two solutions are equivalent if we can get one from the other by relabeling the types of marbles", but then the two solutions you give are actually equivalent: you can get solution 2 from solution 1 by switching $a$ and $c$. $\endgroup$ – Misha Lavrov Mar 15 '17 at 17:58
  • $\begingroup$ You're right, I misspelled solution 2. Thank you. $\endgroup$ – GKiu Mar 15 '17 at 19:13
1
$\begingroup$

In the case where the boxes have two marbles each, restrictions 3 and 4 tell us that we can think of each solution as a graph, where each marble type is a vertex and each box is an edge. Restriction 2 means that each vertex must have degree at least $1$, and Restriction 1 tells us that two solutions are equivalent precisely when the graphs are isomorphic.

So the un-generalized question asks: how many different graphs are there with $4$ vertices and $4$ edges? We get the following two graphs corresponding to the two solutions:Solution 1 Solution 2

Generalizing this to $n$ two-marble boxes and $n$ marble types is not too hard: it is A001434 in the OEIS, the number of $n$-vertex graphs with $n$ edges. The more general sequence A008406 which counts $n$-vertex graphs with $k$ edges gives a somewhat upsetting formula that may be better than nothing. If we also include the restriction that no marble is used more than three times, then each vertex is limited to degree 3, which makes things trickier; I'm not sure that's been counted before.

Generalizing the boxes to hold $k$ marbles each means we've moved on to $k$-uniform hypergraphs, which is also much scarier and I don't have an answer for you there.

$\endgroup$
  • $\begingroup$ This is amazing. Thank you very much for your answer! This is the first time I'm dealing with graphs so I'll have to study this a bit before fully understanding your answer. However, if I may add an extra question, how would a box of 3 marbles and another one of 2 marbles fit into this? I do not need a numerical answer, just the correct way to express the solution in graph nomenclature. In the end, I'm interested in generalising the answer for any number of boxes, with different marbles slots each. $\endgroup$ – GKiu Mar 15 '17 at 20:22
  • $\begingroup$ As soon as you get boxes with more than 2 marbles in them, you're talking about a hypergraph (but a non-uniform one when the boxes have different sizes). Technically, any set family is a hypergraph, but because your symmetry condition is essentially asking about (hyper)graph isomorphism, I think the terminology is useful here. $\endgroup$ – Misha Lavrov Mar 15 '17 at 20:27
  • $\begingroup$ That's more than enough for me, thank you very much! $\endgroup$ – GKiu Mar 16 '17 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.