1
$\begingroup$

First of all let me tell what I mean by distribution order matters: it means the order in which cells gets item matters (This may get clear with example and some points noted in the end).

Now I have few conditions on distribution for which I want to find closed formula (or summation series):

  • Both items and cells are distinguishable
  • Repetition of items is not allowed (one item can go to only one cell)
  • Each cell can receive zero or more items
  • Order of distribution matters.

Let me give example. There are two cells $\{a,b\}$ and three items $\{1,2,3\}$. Then each of the following will be considered as different distributions:

  • $\{a=[1,2],b=[3]\}$
  • $\{a=[2,1],b=[3]\}$
  • $\{a=[1,3],b=[2]\}$
  • $\{a=[3,1],b=[2]\}$
  • $\{a=[2,3],b=[1]\}$
  • $\{a=[3,2],b=[1]\}$
  • $\{b=[1,2],a=[3]\}$
  • $\{b=[2,1],a=[3]\}$
  • $\{b=[1,3],a=[2]\}$
  • $\{b=[3,1],a=[2]\}$
  • $\{b=[2,3],a=[1]\}$
  • $\{b=[3,2],a=[1]\}$

Some points:

  • Note that above example does not show distributions having any cell zero items. I tried listing only those distributions having no cell zero items to illustrate what all distributions are possible.
  • Note that the difference between $[1,2]$ and $[2,1]$ is that in $[1,2]$, 1 is put first in the cell and 2 afterwards, while in $[2,1]$, 2 is put first in the cell and 1 afterwards.
  • Also above considers the distribution order within then the cell. If we consider distribution order across the cells then the same end result: $\{a=\{1,2\},b=\{3\}\}$ will have $n!$ possible distribution orders as shown in below table. What will be number of distributions in this case? (And also above case in which order matters "wihthin the cell") Below is list of all distributions that will result when order matters across cells: enter image description here The total turns out to be 67 distributions.
$\endgroup$
1
$\begingroup$

There will be $n!$ permutations of your items, and then for each permutation there will be $n + k - 1 \choose k - 1$ ways of putting the $n$ items into $k$ boxes (which may or may not be empty). Every possible configuration you're looking for can be achieved by putting the objects in a specific order (one of the permutations), and then boxing them all up in exactly that order, so the number of ways to achieve your goal is precisely $n! {n + k - 1 \choose k - 1}.$

(For example: notice that for the case you gave with $n = 3$ and $k = 2$, there are $12$ more possibilities like $a = [1, 3, 2], b = []$, etc., which brings the total possibilities to $24$. Our calculation then gives $3! {4 \choose 1} = 24$, as expected.)

$\endgroup$
  • $\begingroup$ ok so $n!\binom{n+k-1}{k-1}$ is when the order of distribution within the cell matters. What about when the order of distribution across the cell matters (last point in the original question)? Now I feel we should multiply again by $n!$ making it $(n!)^2\binom{n+k-1}{k-1}$. (1) Right? Also what when each cell can have at least one item? Will it be (2) $n!\binom{n-1}{k-1}$ when order matters within the cell? and (3) $(n!)^2\binom{n-1}{k-1}$ when order matters across cells? $\endgroup$ – anir Jul 17 '17 at 20:22
  • $\begingroup$ @anir This answer takes into account the difference between $a = [1, 3, 2], b = []$ and $b = [1, 3, 2], a = []$, and it also takes into account the difference between $a = [1, 3, 2]$ and $a = [3, 2, 1]$, if either of those are what you're asking about. Otherwise, I'm not sure what you mean by "distribution across the cell" - an example might help clarify. For $(2)$, yes, if the cells must be non-empty then $n! {n-1 \choose k-1}$ is the correct count. I don't really understand you in $(3)$. $\endgroup$ – Chris Jul 17 '17 at 21:35
  • $\begingroup$ I guess my example in question made you implicitly assume that all items get distributed to some cell. But if you read the conditions, this isn't listed. For the case "when distribution matters across cells", I have listed out all possible distributions for $n=3,r=2$ in the diagram I added in the original question now. Please have a look. $\endgroup$ – anir Jul 19 '17 at 6:11
  • $\begingroup$ @anir Yes, I assumed you were distributing all the items. If that's not the case, make selections of which items you are distributing, then solve the problem for all such possibilities. (For example, maybe you're distributing $\{a, b\}$, or $\{a\}$. Use the logic above for those possiblities.) $\endgroup$ – Chris Jul 19 '17 at 6:20
  • $\begingroup$ Can there a closed formula or at least a summation series for this count? I initially thought it should be $n!r^n$, because there are $n!$ ways to arrange $n$ items and then each of $n$ item can go in any one of $r$ cells. But then an item may not go in any cell too. So I thought it should be $(r+1)^n$. But neither $n!r^n$ nor $n!(r+1)^n$ seem to give correct count. Also I am not able to come up with summation series which can logically mimic the distribution and give the correct count... $\endgroup$ – anir Jul 19 '17 at 20:09

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.