Author 
Message 
Guest

Posted: Sat Apr 09, 2005 5:51 am Post subject:
inclusion/exclusion



Consider n students in a queue 1....n
We want to find how many options there are to resettle them so that no
one sees in front of him the same student he sees now.
Any suggestions? I guess I should define
P_i  student i sees the same student in front of him
I can find W(P_i), Even W(P_i, P_j) but then it gets complicated and I
can't find a specific rule...
Thanx for you help. 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Mon Apr 11, 2005 8:57 pm Post subject:
Re: inclusion/exclusion



alexrait@gmail.com wrote:
Quote:  Consider n students in a queue 1....n
We want to find how many options there are to resettle
them so that no one sees in front of him the same student
he sees now.
Any suggestions? I guess I should define
P_i  student i sees the same student in front of him
I can find W(P_i), Even W(P_i, P_j) but then it gets
complicated and I can't find a specific rule...

InclusionExclusion looks like the wrong way to go for this. My
inclination is to find a recurrence.
In fact, here's what I came up with:
Given a permutation sigma of {1,2,...,n}, define K_sigma to be the
number of i's such that
sigma(i+1) = sigma(i) + 1, where i is between 1 and n1. Then let
A(n,k) be the number of permutations sigma such that K_sigma = k. Then
you want to find A(n,0).
To get a recurrence, let sigma be a permutation of 1,2,...,n. Then look
at the effect of inserting (n+1) after the ith position, to get the
permutation tau.
(1) If i = 0, then K_tau = K_sigma.
(2) If i is such that sigma(i) = n, then K increases by 1; i.e.,
K_tau = K_sigma + 1. (This is because sigma(i+1), if defined, is less
than n.)
(3) If i is such that sigma(i+1) = sigma(i) + 1, then K decreases by 1.
(4) If i is such that sigma(i+1) =/= sigma(i) + 1, and sigma(i) =/= n,
then there is no change in K.
Now, for any permutation sigma of {1,2,...,n}, (1) occurs in 1 way, (2)
occurs in 1 way, (3) occurs in K_sigma ways, and (4) occurs in
nK_sigma1 ways.
If tau is a permutation of {1,2,..,n+1} with K_tau = k (an arbitrary
number here), then tau can be obtained from a permutation sigma of
{1,2,...,n} in 1 way (for (1) from a permutation with K_sigma = K_tau);
1 way (for (2) from a permutation with K_sigma = K_tau  1); K_tau+1
ways (for (3) from a permutation with K_sigma = K_tau  1); and
nK_tau1 ways (for (4) from a permutation with K_sigma = K_tau).
The recurrence you get is
A(n+1,k) = (nk) A(n,k) + A(n,k1) + (k+1) A(n,k+1),
where n >= 0, 0 <= k < n, along with the "boundary conditions"
A(n,n) = 0 for all n (because K_sigma < n, in fact),
A(n,1) = 0 for all n, and
A(1,0) = 1 (direct calculation).
Now, if I had the time, I'd pull out my copy of A=B to find out how to
get Maple to find a closed form for A(n,k), and check a few values,
just to make sure I got the limits on the indices correct. (n=3 should
be good enough, and can also be tabulated by hand.)
Whew! 8)
 Christopher Heckman 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Mon Apr 11, 2005 11:26 pm Post subject:
Re: inclusion/exclusion



Proginoskes wrote:
Quote:  alexrait@gmail.com wrote:
Consider n students in a queue 1....n
We want to find how many options there are to resettle
them so that no one sees in front of him the same student
he sees now.
[...]
InclusionExclusion looks like the wrong way to go for this.
My inclination is to find a recurrence.
In fact, here's what I came up with:
Given a permutation sigma of {1,2,...,n}, define K_sigma to
be the number of i's such that
sigma(i+1) = sigma(i) + 1, where i is between 1 and n1.
Then let A(n,k) be the number of permutations sigma such
that K_sigma = k. Then you want to find A(n,0).
To get a recurrence, let sigma be a permutation of 1,2,...,n.
Then look at the effect of inserting (n+1) after the ith
position, to get the permutation tau.
(1) If i = 0, then K_tau = K_sigma.
(2) If i is such that sigma(i) = n, then K increases by 1;
i.e., K_tau = K_sigma + 1. (This is because sigma(i+1), if
defined, is less than n.)
(3) If i is such that sigma(i+1) = sigma(i) + 1, then K
decreases by 1.
(4) If i is such that sigma(i+1) =/= sigma(i) + 1, and
sigma(i) =/= n, then there is no change in K.
Now, for any permutation sigma of {1,2,...,n}, (1) occurs
in 1 way, (2) occurs in 1 way, (3) occurs in K_sigma ways,
and (4) occurs in nK_sigma1 ways.
If tau is a permutation of {1,2,..,n+1} with K_tau = k
(an arbitrary number here), then tau can be obtained from
a permutation sigma of {1,2,...,n} in 1 way (for (1) from
a permutation with K_sigma = K_tau); 1 way (for (2) from a
permutation with K_sigma = K_tau  1); K_tau+1 ways (for
(3) from a permutation with K_sigma = K_tau  1); and
nK_tau1 ways (for (4) from a permutation with
K_sigma = K_tau).
The recurrence you get is
A(n+1,k) = (nk) A(n,k) + A(n,k1) + (k+1) A(n,k+1),
where n >= 0, 0 <= k < n, along with the "boundary
conditions"
A(n,n) = 0 for all n (because K_sigma < n, in fact),
A(n,1) = 0 for all n, and
A(1,0) = 1 (direct calculation).

You also need A(n,n1) = 1, for all n.
Quote:  Now, if I had the time, I'd pull out my copy of A=B to
find out how to get Maple to find a closed form for A(n,k),
and check a few values, just to make sure I got the limits
on the indices correct. (n=3 should be good enough, and
can also be tabulated by hand.)

After having skimmed A=B, I've found I may not be able to do this. So
I'll just look for patterns. And use n=4.
(Later:) I programmed the recurrence and have found the sequence you're
interested in (starting with n = 0): 0, 1, 1, 3, 11, 53, 309, 2119, ...
This is sequence number A000255 in the Online Encyclopedia of Integer
Sequences, and is defined as in the original problem:
http://www.research.att.com/projects/OEIS?Anum=A000255
A(n,1) = 1, 2, 9, 44, 265, 1854, ..., which appears to be the number of
derangements (A000166) (!), at
http://www.research.att.com/projects/OEIS?Anum=A000166
(Hmmm ... It seems like there should be a nice proof of this fact, if
it's true.)
A(n,2) appears to be A000274.
A(n,3) appears to be A000313.
A(n,4) appears to be A001260.
Et cetera. (There don't seem to be any nice descriptions of A(n,k) for
any other fixed values of k, other than k = 1.)
Quote:  Whew!

 Christopher Heckman 

Back to top 


Matthew Roozee science forum beginner
Joined: 22 Oct 2005
Posts: 7

Posted: Sat Oct 22, 2005 7:46 pm Post subject:
Re: inclusion/exclusion



Quote:  alexrait@gmail.com wrote:
Consider n students in a queue 1....n
We want to find how many options there are to resettle
them so that no one sees in front of him the same student
he sees now.
Any suggestions? I guess I should define
P_i  student i sees the same student in front of him
I can find W(P_i), Even W(P_i, P_j) but then it gets
complicated and I can't find a specific rule...

If A(n) is defined as the number of "good" resettlings of students, then
the recurrence relation is:
A(n) = (n1)A(n1) + (n2)A(n2)
where A(1) = 1, A(2) = 1
An alternative approach is to express the solution in terms of derangements:
A(n) = D(n) + D(n1)
The first few values for A are:
1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457
as n gets large, the probability of a resettling being "good" approaches
1/e or about 36.8%
 Matt 

Back to top 


Google


Back to top 



The time now is Wed Sep 26, 2018 5:30 am  All times are GMT

