|
|
| (4 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| === Sums of like powers=== | | ==A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.== |
| ==== Sums of k m-th powers >= 0====
| | The triangle starts: |
| {| class="wikitable" style="text-align:left"
| | A002 A550 A550 A550 A550 A550 A550 A550 A550 A550 A550 |
| !   !!m=2!!m=3!!m=4!!m=5!!m=6!!m=7!!m=8!!m=9!!m=10!! !! !!m=13
| | 620 278 279 280 281 282 283 284 285 286 287 |
| |-
| | n/k 1 2 3 4 5 6 7 8 9 10 11 12 |
| | k>=2 ||<span title="Sums of at least 2 squares s'', for s >= 4.">[https://oeis.org/A176209 A176209]</span>|| || || || || || || || || || || 
| | --+--------------------------------------------------------------- |
| |-
| | 1| 1 |
| | k=-1 ||<span title="Sum of square displacements over all self-avoiding n-step walks on 4-d cubic lattice with first step specified, A242355(n)/8.">[https://oeis.org/A323856 A323856]</span>||<span title="Sum of the cubes of the parts in the partitions of n into two distinct parts.">[https://oeis.org/A294287 A294287]</span>||<span title="Sum of the 4th powers of the degrees of irreducible representations of S_n, the symmetric group on n letters.">[https://oeis.org/A129627 A129627]</span>||<span title="Sum of 5th powers: 0^5 + 1^5 + 2^5 + ... + n^5.">[https://oeis.org/A000539 A000539]</span>||<span title="Sum of 6th powers: 0^6 + 1^6 + 2^6 + ... + n^6.">[https://oeis.org/A000540 A000540]</span>||<span title="Sum of 7th powers: 1^7 + 2^7 + ... + n^7.">[https://oeis.org/A000541 A000541]</span>||<span title="Numbers that are sums of 8th powers of 2 distinct positive integers.">[https://oeis.org/A155468 A155468]</span>||<span title="Sum of 9th powers.">[https://oeis.org/A007487 A007487]</span>||<span title="Sum of 10th powers.">[https://oeis.org/A023002 A023002]</span>|| || ||<span title="Sum of 13th powers: 0^13+1^13+2^13+...+n^13.">[https://oeis.org/A181134 A181134]</span>
| | 2| 1 0 |
| |-
| | 3| 1 1 0 |
| | k=2 ||<span title="Sum of two squares of Lucas numbers (A000032).">[https://oeis.org/A140328 A140328]</span>||<span title="Sums of two nonnegative cubes.">[https://oeis.org/A004999 A004999]</span>||<span title="Numbers that are the sum of two 4th powers in more than one way.">[https://oeis.org/A018786 A018786]</span>|| || || || || || || || || 
| | 4| 1 2 1 0 |
| |-
| | 5| 1 4 3 1 0 |
| | k=3 ||<span title="Numbers that are the sum of three squares (square 0 allowed) in exactly ten ways.">[https://oeis.org/A294713 A294713]</span>||<span title="Sum of three cubes problem: a(n) = integer x with the least possible absolute value such that n = x^3 + y^3 + z^3 with |x| >= |y| >= |z|, or 0 if no such x exists.">[https://oeis.org/A332201 A332201]</span>||<span title="Numbers that are the sum of three biquadrates (fourth powers) in more than one way.">[https://oeis.org/A193244 A193244]</span>|| || || || || || || || || 
| | 6| 1 6 8 4 1 0 |
| |-
| | 7| 1 9 18 14 5 1 0 |
| | k=4 || ||<span title="Numbers that are the sum of 4 cubes in more than 1 way.">[https://oeis.org/A001245 A001245]</span>|| || || || || || || || || || 
| | 8| 1 12 35 39 21 6 1 0 |
| |-
| | 9| 1 16 62 97 72 30 7 1 0 |
| |}
| | 10| 1 20 103 212 214 120 40 8 1 0 |
| ==== Sums of exactly k positive m-th powers > 0====
| | 11| 1 25 161 429 563 416 185 52 9 1 0 |
| {| class="wikitable" style="text-align:left"
| | 12| 1 30 241 804 1344 1268 732 270 65 10 1 0 |
| !   !!m=2!!m=3!!m=4!!m=5!!m=6!!m=7!!m=8!!m=9!!m=10!!m=11
| | 13| 1 36 348 1427 2958 3499 2544 1203 378 80 11 1 0 |
| |-
| | For some columns, an o.g.f. is already given or conjectured: |
| | k=2 ||<span title="Numbers that are the sum of 2 nonzero squares, including repetitions.">[https://oeis.org/A024509 A024509]</span>||<span title="Numbers that are the sum of 2 positive cubes.">[https://oeis.org/A003325 A003325]</span>||<span title="Numbers that are the sum of 2 positive 4th powers.">[https://oeis.org/A003336 A003336]</span>||<span title="Numbers that are the sum of 2 positive 5th powers.">[https://oeis.org/A003347 A003347]</span>||<span title="Numbers that are the sum of 2 nonzero 6th powers.">[https://oeis.org/A003358 A003358]</span>||<span title="Numbers that are the sum of 2 positive 7th powers.">[https://oeis.org/A003369 A003369]</span>||<span title="Numbers that are the sum of 2 nonzero 8th powers.">[https://oeis.org/A003380 A003380]</span>||<span title="Numbers that are the sum of 2 positive 9th powers.">[https://oeis.org/A003391 A003391]</span>||<span title="Numbers that are the sum of 2 nonzero 10th powers.">[https://oeis.org/A004802 A004802]</span>||<span title="Numbers that are the sum of 2 positive 11th powers.">[https://oeis.org/A004813 A004813]</span>
| | A002620 (column 2): x^2 / ((1+x)*(1-x)^3) |
| |-
| | A055278 (column 3): x^4*(x^3+x^2+1) / ((1-x^2)*(1-x^3)*(1-x)^3) |
| | k=3 ||<span title="Numbers that are the sum of 3 nonzero squares, including repetitions.">[https://oeis.org/A024795 A024795]</span>||<span title="Numbers that are the sum of 3 positive cubes, including repetitions.">[https://oeis.org/A024981 A024981]</span>||<span title="Numbers that are the sum of 3 nonzero 4th powers in more than one way.">[https://oeis.org/A309762 A309762]</span>||<span title="Numbers that are the sum of 3 positive 5th powers.">[https://oeis.org/A003348 A003348]</span>||<span title="Numbers that are the sum of 3 nonzero 6th powers.">[https://oeis.org/A003359 A003359]</span>||<span title="Numbers that are the sum of 3 positive 7th powers.">[https://oeis.org/A003370 A003370]</span>||<span title="Numbers that are the sum of 3 nonzero 8th powers.">[https://oeis.org/A003381 A003381]</span>||<span title="Numbers that are the sum of 3 positive 9th powers.">[https://oeis.org/A003392 A003392]</span>||<span title="Numbers that are the sum of 3 nonzero 10th powers.">[https://oeis.org/A004803 A004803]</span>||<span title="Numbers that are the sum of 3 positive 11th powers.">[https://oeis.org/A004814 A004814]</span>
| | A055279 (column 4): x^5*(1+x+3*x^2+5*x^3+7*x^4+5*x^5+5*x^6+2*x^7+x^8) / ((1-x)^3*(1-x^2)^2*(1-x^3)*(1-x^4)) |
| |-
| | "Guessed" o.g.f.s (with Maple's <code>guessgf</code>) show denominators that are products of cyclotomic polynomials. The following factorizations of the denominators are obtained: |
| | k=4 ||<span title="Numbers that are the sum of 4 nonzero squares.">[https://oeis.org/A000414 A000414]</span>|| ||<span title="Numbers that are the sum of 4 nonzero 4th powers in more than one way.">[https://oeis.org/A309763 A309763]</span>||<span title="Numbers that are the sum of 4 positive 5th powers.">[https://oeis.org/A003349 A003349]</span>||<span title="Numbers that are the sum of 4 positive 6th powers.">[https://oeis.org/A003360 A003360]</span>||<span title="Numbers that are the sum of 4 positive 7th powers.">[https://oeis.org/A003371 A003371]</span>||<span title="Numbers that are the sum of 4 nonzero 8th powers.">[https://oeis.org/A003382 A003382]</span>||<span title="Numbers that are the sum of 4 positive 9th powers.">[https://oeis.org/A003393 A003393]</span>||<span title="Numbers that are the sum of 4 nonzero 10th powers.">[https://oeis.org/A004804 A004804]</span>||<span title="Numbers that are the sum of 4 positive 11th powers.">[https://oeis.org/A004815 A004815]</span>
| | deo[2 ] := (x^2-1) *(x-1)^2; |
| |-
| | deo[3 ] := (x^3-1) *(x^2-1) *(x-1)^3; |
| | k=5 ||<span title="Numbers that are the sum of 5 positive squares.">[https://oeis.org/A047700 A047700]</span>||<span title="Numbers that are the sum of 5 positive cubes.">[https://oeis.org/A003328 A003328]</span>||<span title="Numbers that are the sum of 5 positive 4th powers.">[https://oeis.org/A003339 A003339]</span>||<span title="Numbers that are the sum of 5 positive 5th powers.">[https://oeis.org/A003350 A003350]</span>||<span title="Numbers that are the sum of 5 positive 6th powers.">[https://oeis.org/A003361 A003361]</span>||<span title="Numbers that are the sum of 5 positive 7th powers.">[https://oeis.org/A003372 A003372]</span>||<span title="Numbers that are the sum of 5 nonzero 8th powers.">[https://oeis.org/A003383 A003383]</span>||<span title="Numbers that are the sum of 5 positive 9th powers.">[https://oeis.org/A003394 A003394]</span>||<span title="Numbers that are the sum of 5 positive 10th powers.">[https://oeis.org/A004805 A004805]</span>||<span title="Numbers that are the sum of 5 positive 11th powers.">[https://oeis.org/A004816 A004816]</span>
| | deo[4 ] := (x^4-1) *(x^3-1) *(x^2-1)^2*(x-1)^3; |
| |-
| | deo[5 ] := (x^5-1) *(x^4-1) *(x^2-1)^2*(x-1)^5; |
| | k=6 || ||<span title="Numbers that are the sum of 6 positive cubes.">[https://oeis.org/A003329 A003329]</span>||<span title="Numbers that are the sum of 6 positive 4th powers.">[https://oeis.org/A003340 A003340]</span>||<span title="Numbers that are the sum of 6 positive 5th powers.">[https://oeis.org/A003351 A003351]</span>||<span title="Numbers that are the sum of 6 positive 6th powers.">[https://oeis.org/A003362 A003362]</span>||<span title="Numbers that are the sum of 6 positive 7th powers.">[https://oeis.org/A003373 A003373]</span>||<span title="Numbers that are the sum of 6 nonzero 8th powers.">[https://oeis.org/A003384 A003384]</span>||<span title="Numbers that are the sum of 6 positive 9th powers.">[https://oeis.org/A003395 A003395]</span>||<span title="Numbers that are the sum of 6 positive 10th powers.">[https://oeis.org/A004806 A004806]</span>||<span title="Numbers that are the sum of 6 positive 11th powers.">[https://oeis.org/A004817 A004817]</span>
| | deo[6 ] := (x^6-1) *(x^5-1) *(x^4-1) *(x^3-1)^2*(x^2-1)^3*(x-1)^3; |
| |- | | deo[7 ] := (x^7-1)*(x^6-1) *(x^5-1) *(x^4-1) *(x^3-1)^2*(x^2-1)^3*(x-1)^4; |
| | k=7 || ||<span title="Numbers that are the sum of 7 positive cubes.">[https://oeis.org/A003330 A003330]</span>||<span title="Numbers that are the sum of 7 positive 4th powers.">[https://oeis.org/A003341 A003341]</span>||<span title="Numbers that are the sum of 7 positive 5th powers.">[https://oeis.org/A003352 A003352]</span>||<span title="Numbers that are the sum of 7 positive 6th powers.">[https://oeis.org/A003363 A003363]</span>||<span title="Numbers that are the sum of 7 positive 7th powers.">[https://oeis.org/A003374 A003374]</span>||<span title="Numbers that are the sum of 7 nonzero 8th powers.">[https://oeis.org/A003385 A003385]</span>||<span title="Numbers that are the sum of 7 positive 9th powers.">[https://oeis.org/A003396 A003396]</span>||<span title="Numbers that are the sum of 7 positive 10th powers.">[https://oeis.org/A004807 A004807]</span>||<span title="Numbers that are the sum of 7 positive 11th powers.">[https://oeis.org/A004818 A004818]</span>
| | deo[8 ] := (x^8-1)*(x^7-1)*(x^6-1) *(x^5-1) *(x^4-1)^2*(x^3-1) *(x^2-1)^3*(x-1)^5; |
| |-
| | deo[9 ] := (x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1) *(x^4-1)^2*(x^3-1)^3*(x^2-1)^3*(x-1)^4; |
| | k=8 || ||<span title="Numbers that are the sum of 8 positive cubes.">[https://oeis.org/A003331 A003331]</span>||<span title="Numbers that are the sum of 8 positive 4th powers.">[https://oeis.org/A003342 A003342]</span>||<span title="Numbers that are the sum of 8 positive 5th powers.">[https://oeis.org/A003353 A003353]</span>||<span title="Numbers that are the sum of 8 positive 6th powers.">[https://oeis.org/A003364 A003364]</span>||<span title="Numbers that are the sum of 8 positive 7th powers.">[https://oeis.org/A003375 A003375]</span>||<span title="Numbers that are the sum of 8 nonzero 8th powers.">[https://oeis.org/A003386 A003386]</span>||<span title="Numbers that are the sum of 8 positive 9th powers.">[https://oeis.org/A003397 A003397]</span>||<span title="Numbers that are the sum of 8 positive 10th powers.">[https://oeis.org/A004808 A004808]</span>||<span title="Numbers that are the sum of 8 positive 11th powers.">[https://oeis.org/A004819 A004819]</span>
| | deo[10] := (x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1)^2*(x^4-1)^2*(x^3-1)^3*(x^2-1)^4*(x-1)^3; |
| |-
| | deo[11] := (x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1)^2*(x^4-1)^2*(x^3-1)^2*(x^2-1)^4*(x-1)^5; |
| | k=9 || ||<span title="Numbers that are the sum of 9 positive cubes.">[https://oeis.org/A003332 A003332]</span>||<span title="Numbers that are the sum of 9 positive 4th powers.">[https://oeis.org/A003343 A003343]</span>||<span title="Numbers that are the sum of 9 positive 5th powers.">[https://oeis.org/A003354 A003354]</span>||<span title="Numbers that are the sum of 9 positive 6th powers.">[https://oeis.org/A003365 A003365]</span>||<span title="Numbers that are the sum of 9 positive 7th powers.">[https://oeis.org/A003376 A003376]</span>||<span title="Numbers that are the sum of 9 nonzero 8th powers.">[https://oeis.org/A003387 A003387]</span>||<span title="Numbers that are the sum of 9 positive 9th powers.">[https://oeis.org/A003398 A003398]</span>||<span title="Numbers that are the sum of 9 positive 10th powers.">[https://oeis.org/A004809 A004809]</span>||<span title="Numbers that are the sum of 9 positive 11th powers.">[https://oeis.org/A004820 A004820]</span>
| | deo[12] := (x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)^2*(x^5-1)^2*(x^4-1)^3*(x^3-1)^3*(x^2-1)^3*(x-1)^4; |
| |-
| | Some pattern can be seen, but the higher exponents are not systematic. The problem is that some factors may have been cancelled out in the o.g.f.s polynomial fraction. |
| | k=10 || ||<span title="Numbers that are the sum of 10 positive cubes.">[https://oeis.org/A003333 A003333]</span>||<span title="Numbers that are the sum of 10 positive 4th powers.">[https://oeis.org/A003344 A003344]</span>||<span title="Numbers that are the sum of 10 positive 5th powers.">[https://oeis.org/A003355 A003355]</span>||<span title="Numbers that are the sum of 10 positive 6th powers.">[https://oeis.org/A003366 A003366]</span>||<span title="Numbers that are the sum of 10 positive 7th powers.">[https://oeis.org/A003377 A003377]</span>||<span title="Sum of 10 nonzero 8th powers.">[https://oeis.org/A003388 A003388]</span>||<span title="Sum of 10 positive 9th powers.">[https://oeis.org/A003399 A003399]</span>||<span title="Numbers that are the sum of 10 positive 10th powers.">[https://oeis.org/A004810 A004810]</span>||<span title="Numbers that are the sum of 10 positive 11th powers.">[https://oeis.org/A004821 A004821]</span>
| | However, by multiplying both the nominator and the denominator polynomials with such factors, the following form of the denominators can be obtained: |
| |-
| | den[2 ] := (x^2-1) *(x-1)^2 ; |
| | k=11 || ||<span title="Numbers that are the sum of 11 positive cubes.">[https://oeis.org/A003334 A003334]</span>||<span title="Numbers that are the sum of 11 positive 4th powers.">[https://oeis.org/A003345 A003345]</span>||<span title="Numbers that are the sum of 11 positive 5th powers.">[https://oeis.org/A003356 A003356]</span>||<span title="Numbers that are the sum of 11 positive 6th powers.">[https://oeis.org/A003367 A003367]</span>||<span title="Numbers that are the sum of 11 positive 7th powers.">[https://oeis.org/A003378 A003378]</span>||<span title="Numbers that are the sum of 11 positive 8th powers.">[https://oeis.org/A003389 A003389]</span>||<span title="Sum of 11 positive 9th powers.">[https://oeis.org/A004800 A004800]</span>||<span title="Numbers that are the sum of 11 positive 10th powers.">[https://oeis.org/A004811 A004811]</span>||<span title="Numbers that are the sum of 11 positive 11th powers.">[https://oeis.org/A004822 A004822]</span>
| | den[3 ] := (x^3-1) *(x^2-1) *(x-1)^3 ; |
| |-
| | den[4 ] := (x^4-1) *(x^3-1) *(x^2-1)^2*(x-1)^'''<span style="color:red">4</span>''' ; |
| | k=12 || ||<span title="Numbers that are the sum of 12 positive cubes.">[https://oeis.org/A003335 A003335]</span>||<span title="Numbers that are the sum of 12 positive 4th powers.">[https://oeis.org/A003346 A003346]</span>||<span title="Numbers that are the sum of 12 positive 5th powers.">[https://oeis.org/A003357 A003357]</span>||<span title="Numbers that are the sum of 12 positive 6th powers.">[https://oeis.org/A003368 A003368]</span>||<span title="Numbers that are the sum of 12 positive 7th powers.">[https://oeis.org/A003379 A003379]</span>||<span title="Sum of 12 nonzero 8th powers.">[https://oeis.org/A003390 A003390]</span>||<span title="Sum of 12 positive 9th powers.">[https://oeis.org/A004801 A004801]</span>||<span title="Numbers that are the sum of 12 positive 10th powers.">[https://oeis.org/A004812 A004812]</span>||<span title="Numbers that are the sum of 12 positive 11th powers.">[https://oeis.org/A004823 A004823]</span>
| | den[5 ] := (x^5-1) *(x^4-1) *(x^3-1) *(x^2-1)^2*(x-1)^5 ; |
| |-
| | den[6 ] := (x^6-1) *(x^5-1) *(x^4-1) *(x^3-1)^2*(x^2-1)^3*(x-1)^'''<span style="color:red">6</span>''' ; |
| | k=13 || || || ||<span title="Sum of 13 positive 5th powers.">[https://oeis.org/A123294 A123294]</span>|| || || || || || 
| | den[7 ] := (x^7-1)*(x^6-1) *(x^5-1) *(x^4-1) *(x^3-1)^2*(x^2-1)^3*(x-1)^'''<span style="color:red">7</span>''' ; |
| |-
| | den[8 ] := (x^8-1)*(x^7-1)*(x^6-1) *(x^5-1) *(x^4-1)^2*(x^3-1)^'''<span style="color:red">2</span>'''*(x^2-1)^'''<span style="color:red">4</span>'''*(x-1)^'''<span style="color:red">8</span>''' ; |
| | k=14 || || || ||<span title="Sum of 14 positive 5th powers.">[https://oeis.org/A123295 A123295]</span>|| || || || || || 
| | den[9 ] := (x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1) *(x^4-1)^2*(x^3-1)^3*(x^2-1)^'''<span style="color:red">4</span>'''*(x-1)^'''<span style="color:red">9</span>''' ; |
| |-
| | den[10] := (x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1)^2*(x^4-1)^2*(x^3-1)^3*(x^2-1)^'''<span style="color:red">5</span>'''*(x-1)^'''<span style="color:red">10</span>'''; |
| |}
| | den[11] := (x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1)^2*(x^4-1)^2*(x^3-1)^'''<span style="color:red">3</span>'''*(x^2-1)^'''<span style="color:red">5</span>'''*(x-1)^'''<span style="color:red">11</span>'''; |
| ==== Sums of at most k positive m-th powers > 0====
| | den[12] := (x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)^2*(x^5-1)^2*(x^4-1)^3*(x^3-1)^'''<span style="color:red">4</span>'''*(x^2-1)^'''<span style="color:red">6</span>'''*(x-1)^'''<span style="color:red">12</span>'''; |
| {| class="wikitable" style="text-align:left"
| | Here, the exponents increase in groups of 1 for <code>(x-1)</code>, in groups of 2 for <code>(x^2-1)</code>, in groups of 3 for <code>(x^3-1)</code>, etc. |
| !   !!m=3!!m=4!!m=5!!m=6!!m=7!!m=8!!m=9!!m=10!!m=11
| | Please note that this widening of the g.f.'s denominator polynomials must also be done for the numerator polynomials, but that the initial terms of the sequence remain unaffected. |
| |-
| | The advantage of this deliberate increase of degree in both polynomials is the simple and easy formula for the exponents of <code>(x^m-1)</code> in the denominators. |
| | k<=2 || ||<span title="Numbers that are the sum of at most 2 nonzero 4th powers.">[https://oeis.org/A004831 A004831]</span>||<span title="Numbers that are the sum of at most 2 positive 5th powers.">[https://oeis.org/A004842 A004842]</span>||<span title="Numbers that are the sum of at most 2 nonzero 6th powers.">[https://oeis.org/A004853 A004853]</span>||<span title="Numbers that are the sum of at most 2 positive 7th powers.">[https://oeis.org/A004864 A004864]</span>||<span title="Numbers that are the sum of at most 2 nonzero 8th powers.">[https://oeis.org/A004875 A004875]</span>||<span title="Numbers that are the sum of at most 2 positive 9th powers.">[https://oeis.org/A004886 A004886]</span>||<span title="Numbers that are the sum of at most 2 nonzero 10th powers.">[https://oeis.org/A004897 A004897]</span>||<span title="Numbers that are the sum of at most 2 positive 11th powers.">[https://oeis.org/A004908 A004908]</span>
| | |
| |-
| | These exponents turn out to be the reversed rows of A010766. The latter has a very simple formula <code>T(n,k) = floor(n/k)</code> and starts: |
| | k<=3 ||<span title="Numbers that are the sum of at most 3 positive cubes.">[https://oeis.org/A004825 A004825]</span>||<span title="Numbers that are the sum of at most 3 nonzero 4th powers.">[https://oeis.org/A004832 A004832]</span>||<span title="Numbers that are the sum of at most 3 positive 5th powers.">[https://oeis.org/A004843 A004843]</span>||<span title="Numbers that are the sum of at most 3 nonzero 6th powers.">[https://oeis.org/A004854 A004854]</span>||<span title="Numbers that are the sum of at most 3 positive 7th powers.">[https://oeis.org/A004865 A004865]</span>||<span title="Numbers that are the sum of at most 3 nonzero 8th powers.">[https://oeis.org/A004876 A004876]</span>||<span title="Numbers that are the sum of at most 3 positive 9th powers.">[https://oeis.org/A004887 A004887]</span>||<span title="Numbers that are the sum of at most 3 nonzero 10th powers.">[https://oeis.org/A004898 A004898]</span>||<span title="Numbers that are the sum of at most 3 positive 11th powers.">[https://oeis.org/A004909 A004909]</span>
| | n/k 1 2 3 4 5 6 7 8 9 10 11 12 |
| |-
| | ---+------------------------------------ |
| | k<=4 ||<span title="Numbers that are the sum of at most 4 positive cubes.">[https://oeis.org/A004826 A004826]</span>||<span title="Numbers that are the sum of at most 4 nonzero 4th powers.">[https://oeis.org/A004833 A004833]</span>||<span title="Numbers that are the sum of at most 4 positive 5th powers.">[https://oeis.org/A004844 A004844]</span>||<span title="Numbers that are the sum of at most 4 nonzero 6th powers.">[https://oeis.org/A004855 A004855]</span>||<span title="Numbers that are the sum of at most 4 positive 7th powers.">[https://oeis.org/A004866 A004866]</span>||<span title="Numbers that are the sum of at most 4 nonzero 8th powers.">[https://oeis.org/A004877 A004877]</span>||<span title="Numbers that are the sum of at most 4 positive 9th powers.">[https://oeis.org/A004888 A004888]</span>||<span title="Numbers that are the sum of at most 4 nonzero 10th powers.">[https://oeis.org/A004899 A004899]</span>||<span title="Numbers that are the sum of at most 4 positive 11th powers.">[https://oeis.org/A004910 A004910]</span>
| | 1 | 1 |
| |-
| | 2 | 2 1 |
| | k<=5 ||<span title="Numbers that are the sum of at most 5 positive cubes.">[https://oeis.org/A004827 A004827]</span>||<span title="Numbers that are the sum of at most 5 nonzero 4th powers.">[https://oeis.org/A004834 A004834]</span>||<span title="Numbers that are the sum of at most 5 positive 5th powers.">[https://oeis.org/A004845 A004845]</span>||<span title="Numbers that are the sum of at most 5 nonzero 6th powers.">[https://oeis.org/A004856 A004856]</span>||<span title="Numbers that are the sum of at most 5 positive 7th powers.">[https://oeis.org/A004867 A004867]</span>||<span title="Numbers that are the sum of at most 5 nonzero 8th powers.">[https://oeis.org/A004878 A004878]</span>||<span title="Numbers that are the sum of at most 5 positive 9th powers.">[https://oeis.org/A004889 A004889]</span>||<span title="Numbers that are the sum of at most 5 nonzero 10th powers.">[https://oeis.org/A004900 A004900]</span>||<span title="Numbers that are the sum of at most 5 positive 11th powers.">[https://oeis.org/A004911 A004911]</span>
| | 3 | 3 1 1 |
| |-
| | 4 | 4 2 1 1 |
| | k<=6 ||<span title="Numbers that are the sum of at most 6 positive cubes.">[https://oeis.org/A004828 A004828]</span>||<span title="Numbers that are the sum of at most 6 nonzero 4th powers.">[https://oeis.org/A004835 A004835]</span>||<span title="Numbers that are the sum of at most 6 positive 5th powers.">[https://oeis.org/A004846 A004846]</span>||<span title="Numbers that are the sum of at most 6 nonzero 6th powers.">[https://oeis.org/A004857 A004857]</span>||<span title="Numbers that are the sum of at most 6 positive 7th powers.">[https://oeis.org/A004868 A004868]</span>||<span title="Numbers that are the sum of at most 6 nonzero 8th powers.">[https://oeis.org/A004879 A004879]</span>||<span title="Numbers that are the sum of at most 6 positive 9th powers.">[https://oeis.org/A004890 A004890]</span>||<span title="Numbers that are the sum of at most 6 nonzero 10th powers.">[https://oeis.org/A004901 A004901]</span>||<span title="Numbers that are the sum of at most 6 positive 11th powers.">[https://oeis.org/A004912 A004912]</span>
| | 5 | 5 2 1 1 1 |
| |-
| | 6 | 6 3 2 1 1 1 |
| | k<=7 ||<span title="Numbers that are the sum of at most 7 positive cubes.">[https://oeis.org/A004829 A004829]</span>||<span title="Numbers that are the sum of at most 7 nonzero 4th powers.">[https://oeis.org/A004836 A004836]</span>||<span title="Numbers that are the sum of at most 7 positive 5th powers.">[https://oeis.org/A004847 A004847]</span>||<span title="Numbers that are the sum of at most 7 nonzero 6th powers.">[https://oeis.org/A004858 A004858]</span>||<span title="Numbers that are the sum of at most 7 positive 7th powers.">[https://oeis.org/A004869 A004869]</span>||<span title="Numbers that are the sum of at most 7 nonzero 8th powers.">[https://oeis.org/A004880 A004880]</span>||<span title="Numbers that are the sum of at most 7 positive 9th powers.">[https://oeis.org/A004891 A004891]</span>||<span title="Numbers that are the sum of at most 7 nonzero 10th powers.">[https://oeis.org/A004902 A004902]</span>||<span title="Numbers that are the sum of at most 7 positive 11th powers.">[https://oeis.org/A004913 A004913]</span>
| | 7 | 7 3 2 1 1 1 1 |
| |-
| | 8 | 8 4 2 2 1 1 1 1 |
| | k<=8 ||<span title="Numbers that are the sum of at most 8 positive cubes.">[https://oeis.org/A004830 A004830]</span>||<span title="Numbers that are the sum of at most 8 nonzero 4th powers.">[https://oeis.org/A004837 A004837]</span>||<span title="Numbers that are the sum of at most 8 positive 5th powers.">[https://oeis.org/A004848 A004848]</span>||<span title="Numbers that are the sum of at most 8 nonzero 6th powers.">[https://oeis.org/A004859 A004859]</span>||<span title="Numbers that are the sum of at most 8 positive 7th powers.">[https://oeis.org/A004870 A004870]</span>||<span title="Numbers that are the sum of at most 8 nonzero 8th powers.">[https://oeis.org/A004881 A004881]</span>||<span title="Numbers that are the sum of at most 8 positive 9th powers.">[https://oeis.org/A004892 A004892]</span>||<span title="Numbers that are the sum of at most 8 nonzero 10th powers.">[https://oeis.org/A004903 A004903]</span>||<span title="Numbers that are the sum of at most 8 positive 11th powers.">[https://oeis.org/A004914 A004914]</span>
| | 9 | 9 4 3 2 1 1 1 1 1 |
| |-
| | 10 | 10 5 3 2 2 1 1 1 1 1 |
| | k<=9 || ||<span title="Numbers that are the sum of at most 9 nonzero 4th powers.">[https://oeis.org/A004838 A004838]</span>||<span title="Numbers that are the sum of at most 9 positive 5th powers.">[https://oeis.org/A004849 A004849]</span>||<span title="Numbers that are the sum of at most 9 nonzero 6th powers.">[https://oeis.org/A004860 A004860]</span>||<span title="Numbers that are the sum of at most 9 positive 7th powers.">[https://oeis.org/A004871 A004871]</span>||<span title="Numbers that are the sum of at most 9 nonzero 8th powers.">[https://oeis.org/A004882 A004882]</span>||<span title="Numbers that are the sum of at most 9 positive 9th powers.">[https://oeis.org/A004893 A004893]</span>||<span title="Numbers that are the sum of at most 9 nonzero 10th powers.">[https://oeis.org/A004904 A004904]</span>||<span title="Numbers that are the sum of at most 9 positive 11th powers.">[https://oeis.org/A004915 A004915]</span>
| | 11 | 11 5 3 2 2 1 1 1 1 1 1 |
| |-
| | 12 | 12 6 4 3 2 2 1 1 1 1 1 1 |
| | k<=10 || ||<span title="Numbers that are the sum of at most 10 nonzero 4th powers.">[https://oeis.org/A004839 A004839]</span>||<span title="Numbers that are the sum of at most 10 positive 5th powers.">[https://oeis.org/A004850 A004850]</span>||<span title="Numbers that are the sum of at most 10 nonzero 6th powers.">[https://oeis.org/A004861 A004861]</span>||<span title="Numbers that are the sum of at most 10 positive 7th powers.">[https://oeis.org/A004872 A004872]</span>||<span title="Numbers that are the sum of at most 10 nonzero 8th powers.">[https://oeis.org/A004883 A004883]</span>||<span title="Numbers that are the sum of at most 10 positive 9th powers.">[https://oeis.org/A004894 A004894]</span>||<span title="Numbers that are the sum of at most 10 nonzero 10th powers.">[https://oeis.org/A004905 A004905]</span>||<span title="Numbers that are the sum of at most 10 positive 11th powers.">[https://oeis.org/A004916 A004916]</span>
| | |
| |-
| | In order to support this hypothesis, the following steps were performed: |
| | k<=11 || ||<span title="Numbers that are the sum of at most 11 nonzero 4th powers.">[https://oeis.org/A004840 A004840]</span>||<span title="Numbers that are the sum of at most 11 positive 5th powers.">[https://oeis.org/A004851 A004851]</span>||<span title="Numbers that are the sum of at most 11 nonzero 6th powers.">[https://oeis.org/A004862 A004862]</span>||<span title="Numbers that are the sum of at most 11 positive 7th powers.">[https://oeis.org/A004873 A004873]</span>||<span title="Numbers that are the sum of at most 11 nonzero 8th powers.">[https://oeis.org/A004884 A004884]</span>||<span title="Numbers that are the sum of at most 11 positive 9th powers.">[https://oeis.org/A004895 A004895]</span>||<span title="Numbers that are the sum of at most 11 nonzero 10th powers.">[https://oeis.org/A004906 A004906]</span>||<span title="Numbers that are the sum of at most 11 positive 11th powers.">[https://oeis.org/A004917 A004917]</span>
| | # Determine the denomiator polynomials <code>den</code> above, and take their coefficients as the signature for a linear recurrence with constant coefficients. |
| |-
| | # Compute a sufficient number of terms (150 - 270) for the column sequences A055278-A055287 with Michale Somos' PARI program in A055277. This took about 1 day. |
| | k<=12 || ||<span title="Numbers that are the sum of at most 12 nonzero 4th powers.">[https://oeis.org/A004841 A004841]</span>||<span title="Numbers that are the sum of at most 12 positive 5th powers.">[https://oeis.org/A004852 A004852]</span>||<span title="Numbers that are the sum of at most 12 nonzero 6th powers.">[https://oeis.org/A004863 A004863]</span>||<span title="Numbers that are the sum of at most 12 positive 7th powers.">[https://oeis.org/A004874 A004874]</span>||<span title="Numbers that are the sum of at most 12 nonzero 8th powers.">[https://oeis.org/A004885 A004885]</span>||<span title="Numbers that are the sum of at most 12 positive 9th powers.">[https://oeis.org/A004896 A004896]</span>||<span title="Numbers that are the sum of at most 12 nonzero 10th powers.">[https://oeis.org/A004907 A004907]</span>||<span title="Numbers that are the sum of at most 12 positive 11th powers.">[https://oeis.org/A004918 A004918]</span>
| | # Take <code>degree(den[n])</code> initial terms from step 2, run the linear recurrence and verify it for all terms. |
| |-
| | |
| |}
| | In fact, the initial terms could have been been prefixed by <code>n</code> zeros, but in the OEIS sequences the leading zeros are omitted. |
| ==== Sums of k positive m-th powers > 1====
| |
| {| class="wikitable" style="text-align:left"
| |
| !   !!m=2!!m=3
| |
| |-
| |
| | k=-1 || ||<span title="Numbers which can be written as sum of cubes > 1.">[https://oeis.org/A078131 A078131]</span>
| |
| |-
| |
| | k=2 || ||<span title="Numbers that are the sum of 2 cubes > 1.">[https://oeis.org/A294073 A294073]</span>
| |
| |-
| |
| | k=3 ||<span title="Numbers that are the sum of 3 squares > 1.">[https://oeis.org/A302359 A302359]</span>||<span title="Numbers that are the sum of 3 cubes > 1.">[https://oeis.org/A302360 A302360]</span>
| |
| |-
| |
| |}
| |
| ==== Numbers n having exactly k representations as the sum of m squares >= 0====
| |
| <!--A295158 quant_eq ten representations as the sum of five least_0 pow_2. -->
| |
| {| class="wikitable" style="text-align:left"
| |
| !   !!m=2!! !! !!m=5!!m=6!!m=7
| |
| |-
| |
| | k=1 || || || || ||<span title="Numbers that have exactly one representation as a sum of six nonnegative squares.">[https://oeis.org/A295484 A295484]</span>|| 
| |
| |-
| |
| | k=2 ||<span title="Numbers that are the sum of 2 squares in exactly 2 ways.">[https://oeis.org/A085625 A085625]</span>|| || ||<span title="Numbers that have exactly two representations as a sum of five nonnegative squares.">[https://oeis.org/A295150 A295150]</span>||<span title="Numbers that have exactly two representations as a sum of six nonnegative squares.">[https://oeis.org/A295485 A295485]</span>||<span title="Numbers that have exactly two representations of a sum of seven nonnegative squares.">[https://oeis.org/A295742 A295742]</span>
| |
| |-
| |
| | k=3 ||<span title="Numbers that are the sum of 2 squares in exactly 3 ways.">[https://oeis.org/A000443 A000443]</span>|| || ||<span title="Numbers that have exactly three representations as a sum of five nonnegative squares.">[https://oeis.org/A295151 A295151]</span>||<span title="Numbers that have exactly three representations as a sum of six nonnegative squares.">[https://oeis.org/A295486 A295486]</span>||<span title="Numbers that have exactly three representations of a sum of seven nonnegative squares.">[https://oeis.org/A295743 A295743]</span>
| |
| |-
| |
| | k=4 || || || ||<span title="Numbers that have exactly four representations as a sum of five nonnegative squares.">[https://oeis.org/A295152 A295152]</span>||<span title="Numbers that have exactly four representations as a sum of six nonnegative squares.">[https://oeis.org/A295487 A295487]</span>||<span title="Numbers that have exactly four representations of a sum of seven nonnegative squares.">[https://oeis.org/A295744 A295744]</span>
| |
| |-
| |
| | k=5 ||<span title="Numbers that are the sum of 2 squares in exactly 5 ways.">[https://oeis.org/A294716 A294716]</span>|| || ||<span title="Numbers that have exactly five representations as a sum of five nonnegative squares.">[https://oeis.org/A295153 A295153]</span>||<span title="Numbers that have exactly five representations as a sum of six nonnegative squares.">[https://oeis.org/A295488 A295488]</span>||<span title="Numbers that have exactly five representations of a sum of seven nonnegative squares.">[https://oeis.org/A295745 A295745]</span>
| |
| |-
| |
| | k=6 || || || ||<span title="Numbers that have exactly six representations as a sum of five nonnegative squares.">[https://oeis.org/A295154 A295154]</span>||<span title="Numbers that have exactly six representations as a sum of six nonnegative squares.">[https://oeis.org/A295489 A295489]</span>||<span title="Numbers that have exactly six representations of a sum of seven nonnegative squares.">[https://oeis.org/A295747 A295747]</span>
| |
| |-
| |
| | k=7 || || || ||<span title="Numbers that have exactly seven representations as a sum of five nonnegative squares.">[https://oeis.org/A295155 A295155]</span>||<span title="Numbers that have exactly seven representations as a sum of six nonnegative squares.">[https://oeis.org/A295490 A295490]</span>||<span title="Numbers that have exactly seven representations of a sum of seven nonnegative squares.">[https://oeis.org/A295748 A295748]</span>
| |
| |-
| |
| | k=8 || || || ||<span title="Numbers that have exactly eight representations as a sum of five nonnegative squares.">[https://oeis.org/A295156 A295156]</span>||<span title="Numbers that have exactly eight representations as a sum of six nonnegative squares.">[https://oeis.org/A295491 A295491]</span>||<span title="Numbers that have exactly eight representations of a sum of seven nonnegative squares.">[https://oeis.org/A295749 A295749]</span>
| |
| |-
| |
| | k=9 || || || ||<span title="Numbers that have exactly nine representations as a sum of five nonnegative squares.">[https://oeis.org/A295157 A295157]</span>||<span title="Numbers that have exactly nine representations as a sum of six nonnegative squares.">[https://oeis.org/A295492 A295492]</span>||<span title="Numbers that have exactly nine representations of a sum of seven nonnegative squares.">[https://oeis.org/A295750 A295750]</span>
| |
| |-
| |
| | k=10 || || || ||<span title="Numbers that have exactly ten representations as a sum of five nonnegative squares.">[https://oeis.org/A295158 A295158]</span>||<span title="Numbers that have exactly ten representations as a sum of six nonnegative squares.">[https://oeis.org/A295493 A295493]</span>||<span title="Numbers that have exactly ten representations as a sum of seven nonnegative squares.">[https://oeis.org/A295751 A295751]</span>
| |
| |-
| |
| |}
| |
A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.
The triangle starts:
A002 A550 A550 A550 A550 A550 A550 A550 A550 A550 A550
620 278 279 280 281 282 283 284 285 286 287
n/k 1 2 3 4 5 6 7 8 9 10 11 12
--+---------------------------------------------------------------
1| 1
2| 1 0
3| 1 1 0
4| 1 2 1 0
5| 1 4 3 1 0
6| 1 6 8 4 1 0
7| 1 9 18 14 5 1 0
8| 1 12 35 39 21 6 1 0
9| 1 16 62 97 72 30 7 1 0
10| 1 20 103 212 214 120 40 8 1 0
11| 1 25 161 429 563 416 185 52 9 1 0
12| 1 30 241 804 1344 1268 732 270 65 10 1 0
13| 1 36 348 1427 2958 3499 2544 1203 378 80 11 1 0
For some columns, an o.g.f. is already given or conjectured:
A002620 (column 2): x^2 / ((1+x)*(1-x)^3)
A055278 (column 3): x^4*(x^3+x^2+1) / ((1-x^2)*(1-x^3)*(1-x)^3)
A055279 (column 4): x^5*(1+x+3*x^2+5*x^3+7*x^4+5*x^5+5*x^6+2*x^7+x^8) / ((1-x)^3*(1-x^2)^2*(1-x^3)*(1-x^4))
"Guessed" o.g.f.s (with Maple's guessgf) show denominators that are products of cyclotomic polynomials. The following factorizations of the denominators are obtained:
deo[2 ] := (x^2-1) *(x-1)^2;
deo[3 ] := (x^3-1) *(x^2-1) *(x-1)^3;
deo[4 ] := (x^4-1) *(x^3-1) *(x^2-1)^2*(x-1)^3;
deo[5 ] := (x^5-1) *(x^4-1) *(x^2-1)^2*(x-1)^5;
deo[6 ] := (x^6-1) *(x^5-1) *(x^4-1) *(x^3-1)^2*(x^2-1)^3*(x-1)^3;
deo[7 ] := (x^7-1)*(x^6-1) *(x^5-1) *(x^4-1) *(x^3-1)^2*(x^2-1)^3*(x-1)^4;
deo[8 ] := (x^8-1)*(x^7-1)*(x^6-1) *(x^5-1) *(x^4-1)^2*(x^3-1) *(x^2-1)^3*(x-1)^5;
deo[9 ] := (x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1) *(x^4-1)^2*(x^3-1)^3*(x^2-1)^3*(x-1)^4;
deo[10] := (x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1)^2*(x^4-1)^2*(x^3-1)^3*(x^2-1)^4*(x-1)^3;
deo[11] := (x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1)^2*(x^4-1)^2*(x^3-1)^2*(x^2-1)^4*(x-1)^5;
deo[12] := (x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)^2*(x^5-1)^2*(x^4-1)^3*(x^3-1)^3*(x^2-1)^3*(x-1)^4;
Some pattern can be seen, but the higher exponents are not systematic. The problem is that some factors may have been cancelled out in the o.g.f.s polynomial fraction.
However, by multiplying both the nominator and the denominator polynomials with such factors, the following form of the denominators can be obtained:
den[2 ] := (x^2-1) *(x-1)^2 ;
den[3 ] := (x^3-1) *(x^2-1) *(x-1)^3 ;
den[4 ] := (x^4-1) *(x^3-1) *(x^2-1)^2*(x-1)^4 ;
den[5 ] := (x^5-1) *(x^4-1) *(x^3-1) *(x^2-1)^2*(x-1)^5 ;
den[6 ] := (x^6-1) *(x^5-1) *(x^4-1) *(x^3-1)^2*(x^2-1)^3*(x-1)^6 ;
den[7 ] := (x^7-1)*(x^6-1) *(x^5-1) *(x^4-1) *(x^3-1)^2*(x^2-1)^3*(x-1)^7 ;
den[8 ] := (x^8-1)*(x^7-1)*(x^6-1) *(x^5-1) *(x^4-1)^2*(x^3-1)^2*(x^2-1)^4*(x-1)^8 ;
den[9 ] := (x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1) *(x^4-1)^2*(x^3-1)^3*(x^2-1)^4*(x-1)^9 ;
den[10] := (x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1)^2*(x^4-1)^2*(x^3-1)^3*(x^2-1)^5*(x-1)^10;
den[11] := (x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1) *(x^5-1)^2*(x^4-1)^2*(x^3-1)^3*(x^2-1)^5*(x-1)^11;
den[12] := (x^12-1)*(x^11-1)*(x^10-1)*(x^9-1)*(x^8-1)*(x^7-1)*(x^6-1)^2*(x^5-1)^2*(x^4-1)^3*(x^3-1)^4*(x^2-1)^6*(x-1)^12;
Here, the exponents increase in groups of 1 for (x-1), in groups of 2 for (x^2-1), in groups of 3 for (x^3-1), etc.
Please note that this widening of the g.f.'s denominator polynomials must also be done for the numerator polynomials, but that the initial terms of the sequence remain unaffected.
The advantage of this deliberate increase of degree in both polynomials is the simple and easy formula for the exponents of (x^m-1) in the denominators.
These exponents turn out to be the reversed rows of A010766. The latter has a very simple formula T(n,k) = floor(n/k) and starts:
n/k 1 2 3 4 5 6 7 8 9 10 11 12
---+------------------------------------
1 | 1
2 | 2 1
3 | 3 1 1
4 | 4 2 1 1
5 | 5 2 1 1 1
6 | 6 3 2 1 1 1
7 | 7 3 2 1 1 1 1
8 | 8 4 2 2 1 1 1 1
9 | 9 4 3 2 1 1 1 1 1
10 | 10 5 3 2 2 1 1 1 1 1
11 | 11 5 3 2 2 1 1 1 1 1 1
12 | 12 6 4 3 2 2 1 1 1 1 1 1
In order to support this hypothesis, the following steps were performed:
- Determine the denomiator polynomials
den above, and take their coefficients as the signature for a linear recurrence with constant coefficients.
- Compute a sufficient number of terms (150 - 270) for the column sequences A055278-A055287 with Michale Somos' PARI program in A055277. This took about 1 day.
- Take
degree(den[n]) initial terms from step 2, run the linear recurrence and verify it for all terms.
In fact, the initial terms could have been been prefixed by n zeros, but in the OEIS sequences the leading zeros are omitted.