For each nonnegative integer n, calculate the number of triples ( a , b , c ) of nonnegative integers which satisfy the system of inequalities below: { a + b ≤ 2 n a + c ≤ 2 n c + b ≤ 2 n

Question

For each nonnegative integer   n, calculate the number of triples   (  a  ,  b  ,  c  ) of nonnegative integers which satisfy the system of inequalities below:      {                            a          +          b          ≤          2          n                                      a          +          c          ≤          2          n                                      c          +          b          ≤          2          n

Blaine Andrews · Accepted Answer

The constraints define an n-fold dilation of the 3-dimensional polytope with vertices (0,0,0), (1,1,0), (1,0,1), and (0,1,1). The number of lattice points is hence a cubic Ehrhart polynomial. By inspection, the counts are 1,11,42,106, for n=0,1,2,3, respectively. The resulting polynomial is hence  2      n    3    +            9              n        2              2    +            7      n        2    +  1.

Jayla Faulkner · Accepted Answer

Consider the triples   (  a  ,  b  ,  c  ) of nonnegative integers that satisfy the following relationships:      {                                      a          +          b          =          x                                      a          +          c          ≤          2          n                                      b          +          c          ≤          2          n                        Let&#039;s divide the count of these triples into two steps. In the first we consider   x  =  2  k, while in the second we consider   x  =  2  k  +  1. Thus, the   (  a  ,  b  ) pairs that satisfy   a  +  b  =  2  k are   (  2  k  ,  0  )  ,  .  .  .  ,  (  k  ,  k  )  ,  .  .  .  ,  (  0.2  k  ).For each of these pairs,   c will have to obey   c  ≤  2  n  −  M where   M  =  max  (  a  ,  b  ), which gives us   2  n  −  M  +  1 solutions. Assuming that among the   (  a  ,  b  ) pairs that satisfy the equation, the value of   M ranges from   k  +  1 to   2  k twice and then goes to   k, so the number of solutions for this case it will be:      (    2          ∑              M        =        k        +        1                    2        k              (    2    n    −    M    +    1    )    )    +  2  n  −  k  +  1  =  −  3      k    2    +  4  n  k  +  2  n  +  1For the second case, be   n  =  2  k  +  1. The difference is that we will not have the extra solution in which the components of pair   (  a  ,  b  ) are equal. Like this:      (    2          ∑              M        =        k        +        1                    2        k        +        1              (    2    k    +    1    −    M    +    1    )    )    =  −  3      k    2    +  (  4  n  −  3  )  k  +  4  nSo just calculate the sum of all cases where   a  +  b  =  0,   a  +  b  =  1,… up to   a  +  b  =  2  n and just get the sums for when   2  k  +  1  =  1  ,  3  ,  5  ,  …  ,  2  n  −  1 and sum with the sums for when   2  k  =  0  ,  2  ,  4  ,  …  ,  2  n:      ∑          k      =      0        n    3      k    2    +  4  n  k  +  2  n  +  1  +      ∑          k      =      0              n      −      1        −  3      k    2    +  (  4  n  −  3  )  k  +  4  n  =  2      n    3    +            9              n        2              2    +            11      n        2    +  1

For each nonnegative integer n , calculate the number of triples ( a , b , c ) of

Answered question

Answer & Explanation

New Questions in Algebra I