Permutations/combinations problem

  • Thread starter JL3
  • Start date

JL3

2
0
I have a problem about combinations and permutations I am trying to solve. Say we have an n-dimensional vector. Each element of the vector can contain any one of [tex]\lambda=3[/tex] values (-1, 0 or +1). Then the number of possible vectors is simply:

[tex]\lambda^n[/tex]

If we place the additional restriction that the vector must contain exactly [tex]k[/tex] non-zeros, then it becomes:

[tex]p=(\lambda-1)^{k}\times\binom{n}{k}=\frac{n!(\lambda-1)^{k}}{k!(n-k)!}[/tex]

If we change the restriction so that it must contain at most [tex]k[/tex] non-zeros and at least 1 non-zero, then it becomes:

[tex]p=\sum_{k'=1}^{k}\left[(\lambda-1)^{k'}\times\binom{n}{k'}\right]=\sum_{k'=1}^{k}\frac{n!(\lambda-1)^{k'}}{k'!(n-k')!}[/tex]

Are my equations correct? Is there a more compact way of expressing this last equation, to get rid of the summation?
 

fresh_42

Mentor
Insights Author
2018 Award
10,429
7,122
The formulas are correct.

If we want to get rid of the sum, we needed ##\binom n {k'} =\binom k {k'} \cdot r(n,k)## but the correction ##r## does also depend on ##k'##. So I guess there is no way to get rid of the sum.
 

Want to reply to this thread?

"Permutations/combinations problem" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top