5
$\begingroup$

Suppose we have $n$ marbles each tagged with numbers $1$ through $n$. We have bags which are allowed to contain things where a thing is defined as either $\text{(a)}$ a marble or $\text{(b)}$ another bag.

We want to consider all of the ways which we can "bag" the marbles. "Bagging" means that the "end result", so to speak, is having a set of "outer" bags $\{b_1, b_2, b_3 \cdots b_q\}$ such that each marble is contained in one of the outer bags either directly, or indirectly (e.g., a marble may be within an inner bag which is contained in one of the $b_i$'s, and in general this "nesting" can be up to $n$ bags deep).

We have an endless supply of bags at our disposal. This would suggest that there is an issue. We could put one marble in some bag $b_1$, and put $b_1$ in another bag $b_2$, and continue this process arbitrarily so that we have an infinite number of combinations. We don't allow this. Each bag used must directly contain at least one marble.

Note that we consider the marble combinations as well. For example, if $n=2$, then one idea is to put one marble in a bag $b_1$ and having another bag $b_2$ which contains the other marble along with $b_1.$ This method counts for two baggings, since the two marbles can switch roles. The reason the marbles are "tagged" is to stress this point.

Now, onto the problems:

What is an algorithm to compute the number of all possible baggings as a function of $n$? Can it be done in polynomial time? Is there a mathematical closed form?

I have tried to formalize this below (if there is a mistake in the "formalization", simply go by what I've written above).

Formal Definition:

Let $X$ be an arbitrary nonempty finite set. Suppose it has cardinality $n$. To this set, we assign a finite class of sets $B_{X}$. A member of this class is called a "$B_{X}$ set". This assignment is defined recursively.

If $n=1$, then $X = \{x_0\}$ is a singleton set. In this case, the sole $B_{X}$ set is simply $X$.

If $n > 1$, then the $B_{X}$ sets of $X$ are those sets $B$ which satisfy the following: $B \cap X \neq \varnothing$, and $B \setminus (B \cap X) = \{B({X_1}), B({X_2}) \cdots B({X_p})\}$ where $X_1, X_2 \cdots X_p$ are pairwise disjoint with $\bigcup_{1 \leq i \leq p} X_i = X \setminus (B \cap X)$ and each $B(X_i)$ is a $B_{X_i}$ set (this is the recursive part; note $|X_i| < |X|=n$). Note that $B \setminus (B \cap X) = \varnothing$ is also allowed. In particular, this implies that all nonempty subsets of $X$ are $B_{X}$ sets.

It's fairly clear that the recursion terminates.

A complete bagging of $X$ is a nonempty finite set $\{b_1, b_2, b_3 \cdots b_q\}$ of sets where each $b_i$ is a $B_{Y_i}$ set with all of the $Y_i$'s being nonempty, pairwise disjoint and $\bigcup_{1 \leq i \leq q} Y_i = X$.

The number of complete baggings of $X$ depends solely on $n$. Let $C(n)$ denote this quantity. We want to compute $C(n)$.

$\endgroup$
9
  • 1
    $\begingroup$ I would suggest calculating the answer by hand for some small values of $n$, and then consulting the Online Encyclopedia of Integer Sequences. $\endgroup$ Aug 3, 2017 at 4:23
  • $\begingroup$ This sounds like counting trees with labelled leaves satisfying a condition like "each non-leaf is adjacent to a leaf". $\endgroup$ Aug 3, 2017 at 4:33
  • $\begingroup$ Making any progress, 1122? $\endgroup$ Aug 4, 2017 at 12:48
  • $\begingroup$ @GerryMyerson Unfortunately not. For $n \geq 6$ it's not easy to compute by hand. No luck with the Online Encyclopedia either. $\endgroup$ Aug 5, 2017 at 3:39
  • 1
    $\begingroup$ @GerryMyerson No. Jeremy's answer below seems correct. Also, sorry for the delayed response. $\endgroup$ Aug 8, 2017 at 4:24

1 Answer 1

2
$\begingroup$

The problem breaks down naturally into two parts:

  1. Put the marbles into the $k$ bags that contain them.
  2. Nest the $k$ bags into other bags.

Fixing a particular value of $k$, the first task can be accomplished in $S(n,k)$ ways, where $S(n,k)$ is the Stirling number of the second kind.

For the second task, treat the table on which the "outer" bags sit as a "super-bag". Then the bagging including the "super-bag" is a rooted, labelled tree on $k+1$ nodes, of which there are $(k+1)^{k-1}$ possibilities.

Summing these values for $k \in \{1 \ldots n\}$, we find the number of baggings of $n$ objects is $$\displaystyle \sum_{k=1}^n S(n,k) (k+1)^{k-1}$$

The first couple of terms in the sequence are 1, 4, 26, 243, 2992, 45906. Running up a few extra terms and checking in OEIS, this sequence is indexed as A052880.

Addendum: To address the issue brought up by @Jens, here is an enumeration for $n=3$

  1. Three outer bags - 1 way: (A)(B)(C)
  2. Two outer bags: - 9 ways: (AB)(C), (AC)(B), and (A)(BC); (A(B))(C), (B(A))(C), (A(C))(B), (C(A))(B), (A)(B(C)), (A)(C(B))
  3. One outer bag, three balls in outer bag - 1 way: (ABC)
  4. One outer bag, two balls in outer bag - 3 ways: (AB(C)), (AC(B)), (BC(A))
  5. One outer bag, one ball in outer bag - 12 ways: there are three ways to pick the ball in the outer bag (say A). Then there are four ways to arrange B & C: (A(BC)), (A(B)(C)), (A(B(C))), (A(C(B))).

Adding yields 26 possible combinations.

$\endgroup$
4
  • $\begingroup$ For $n= 1, 2, 3$ I'm getting the result $1, 4, 23$ where the $23$ divides into $1$ combination for $3$ bags, $9$ combinations for $2$ bags and $13$ combinations for $1$ bag. How does this compare with your distribution for $n=3$? $\endgroup$
    – Jens
    Aug 6, 2017 at 20:45
  • $\begingroup$ @Jens: please see edited answer to show my enumeration. Thanks! $\endgroup$ Aug 6, 2017 at 22:35
  • $\begingroup$ Thanks. I see where we differ. You are assuming it is OK to have more than one bag directly inside a bag. My understanding of the OP was that the allowed contents of a bag was one or more marbles and 0 or 1 bag. $\endgroup$
    – Jens
    Aug 6, 2017 at 22:50
  • $\begingroup$ Nice answer. Is there a simple asymptotic estimate for $\sum_{k=1}^{n} S(n,k)(k+1)^{k-1}$? $\endgroup$ Aug 8, 2017 at 4:43

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.