Prev: ... by little being the best way their habitual practice meami naos nakta tanak jet kust tant heut hidin si idin katin ekos kledin uemi siak sia... more » ...
Next: SAMSUNG SCH-U740
From: Senthil Kumar on 8 Jul 2010 07:13
Hi !

Here is my problem

example
k = { 1,2,3,4,5,6,7,8,9,10}
n = 4
x = 3

I want to find the number of combinations where the distance between
2 consecutive elements in the combination is not more than x.

eg combination 1 = { 2 ,3 ,5 ,7 } element( x) - element( x-1 ) <
x
7 - 5 < 3
5 - 3 < 3
3 - 2 < 3




Needed Help!


Senthil

From: Pubkeybreaker on 8 Jul 2010 07:43
On Jul 8, 7:13 am, Senthil Kumar <profile.sent...(a)gmail.com> wrote:
> Hi !
>
>  Here is my problem
>
>  example
>  k = { 1,2,3,4,5,6,7,8,9,10}
>  n = 4
>  x = 3
>
>  I want to find the number of combinations where the distance between
> 2 consecutive elements in the combination is not more than x.
>
>  eg  combination 1  = { 2 ,3 ,5 ,7 }  element( x) - element( x-1 )  <
> x
>                                                    7 - 5 < 3
>                                                    5 - 3 < 3
>                                                    3 - 2 < 3
>
>   Needed Help!
>
> Senthil

Your problem is not well posed.

Sets are not ordered. Your example may also be written as {7,5,3,2}.

If you want to discuss *permutations*, rather than combinations, that
is a different matter.
From: achille on 8 Jul 2010 09:22
On Jul 8, 7:13 pm, Senthil Kumar <profile.sent...(a)gmail.com> wrote:
> Hi !
>
>  Here is my problem
>
>  example
>  k = { 1,2,3,4,5,6,7,8,9,10}
>  n = 4
>  x = 3
>
>  I want to find the number of combinations where the distance between
> 2 consecutive elements in the combination is not more than x.
>
>  eg  combination 1  = { 2 ,3 ,5 ,7 }  element( x) - element( x-1 )  <
> x
>                                                    7 - 5 < 3
>                                                    5 - 3 < 3
>                                                    3 - 2 < 3
>
>   Needed Help!
>
> Senthil


I am confused, shouldn't "distance between 2 consecutive elements
is not more than x" means a_i - a_(i-1) <= x instead of '<' as
you example show???

In any event, if you start with m integers 1, .., m and construct
strictly increasing n-tuples (a_1, a_2, a_3, ... a_n) with the
restriction:
\forall i, 1 <= a_i <= m, AND 0 < a_i - a_(i-1) <= r.

The number of such n-tuples is equal to the coefficient
of z^m in the expansion z^n (1-z^r)^(n-1)/(1-z)^(n+1).

To see how to derive this expression, let's use your
(2,3,5,7) as an example. To build such a 4-tuple,
you can

[1] start at a fictitious position 0,
[2] move forward a_1 = 2 step to the 1st position 2,
associate a factor z^(a_i) to it.
[3] move forward a_2-a_1 = 1 step to the 2nd position 3,
associate a factor z^1 = z^(a_2-a_1) factor to it.
[4] move forward a_3-a_2 = 2 step to the 3rd position 5,
associate a factor z^2 = z^(a_3-a_2) factor to it.
[5] move forward a_4-a_3 = 2 step to the 4th position 7,
associate a factor z^2 = z^(a_4-a_3) factor to it.
[6] move forward m-a_4 = 3 step to the end m = 10,
associate a factor z^3 = z^(m-a_4) to this.

When you complete the moves, you will have accumulated
a factor

z^m = z^(a_1) z^(a_2-a_1) z^(a_3-a_2) z^(a_4-a_3) z^(m-a_4).

Now, let us sum over all possible configuration of (a_1,a_2,a_3...),

In step [2], the legal values of a_1 is 1,2,...
If you collect all factors of z^(a_i) togather,
you will get an overall factor

z+z^2+z^3+.... = z/(1-z)

for the first slot z^(a_1) above.

In step [3-5], the legal values of a_i-a_(i-1) is 1..r,
If you collect all factors z^(a_i-a_(i-1)), you will get
an overall factor

z+z^2+..+z^r = z(1-z^r)/(1-z)

for the slots z^(a_2-a_1), z^(a_3-a_2) and z^(a_4-a_3) above.

In step [6], the legal values of m-a_n is 0,1,2,....
If you collect all factors of z^(m-a_n), you will get

1+z+z^2+.... = 1/(1-z).

for the last slot z^(m-a_n).

Hence, any 'legal' n-tuple will contribute one "z^m" to
the expansion:

(z+z^2+z^3+...)(z+z^2+..+z^r)^(n-1)(1+z+z^2+...)
= (z/(1-z))(z(1-z^r)/(1-z))^(n-1)(1/(1-x))
= z^n (1-z^r)^(n-1) / (1-z)^(n+1).

For your case, if your "is not more than x" really means
a_i - a_(i-1) <= 3, (m,n,r) = (10,4,3) and the number you
want is the coefficient of z^10 in

z^4 (1-z^3)^3 / (1-z)^5 =
x^4+5*x^5+15*x^6+32*x^7+55*x^8+81*x^9+108*x^10+135*x^11+162*x^12+...

ie. 108.

If your "is not more than x" really means a_i - a_(i-1) < 3,
(m,n,r) = (10,4,2) and the number you want is the coefficient
of z^10 in

z^4 (1-z^2)^3 / (1-z)^5 =
x^4+5*x^5+12*x^6+20*x^7+28*x^8+36*x^9+44*x^10+52*x^11+60*x^12+...

ie. 44.


BTW, this sort of technique is called "generation function".
It is useful in solving a lot of enumeration problems in
combinatorics. Hope this helps...
From: Senthil Kumar on 9 Jul 2010 09:14
On Jul 8, 6:22 pm, achille <achille_...(a)yahoo.com.hk> wrote:
> On Jul 8, 7:13 pm, Senthil Kumar <profile.sent...(a)gmail.com> wrote:
>
>
>
>
>
> > Hi !
>
> >  Here is my problem
>
> >  example
> >  k = { 1,2,3,4,5,6,7,8,9,10}
> >  n = 4
> >  x = 3
>
> >  I want to find the number of combinations where the distance between
> > 2 consecutive elements in the combination is not more than x.
>
> >  eg  combination 1  = { 2 ,3 ,5 ,7 }  element( x) - element( x-1 )  <
> > x
> >                                                    7 - 5 < 3
> >                                                    5 - 3 < 3
> >                                                    3 - 2 < 3
>
> >   Needed Help!
>
> > Senthil
>
> I am confused, shouldn't "distance between 2 consecutive elements
> is not more than x" means a_i - a_(i-1) <= x  instead of '<' as
> you example show???
>
> In any event, if you start with m integers 1, .., m and construct
> strictly increasing n-tuples (a_1, a_2, a_3, ... a_n) with the
> restriction:
>   \forall i,  1 <= a_i <= m, AND 0 < a_i - a_(i-1) <= r.
>
> The number of such n-tuples is equal to the coefficient
> of z^m in the expansion  z^n (1-z^r)^(n-1)/(1-z)^(n+1).
>
> To see how to derive this expression, let's use your
> (2,3,5,7) as an example. To build such a 4-tuple,
> you can
>
> [1] start at a fictitious position 0,
> [2] move forward a_1 = 2 step to the 1st position 2,
>     associate a factor z^(a_i) to it.
> [3] move forward a_2-a_1 = 1 step to the 2nd position 3,
>     associate a factor z^1 = z^(a_2-a_1) factor to it.
> [4] move forward a_3-a_2 = 2 step to the 3rd position 5,
>     associate a factor z^2 = z^(a_3-a_2) factor to it.
> [5] move forward a_4-a_3 = 2 step to the 4th position 7,
>     associate a factor z^2 = z^(a_4-a_3) factor to it.
> [6] move forward m-a_4 = 3 step to the end m = 10,
>     associate a factor z^3 = z^(m-a_4) to this.
>
> When you complete the moves, you will have accumulated
> a factor
>
>    z^m = z^(a_1) z^(a_2-a_1) z^(a_3-a_2) z^(a_4-a_3) z^(m-a_4).
>
> Now, let us sum over all possible configuration of (a_1,a_2,a_3...),
>
> In step [2], the legal values of a_1 is 1,2,...
> If you collect all factors of z^(a_i) togather,
> you will get an overall factor
>
>    z+z^2+z^3+.... = z/(1-z)
>
> for the first slot z^(a_1) above.
>
> In step [3-5], the legal values of a_i-a_(i-1) is 1..r,
> If you collect all factors z^(a_i-a_(i-1)), you will get
> an overall factor
>
>    z+z^2+..+z^r = z(1-z^r)/(1-z)
>
> for the slots z^(a_2-a_1), z^(a_3-a_2) and z^(a_4-a_3) above.
>
> In step [6], the legal values of m-a_n is 0,1,2,....
> If you collect all factors of z^(m-a_n), you will get
>
>    1+z+z^2+....  = 1/(1-z).
>
> for the last slot z^(m-a_n).
>
> Hence, any 'legal' n-tuple will contribute one "z^m" to
> the expansion:
>
>    (z+z^2+z^3+...)(z+z^2+..+z^r)^(n-1)(1+z+z^2+...)
> =  (z/(1-z))(z(1-z^r)/(1-z))^(n-1)(1/(1-x))
> =  z^n (1-z^r)^(n-1) / (1-z)^(n+1).
>
> For your case, if your "is not more than x" really means
> a_i - a_(i-1) <= 3, (m,n,r) = (10,4,3) and the number you
> want is the coefficient of z^10 in
>
>    z^4 (1-z^3)^3 / (1-z)^5 =
> x^4+5*x^5+15*x^6+32*x^7+55*x^8+81*x^9+108*x^10+135*x^11+162*x^12+...
>
> ie. 108.
>
> If your "is not more than x" really means a_i - a_(i-1) < 3,
> (m,n,r) = (10,4,2) and the number you want is the coefficient
> of z^10 in
>
>    z^4 (1-z^2)^3 / (1-z)^5 =
> x^4+5*x^5+12*x^6+20*x^7+28*x^8+36*x^9+44*x^10+52*x^11+60*x^12+...
>
> ie. 44.
>
> BTW, this sort of technique is called "generation function".
> It is useful in solving a lot of enumeration problems in
> combinatorics.  Hope this helps...

Thank You for the reply.

I have one query,
Is there a generalized equation where m,n and r can be replaced to get
the number of n-tuples.

Senthil
 | 
Pages: 1
Prev: ... by little being the best way their habitual practice meami naos nakta tanak jet kust tant heut hidin si idin katin ekos kledin uemi siak sia... more » ...
Next: SAMSUNG SCH-U740