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!

Help with combinatorics

  1. Feb 28, 2015 #1
    1. The problem statement, all variables and given/known data

    set {A} : 26 elements <--- let's call this number n

    set {B}: 24 elements <--- let's call this number m

    goal: i want to know the number of possible combinations i will have if i start by replacing one element in {A} with an element in {B}, then i want to know the number of possible combinations of elements i can have if i replace two elements in {A} with any two elements in {B}. i want to do this all the way up to 24 replacements.

    2. Relevant equations

    this is what i'm trying to ultimately find.

    3. The attempt at a solution


    1 replacement: $$ n*m$$
    (since the number of elements you can replace in set A is n, and for each replaced element, there are m possible numbers in B you can replace them with)

    2 replacements: $$n!(n-1)!*m(m-1)$$
    (the n terms on the left deal with the placement of the A elements getting replaced. ie how many different ways can you arrange two elements throughout {A}

    $$a_{1}a_{2}$$
    $$a_{1}a_{3}$$
    $$a_{1}a_{4}$$
    $$...$$
    $$a_{1}a_{n}$$
    ...
    $$a_{2}a_{3}$$
    $$a_{2}a_{4}$$
    $$a_{2}a_{5}$$
    etc..

    and the m terms on the left: basically after you pick a b_element for any particular arrangement, you have now have b-1 elements to choose from.
    )

    m replacements: $$ n!(n-1)!(n-2)!(n-3)!...(n-m)!*m(m-1)(m-2)(m-3)...(1) = Π(n-i)!*m!$$

    i'm very suspicious of my answer because it yields numbers that seem too big to be true
     
  2. jcsd
  3. Feb 28, 2015 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I don't understand how you are getting products of factorials. The sets are unordered, no? E.g. For 2 swaps, you just want the number of pairs you can select from each set.
     
  4. Feb 28, 2015 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    For two replacements, you want to swap pairs from A with pairs from B, so the number you want should be ##N_2 = C(n,2) C(m,2)##, where ##C(a,b)## is the binomial coefficient "a choose b". Thus, you should have ##N_2 = n(n-1) m(m-1)/4##. Your computation counted the choices from A and B way too many times.

    For ##k## interchanges, you want to swap all possible ##k##-tuples from A and B.
     
  5. Feb 28, 2015 #4
    i think i see why you wrote the n terms that way; perhaps this might clear things up. with the n terms, which deal with the placements of the b terms, i'm trying to find the number of combinations of a terms. like this:

    $$a_{1}a_{2}$$
    $$a_{1}a_{3}$$
    $$a_{1}a_{4}$$
    ...
    $$a_{1}a_{n}$$

    $$a_{2}a_{3}$$
    $$a_{2}a_{4}$$
    $$a_{2}a_{5}$$
    ...
    $$a_{2}a_{n}$$

    $$a_{3}a_{4}$$
    $$a_{3}a_{5}$$
    $$a_{3}a_{6}$$
    ...
    $$a_{3}a_{n}$$

    $$a_{n-1}a_{n}$$

    i need to count each of these separately. so not just any a term and another a term (in which case i can see how n(n-1) would appear)

    so maybe..

    first set: (n-1) terms

    second set: (n-2) terms

    ...


    $$\Sigma{(n-i)} (i: 1~(n-1))$$
    would this be more correct?


    in case i misunderstood you, and the above was actually that you were calculating.. how are you getting a factor of n(n-1)/4 for the n terms??
     
  6. Feb 28, 2015 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I just used well-known results: the number of pairs of the form ##a_i a_j##, with ##i < j##, is just ##C(n,2)##.

    This assumes---as you do---that order does not matter, so we only count ##a_1 a_2## and ##a_2 a_1## once, not twice. This is because when dealing with sets, the order does not matter.

    There are similar formulas for finding the number of distinct ##k##-tuples ##a_{i_1} a_{i_2} \ldots a_{i_k}## with ##1 \leq i_1 < i_2 < \cdots < i_k \leq n##, assuming all the ##a_i## are different (so we don't have sets "with repetitions"). I am surprised that your textbook does not have this formula; it is just the formula for the number of subsets of cardinality ##k## in a set of cardinality ##n##. Anyway, it is available on-line; see, eg., http://cims.nyu.edu/~kiryl/teaching/dm/les070103.pdf .
     
    Last edited: Feb 28, 2015
  7. Feb 28, 2015 #6
    thanks for the site.

    but i'm still having trouble understanding the combination/permutation formulas.i looked at the derivations for them and it still doesn't make sense to me.

    combination formula:
    $$C(n,r) = \frac{n!}{r!(n-r)!}$$

    say we have an n choose r situation ie just the combination, where n=5, r=3.

    what are the number of possible sets we can make with three elements from five values?

    if i do this: $$n(n-1)(n-2)(n-3)$$

    i'm doing the following: take any element from the five values, and put it in the first element, take any remaining value and stick it in the second element, and etc.

    so here lies my confusion; while doing n*(n-1)(n-2)...etc i see nothing in this method that restricts you to put the first chosen value in the first element. you could have just as well put the first chosen value in the second or third element. and the freedom to do that would imply that it's a set right? so why divide by r! ?

    what am i missing?
     
  8. Feb 28, 2015 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You are double-counting, or worse.

    For A = {1,2,3,4,5}, how many subsets of size 2 are there? List them all:
    12, 13, 14, 15, 23, 24, 25, 34, 35, 45---10 altogether. Note that 10 = 5*4/2 = C(5,2). In your count "5*4 = 20" you have listed each pair twice; once as 'ab' and again as 'ba'.

    What are the subsets of size 3? Here they are:
    123, 124, 125, 134, 135, 145, 234, 235, 245, 345---10 altogether. Again, 10 = 5*4*3/(3*2) = C(5,3). In your count "5*4*3 = 60" you have counted each triple 6 times; for example, you have counted each of the choices 123, 132, 213, 231, 312, 321 separately, but they are really only one subset and so should not be counted separately.
     
  9. Feb 28, 2015 #8
    i get it!

    thanks ray
     
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: Help with combinatorics
  1. Help on combinatorics (Replies: 3)

  2. Basic Combinatorics (Replies: 3)

  3. Combinatorics Question (Replies: 7)

Loading...