Combinatorics: Solving the Distinct Components of a Symmetric Tensor

In summary, if I have k positive integers, x1, x2, ..., xk and n(also an integer) where $$ x_1≤x_2≤x_3≤...≤x_k≤n $$then there are nCk different combinations of k items.
  • #1
Mayan Fung
131
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
  • #2
Hey Chan Pok Fung.

Hint - Try fixing a case for n = 2 and then do an inductive argument.
 
  • #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. :(
 
  • #4
I also tried starting from k = 1, and I still failed...
 
  • #5
Chan Pok Fung said:
I also tried starting from k = 1, and I still failed...
I hope this is not homework.
How many ways are there of choosing k out of n items?
 
  • #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.
 
  • #7
Chan Pok Fung said:
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.
Right, so which applies here?
 
  • #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:
  • #9
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.
 
  • #10
I still can't get a clue on that :cry:
 
  • #11
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 Mayan Fung
  • #12
That sounds to be a clever method! I will try it after finishing my work on hand! Thanks!
 

What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting, arranging, and selecting objects or elements in a set or group.

What is a symmetric tensor?

A symmetric tensor is a mathematical object that represents a multidimensional array of numbers, where the order of the dimensions does not matter. In other words, it is a tensor that remains unchanged when its components are permuted.

How do you solve the distinct components of a symmetric tensor?

To solve the distinct components of a symmetric tensor, you can use various techniques such as permutation and combination formulas, generating functions, and graph theory. The specific method used will depend on the problem at hand.

What are some real-world applications of combinatorics?

Combinatorics has many practical applications in fields such as computer science, statistics, biology, and physics. Some examples include coding theory, network analysis, DNA sequencing, and quantum mechanics.

Why is understanding combinatorics important?

Combinatorics is a fundamental concept in mathematics and has numerous applications in various fields. It helps in solving complex problems, making predictions, and understanding patterns and relationships between objects. It also lays the foundation for more advanced mathematical concepts and techniques.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
818
Replies
3
Views
577
  • General Math
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
898
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
646
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
22
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Back
Top