1
$\begingroup$

I am trying to find out if there is a mathematical function which can take n objects and place them in m boxes in a way that is indexed?

For example if I had 3 balls and I wanted them in 4 boxes, the function would generate something like: f_1(3,4) = (1,1,1,0), f_2(3,4) = (1,1,0,1), other f_i(3,4)'s (1,0,1,1),(0,1,1,1),(2,1,0,0),(1,2,0,0),(2,0,1,0),(1,0,2,0),(2,0,0,1),(1,0,0,2),(3,0,0,0),(0,3,0,0),(0,0,3,0), f_N(3,4) = (0,0,0,3).

Then if I wanted a specific permutation I could get f_i(3,4).

$\endgroup$
1
  • 1
    $\begingroup$ If you know the stars and bars argument, you can write an equivalence of this problem with finding subsets of $\{1,\dots,m+n-1\}$ of size $n-1.$ Specifically, if $1\leq a_1<a_2<\cdots<a_{n-1}\leq m+n-1,$ you can take the tuple $(a_1-1,a_2-a_1-1,\dots,a_{n-1}-a_{n-2}-1, m+n-1-a_{n-1}).$ It is easier to find an index of such a subset, rather than take an index and compute a subset, which is the reverse of your answer. $\endgroup$
    – Thomas Andrews
    Commented Sep 11, 2023 at 19:27

1 Answer 1

Reset to default
0
$\begingroup$

First, use combinadics to get an indexing function which, given a nonnegative integer $i$, returns the $i^\text{th}$ subset of $\{1,\dots,m+n-1\}$ whose size is $n$. I described how to do that in this answer.

Then, use the following correspondence to get a placement of $n$ balls in $m$ boxes. I will give a specific example in the case where $n=10$ and $m=100$. Suppose the indexing function from before gives your the subset $$\{3,4,10,11,12,27,104,105,106,107\}$$ of $\{1,2,\dots,109\}$. Decrease the smallest element by $0$, the second smallest element by $1$, and so on, up to decreasing the largest element by $9$. The result is a multiset, which may have repeated elements: $$ \{3,3,8,8,8,22,98,98,98,98\} $$ Finally, for each occurrence of a number, place a ball in the box with that number. For this example, place two balls in box $3$, three balls in box $8$, one ball in box $22$, and four balls in box $98$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .