1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics with repetition

  1. Oct 15, 2015 #1
    1. The problem statement, all variables and given/known data

    if there are k spots for n balls, what are the number of possible arrangements? each spot can hold n number of balls and each ball is indistinguishable from one another.

    2. Relevant equations
    $$\frac{n+k-1}{k!(n-1)!}$$

    3. The attempt at a solution
    I just wanted to know if this was the right equation, since i don't understand the equation.
     
  2. jcsd
  3. Oct 15, 2015 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The question is unclear. Does it mean the following?

    We have m>nk indistinguishable balls and k buckets, labeled 1 to k. We then put a number of balls between 0 and n inclusive in each bucket.
    How many different arrangements of number of balls in the numbered buckets are there?
     
  4. Oct 15, 2015 #3
    yup, that's what i meant. I'm actually trying to recreate all the possibilities visually (well, conceptually) but the number i get is different from the one the below eqn yields. $$\frac{n+k-1}{k!(n-1)!}$$
    basically, i'm either not covering all possible arrangements with the way i'm going about it, or the expression i came up with is just incorrect. Either way i'd like someone to point out what i'm doing wrong.


    so here's how i'm doing it visually, just bear with me:

    first, only one of the balls traverse all possible spots leaving us so far with:
    $$Arrangements = k$$
    H2TepLs.png

    then, for each spot it occupied, we find the number of additional arrangements it can make with an additional ball:

    ogLhRom.png
    +1
    G8CJMjI.png
    +2
    dt7lcyg.png
    +3

    for each time we move the red over, we traverse the green from position 2 to the red. (I do this because i'm trying to find the combination and not the permutation)

    so now we have $$Arrangements = k + \sum^{k-1}_{i=1}(i)$$

    again, being careful not to include any doubles of the same arrangement, i go from left to right.

    MmQfO6p.png
    mkyahKM.png
    i move the blue over to position 2, we have the same situation we had earlier, just with k-1 spots now.repeating the previous process we should end up with..

    $$Arrangements = k-1 + \sum^{k-2}_{i=1}(i)$$

    repeating the process till the end we get:

    $$Arrangements = \sum^{k-1}_{j=0}[ (k-j) + \sum^{k-1-j}_{i=1}(i)]$$

    So.....
    this was the case for 3 choose k. using my formula for say.. 3 choose 10, i get 121, whereas $$\frac{n+k-1}{k!(n-1)!}$$
    says it should be 220. how does this not cover every possible arrangement?
     
    Last edited: Oct 15, 2015
  5. Oct 15, 2015 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I think you're doing it in a more difficult way than necessary. Your pictures seem to be treating the balls as distinguishable by colour, whereas the problem says they are indistinguishable. That reduces the problem to the following:

    How many different sequences of k numbers are there, where each number is an integer in {0, 1, 2, ..., n}?
     
  6. Oct 15, 2015 #5
    my apologies! the colors were just for me to keep track of what spots i already traversed. just makes it easier for me. but yes they are indistinguishable and so the colors are irrelevant.

    k!, actually i have a simpler question, what i did above, is that "combination with repetition" or is it something completely different?
     
  7. Oct 16, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    First, your equation is not quite right. It should be ##\frac{(n+k-1)!}{(k-1)!n!}##. To verify that, consider 1 ball, 2 spots. There are two possible arrangements, not 1.
    The easiest way to understand this equation is to think in terms of separators between the 'spots', rather than the spots themselves. There are k-1 of these.
    Next, blur the distinction between the balls and the separators. There are just n+ k-1 'things' in a line, of which k-1 are separators. The possible arrangements of undistinguished balls into the slots is then just the number of ways of deciding which of the n+k-1 things are the k-1 separators.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics with repetition
  1. Digit 5 repetition (Replies: 3)

  2. Combinatorics Question (Replies: 7)

  3. Combinatorics help.... (Replies: 12)

Loading...