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

$$\left|S\right| - \sum \left|A_{1}\right| + \sum \left|A_{1} \cap A_{2}\right| -...$$

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

 

[pupeye11]

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

$$\begin{pmatrix}7\\4\end{pmatrix}$$

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

$$\begin{pmatrix}7\\4\end{pmatrix} D_{3}$$

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.