CombinatoricsDifficulty 4.7AIMEFind the answerUnited States
Problem: A monomial term xi1xi2…xik in the variables x1,x2,…,x8 is square-free if i1,i2,…,ik are distinct. (A constant term such as 1 is considered square-free.) What is the sum of the coefficients of the squarefree terms in the following product? 1≤i<j≤8∏(1+xixj)
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
Solution: Answer: 764 Let an be the sum of the coefficients of the square-terms in the product ∏1≤i<j≤n(1+xixj). Square-free terms in this product come in two types: either they include xn, or they do not. The sum of the coefficients of the terms that include xn is (n−1)an−2, since we can choose any of the n−1 other variables to be paired with xn, and then choose any square-free term from the product taken over the other n−2 variables. The sum of the coefficients of the terms that do not include xn are an−1, because they all come from the product over the other n−1 variables. Therefore, an=an−1+(n−1)an−2.
We use this recursion to find a8. As base cases, a0 and a1 are both 1. Then a2=2, a3=4, a4=10, a5=26, a6=76, a7=232, and finally, a8=764.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.