Discrete Mathematics · Induction, recursion, and invariants
[Honors] Using inclusion-exclusion, find the number of permutations π of {1,2,…,9} such…
Problem
[Honors] Using inclusion-exclusion, find the number of permutations \(\pi\) of \(\{1,2,\ldots,9\}\) such that no even integer appears in its natural position: that is, \(\pi(2)\ne 2\), \(\pi(4)\ne 4\), \(\pi(6)\ne 6\), and \(\pi(8)\ne 8\). (Odd integers are unrestricted.)
Hint
Only four positions are restricted; this is inclusion-exclusion on those four “forbidden fixed points,” not a full derangement of nine items.
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Discrete Mathematics sample problem: Try the free sample problem.
More Discrete Mathematics practice problems
- Let p, q, and r be propositionsPropositional and predicate logic with proof methods
- Let A={1,2,3,4} and B={3,4,5,6}Propositional and predicate logic with proof methods
- Let R be a relation on a set ASets, functions, relations, and equivalence classes
- Use strong induction to prove that every positive integer n can be written as n=2^k m…Sets, functions, relations, and equivalence classes
- (Honors) Let u_n be defined by u_0=0, u_1=1, and u_n=4u_(n-1)-4u_(n-2)+n for n≥ 2Induction, recursion, and invariants
- Let n be a positive integerRecurrences, generating functions, and discrete asymptotics
- RSA decryption needs Euler, and Euler needs a coprime messageDivisibility, modular arithmetic, and elementary number theory
- Four labs sharing ten hours cannot exceed a per-lab capCombinatorics and inclusion-exclusion
- BFS two-coloring is the certificate that no odd cycle existsGraphs, trees, connectivity, and matchings