Talk:Main Page
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))
When o.g.f.s for higher columns are "guessed" (with Maple's guessgf), it turns out that the denominators are all 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 some factor, 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.
The triangle of the exponents turns out to be A010766 (with rows reversed). 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
denabove, 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 recurrence and verify it for all terms.
In fact, the initial terms could be prefixed by n zeros.