Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

B Combinatorics problem

  1. Nov 29, 2016 #1
    If I have k positive integers, x1, x2, ..., xk and n(also an integer) where
    $$ x_1≤x_2≤x_3≤...≤x_k≤n $$
    How can I get the total combinations? I am trying to find the distinct components of a symmetric tensor. But I stuck here.
     
  2. jcsd
  3. Nov 29, 2016 #2

    chiro

    User Avatar
    Science Advisor

    Hey Chan Pok Fung.

    Hint - Try fixing a case for n = 2 and then do an inductive argument.
     
  4. Nov 29, 2016 #3
    I tried that but I couldn't get a simple mathematical form.
    $$n=1, \#= 1$$
    $$n=2, \#= 1+k$$
    $$n=3, \#= \sum_{i=0}^k (1+k-i)= \frac{(k+1)(k+2)}{2}$$
    $$n=4, \#= \sum_{i=0}^k \frac{(k+1)(k+2)}{2} = .....$$
    I can't even get the n=4 term :( and I don't how how to generalize it. :(
     
  5. Nov 29, 2016 #4
    I also tried starting from k = 1, and I still failed...
     
  6. Nov 30, 2016 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I hope this is not homework.
    How many ways are there of choosing k out of n items?
     
  7. Nov 30, 2016 #6
    um... I have this doubt after doing my homework. Choosing k out of n items is nCk if they don't repeat. If they can repeat, then it is n^k.
     
  8. Nov 30, 2016 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Right, so which applies here?
     
  9. Nov 30, 2016 #8
    should be n^k and I need to find some ways to minus those counted repeatedly. For example, in the case of three objects, 123, 132, 213, 231, 312, 321 are the same. 122, 212, 221 are the same. But combination with "abc" forms are counted as 6 times, "abb" forms are counted as 3 times. Things even become more complicated for larger n and k. That's why I got stuck :(
     
    Last edited: Nov 30, 2016
  10. Nov 30, 2016 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, there's an easier way.
    The trick is to map it into the distinct values case. Consider the sequence yi=xi+i.
     
  11. Dec 1, 2016 #10
    I still can't get a clue on that :cry:
     
  12. Dec 2, 2016 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Consider an arbitrary sequence of positive integers x1 to xn such that xi<=xi+1.
    Now add 1 to the second term, 2 to the third term and so on to produce the sequence yi satisfying yi<yi+1.
    It is clear that each x sequence produces a y sequence in a deteministic manner.
    We can reverse the process. Given a y sequence, i.e. strictly increasing, we can subtract 1 from the second term, 2 from the third etc. to produce an x sequence. Again, a given y sequence can only produce one possible x sequence.
    We have established a bijection, or 1 to 1 correspondence, whatever terminology you are familiar with. Thus there is the same number of x sequences as there is of y sequences.
    If the set of x sequences was constrained by xn<=N, what is the constraint for the y sequences?
     
  13. Dec 2, 2016 #12
    That sounds to be a clever method! I will try it after finishing my work on hand! Thanks!
     
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 problem
  1. Combinatorics problem (Replies: 6)

  2. Combinatorics problem (Replies: 3)

  3. Combinatorics problem (Replies: 8)

  4. Combinatorics problem (Replies: 4)

Loading...