Inclusion/Exclusion Combinatorics

[pupeye11]

Homework Statement

Determine the number of permutations of {1,2,3,4,5,6,7} in which exactly four integers are in there natural positions.

The Attempt at a Solution

Would this be solved by using the Inclusion/Exclusion Principle and finding

<br /> \left|S\right| - \sum \left|A_{1}\right| + \sum \left|A_{1} \cap A_{2}\right| -...<br />

where i={1,2,3,4,5,6,7}

 

[pupeye11]

Wait the easier way to do this would be to say there are

<br /> \begin{pmatrix}7\\4\end{pmatrix}<br />

while the other 3 integers will form a derangement, so the answer would be

<br /> \begin{pmatrix}7\\4\end{pmatrix} D_{3}<br />

Is that correct?

 

[Tedjn]

Yes. What is your value for D₃?

 

[pupeye11]

Came out to 2 so my answer was 70

 

[Tedjn]

It seems good to me.

 

[pupeye11]

Is a non-recursive formula a formula that only works for a given function and parameters?

 

[Tedjn]

What do you mean given function and parameters? As far as I know, a non-recursive formula is one not defined in terms of previous terms.

 

[pupeye11]

Well the question states as follows:

The sequence f_n is defined by f_0=f_1=2 and

f_n = (\frac{f_{n-1}+2f_{n-2}}{6}), when n\geq2.

Find a non-recursive formula for f_n

 

[Tedjn]

It's asking you to find a formula for f_n only in terms of n, not f_anything.

 

[lanedance]

so you need to only find f as a function of n alone

 

[pupeye11]

So its the same as finding a recurrence relation?

 

[Tedjn]

What you gave in the problem is the recurrence relation. You need to find what is called a "closed form." From Wikipedia: Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n.

 

[pupeye11]

Shoot, not really sure how to do that...

 

[pupeye11]

would it be the same as this problem:

solve the recurrence relation h_n = 5h_{n-1}+6h_{n-2}

subject to the initial values h_0 = 1 and h_1 = -2

 

[Tedjn]

It is similar enough that the same solution technique would likely work on both.

 

[pupeye11]

I will attempt that and post if I run into trouble. Thanks.