Inclusion/Exclusion Combinatorics

1. Jun 14, 2010

pupeye11

1. The problem statement, all variables and given/known data

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

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

2. Jun 14, 2010

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?

3. Jun 14, 2010

Tedjn

Yes. What is your value for D3?

4. Jun 14, 2010

pupeye11

Came out to 2 so my answer was 70

5. Jun 14, 2010

Tedjn

It seems good to me.

6. Jun 14, 2010

pupeye11

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

7. Jun 14, 2010

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.

8. Jun 14, 2010

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

9. Jun 14, 2010

Tedjn

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

10. Jun 14, 2010

lanedance

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

11. Jun 14, 2010

pupeye11

So its the same as finding a recurrence relation?

12. Jun 14, 2010

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.

13. Jun 14, 2010

pupeye11

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

14. Jun 14, 2010

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

15. Jun 14, 2010

Tedjn

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

16. Jun 14, 2010

pupeye11

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