Search   Memberlist   Usergroups
 Page 1 of 1 [4 Posts]
Author Message
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) = (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

- Matt
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. [...] 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!

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

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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [4 Posts]
 The time now is Wed Dec 12, 2018 3:04 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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