Mathematica function for # possible arrangements of items in bins?

GROUPS:
 You have a hat with an infinite number of marbles with 10 color categories - equiprobable.You have 50 (numbered) bins to fill, so order matters.How many possible arrangements are there?Here is where I get stuck: What if we require that all of the 10 colors be used at least once?
3 years ago
12 Replies
 Daniel Lichtblau 3 Votes This isn't a Mathematica question, but...consider recasting your bins as digit places and your colored marbles as numbers from 0 through 9. So bin#1 is the ones place, bin#2 the tens place, etc. And red=0, yellow=1,...,violet=9.Your (first) question is thus equivalent to this: how many base 10 numbers are there of 50 digits?the requirement that all colors get used at least once is equivalent to asking how many 50 digit numbers there are that use every digit between 0 and 9. For that, you might start with the answer to the first question and subtract off however many numbers there are that DO NOT use all 10 digits. So then ask: how many use all but the first digit? All but the second? And so on. Now you have to account for double-subtracting since the ones that use all but the first overlap those that use all but the second (they are the ones that use neither first nor second). From here one develops an inclusion-exclusion method.If I wrote the computation correctly, it is this: s1 = Sum[(-1)^j*Binomial[10, j]*j^50, {j, 10}] (* Out[90]= 94910235292763223632455966616702223835130977516800 *) N[s1/10^50] (* Out[93]= 0.949102352928 *) So around 95% of the 50 digit numbers use all ten digits.
3 years ago
 Daniel, Thank you. I'll try it. Doug
3 years ago
 You can generalize from Daniel's formula to the following: (* Number of digits and number of draws *) ndigits = 3; n = 4; (* Total number of arrangements *) ndigits^n (* Number of arrangements with all digits *) (-1)^ndigits*Sum[(-1)^j*Binomial[ndigits, j]*j^n, {j, ndigits}] (* If you want to see all of the possible arrangements to check on the formula *) digits = Table[i, {i, 0, ndigits - 1}] If[ndigits^n < 500, Tuples[digits, n]] The multiplier (-1)^ndigits is needed when there is an odd number of digits.
3 years ago
 Consider this to be the genetic code, and for once and all we are going to state how many possible codes there are! 64 bins for the codons. 21 items, for the 20 amino acids plus one stop codon.Am I suppose to take an absolute value if these equations produce negative numbers?Dougs1 = Sum[(-1)^jBinomial[21, j]j^64, {j, 21}]N[s1/21^64]-151010951579291824411678133931578508184129460796061495630233012354424\ 2628820336640000-0.360557
3 years ago
 Daniel Lichtblau 1 Vote For generality use the (-1)^ndigits as @Jim Baldwin mentioned. In this example it amounts to taking the absolute value.
3 years ago
 Douglas Kubler 1 Vote Douglas, Consider this to be the genetic code, and for once and all we are going to state how many possible codes there are! 64 bins for the codons. 21 items, for the 20 amino acids plus one stop codon. Does Nature know left from right? Should you divide your count by 2?
3 years ago
 Thank you Jim and Dan. DougP.S. 4 nucleotides, 20 amino acids == faces of smallest and largest Platonic solids.
3 years ago
 Jim Baldwin 1 Vote Taking the absolute value works just fine in this case but I wanted to assure you that it is not just a matter of convenience. One can write the appropriate general equation using the inclusion/exclusion principle (inclusion/exclusion principle wiki) just as Daniel Lichtblau described. For whatever it's worth below is more of a step-by-step use of that principle for a "less numerous" example than the original question. (* Determine the number of permutations of length n with up to d digits that contain all d digits. *) (* Set values that only require a few steps *) d = 4; n = 8; (* Total number of permutations *) s0 = d^n (* Now subtract off the number of permutations that leave off one number and use just the remaining number of digits. There are d = Binomial[d,1] possible digits to remove and (d-1)^n permutations of the remaining d-1 digits. Those permutations consist of the remaining d-1 digits. *) s1 = s0 - Binomial[d, 1] (d - 1)^n (* We've now subtracted off too many times the number of permutations that had two digits left off. There are Binomial[d,2] possible pairs of digits to leave off and (d-2)^n permutations of the remaining digits. So add those back in. *) s2 = s1 + Binomial[d, 2] (d - 2)^n (* We've now add added in too many times the number of permutations that had three digits left off. There are Binomial[d,3] possible triplets of digits and there are (d-3)^n permutations of the remaining digits. So subtract those out. *) s3 = s2 - Binomial[d, 3] (d - 3)^n (* We are now done for this example after considering removing up to 3 digits because we only had 4 digits to start with as all permutations have to have at least one digit represented. *) (* If we did this in general, we see that because Binomial[d,j] == Binomial[d,d-j], the answer is any of the equivalent forms below... *) d^n + Sum[Binomial[d, j] (d - j)^n (-1)^j, {j,d - 1}] (* Direct from the steps above *) Sum[Binomial[d, j] (d - j)^n (-1)^j, {j, 0, d - 1}] Sum[Binomial[d, j] j^n (-1)^(d - j), {j, d}] (-1)^d*Sum[(-1)^j*Binomial[d, j]*j^n, {j, d}] Abs[Sum[(-1)^j*Binomial[d, j]*j^n, {j, d}]]
3 years ago
 Is there an online Mathematics journal that is peer reviewed where we could publish this number and how it was derived?After that, we could drop the reference in Wikipedia in a few places so this question does not come up again or get answered using bad math.I obviously have some reading to do, because I like to be able to derive the math I am using from scratch.