FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
inclusion/exclusion
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Matthew Roozee
science forum beginner


Joined: 22 Oct 2005
Posts: 7

PostPosted: Sat Oct 22, 2005 7:46 pm    Post subject: Re: inclusion/exclusion Reply with quote

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) = (n-1)A(n-1) + (n-2)A(n-2)

where A(1) = 1, A(2) = 1

An alternative approach is to express the solution in terms of derangements:

A(n) = D(n) + D(n-1)

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
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Mon Apr 11, 2005 11:26 pm    Post subject: Re: inclusion/exclusion Reply with quote

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.
[...]
Inclusion-Exclusion 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 n-1.
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 n-K_sigma-1 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
n-K_tau-1 ways (for (4) from a permutation with
K_sigma = K_tau).

The recurrence you get is

A(n+1,k) = (n-k) A(n,k) + A(n,k-1) + (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,n-1) = 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! Cool

--- Christopher Heckman
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Mon Apr 11, 2005 8:57 pm    Post subject: Re: inclusion/exclusion Reply with quote

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...

Inclusion-Exclusion 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 n-1. 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
n-K_sigma-1 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
n-K_tau-1 ways (for (4) from a permutation with K_sigma = K_tau).

The recurrence you get is

A(n+1,k) = (n-k) A(n,k) + A(n,k-1) + (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
Guest






PostPosted: Sat Apr 09, 2005 5:51 am    Post subject: inclusion/exclusion Reply with 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...

Thanx for you help.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Wed Aug 23, 2017 5:48 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Algebraic and topological inclusion GT Research 0 Wed Jun 14, 2006 12:03 pm
No new posts Pauli EXCLUSiON factor k, in Big Bang GR (Bilge). brian a m stuckless Electromagnetics 0 Thu Feb 16, 2006 10:01 am
No new posts Pauli EXCLUSiON factor k, in Big Bang GR (Bilge). brian a m stuckless Math 0 Thu Feb 16, 2006 10:01 am
No new posts Pauli EXCLUSiON factor k, in Big Bang GR (Bilge). brian a m stuckless Relativity 0 Thu Feb 16, 2006 10:01 am
No new posts Inclusion or Exclusion of numbers from a list... sophie_newbie Math 4 Wed Feb 08, 2006 2:44 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0363s ][ Queries: 20 (0.0050s) ][ GZIP on - Debug on ]