1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inclusion/Exclusion Combinatorics

  1. Jun 14, 2010 #1
    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. jcsd
  3. Jun 14, 2010 #2
    Wait the easier way to do this would be to say there are


    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?
  4. Jun 14, 2010 #3
    Yes. What is your value for D3?
  5. Jun 14, 2010 #4
    Came out to 2 so my answer was 70
  6. Jun 14, 2010 #5
    It seems good to me.
  7. Jun 14, 2010 #6
    Is a non-recursive formula a formula that only works for a given function and parameters?
  8. Jun 14, 2010 #7
    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.
  9. Jun 14, 2010 #8
    Well the question states as follows:

    The sequence [tex]f_n[/tex] is defined by [tex]f_0=f_1=2[/tex] and

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

    Find a non-recursive formula for [tex]f_n[/tex]
  10. Jun 14, 2010 #9
    It's asking you to find a formula for fn only in terms of n, not fanything.
  11. Jun 14, 2010 #10


    User Avatar
    Homework Helper

    so you need to only find f as a function of n alone
  12. Jun 14, 2010 #11
    So its the same as finding a recurrence relation?
  13. Jun 14, 2010 #12
    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.
  14. Jun 14, 2010 #13
    Shoot, not really sure how to do that....
  15. Jun 14, 2010 #14
    would it be the same as this problem:

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

    subject to the initial values [tex]h_0 = 1[/tex] and [tex]h_1 = -2[/tex]
  16. Jun 14, 2010 #15
    It is similar enough that the same solution technique would likely work on both.
  17. Jun 14, 2010 #16
    I will attempt that and post if I run into trouble. Thanks.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Inclusion/Exclusion Combinatorics
  1. Inclusion exclusion (Replies: 0)