Combinatorics: Solving the Distinct Components of a Symmetric Tensor

  • Context: High School 
  • Thread starter Thread starter Mayan Fung
  • Start date Start date
  • Tags Tags
    Combinatorics
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
11 replies · 2K views
Mayan Fung
Messages
131
Reaction score
14
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.
 
Physics news on Phys.org
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. :(
 
I also tried starting from k = 1, and I still failed...
 
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.
 
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:
Chan Pok Fung said:
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 :(
No, there's an easier way.
The trick is to map it into the distinct values case. Consider the sequence yi=xi+i.
 
I still can't get a clue on that :cry:
 
Chan Pok Fung said:
I still can't get a clue on that :cry:
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?
 
  • Like
Likes   Reactions: Mayan Fung
That sounds to be a clever method! I will try it after finishing my work on hand! Thanks!