Talk:Main Page: Difference between revisions

From tehowiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
imported>Gfis
No edit summary
imported>Gfis
No edit summary
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
=== <code>b[n]q</code>: rebase from base b into base q ===
==A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 &lt;= k &lt;= n.==
In 2005, [[User:Marc_LeBrun|Marc LeBrun]] described the rebasing notation (cf. A000695):
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 <code>guessgf</code>) 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)^'''<span style="color:red">4</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>''' ;
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>''' ;
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>''';
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>''';
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.
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.


:This may be described concisely using the "rebase" notation <code>b[n]q</code>, which means "replace b with q in the expansion of n", thus rebasing" n from base b into base q. The present sequence is <code>2[n]4</code>. Many interesting operations (e.g., <code>10[n](1/10)</code> = digit reverse, shifted) are nicely expressible this way.
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:
  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


:Note that <code>q[n]b</code> is (roughly) inverse to <code>b[n]q</code>.
In order to support this hypothesis, the following steps were performed:
# 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.
# Take <code>degree(den[n])</code> initial terms from step 2, run the linear recurrence and verify it for all terms.


:It's also natural to generalize the idea of "basis" so as to cover the likes of <code>F[n]2</code>, the so-called "fibbinary" numbers (A003714) nd provide standard ready-made images of entities obeying other arithmetics, say like <code>GF2[n]2</code> (e.g., primes = A014580, squares = the present sequence, etc.).
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.
 
The following table shows relevant pertinent sequences in the OEIS:
{| class="wikitable" style="text-align:left"
! &#xa0; !!b=2!!b=3!!b=4!!b=5!!b=6!!b=7!!b=8!!b=9!!b=10
|-
| q=2 ||<center>&mdash;</center>||<span title="Rebase n from 3 to 2. Replace 3^k with 2^k in ternary expansion of n.">A065361</span>||<span title="Rebase n from 4 to 2. Replace 4^k with 2^k in quaternary expansion of n.">A065362<sup>2</sup></span>||<span title="a(n)=Sum{d(i)*2^i: i=0,1,...,m}, where Sum{d(i)*5^i: i=0,1,...,m} is the base 5 representation of n.">A215088</span>||<span title="a(n)=Sum{d(i)*6^i: i=0,1,...,m}, where Sum{d(i)*2^i: i=0,1,...,m} is the base 2 representation of n.">A215089</span>||<span title="a(n) = Sum{d(i)*2^i: i=0,1,...,m}, where Sum{d(i)*7^i: i=0,1,...,m}=n, d(i)∈{0,1,...,6}">A203580</span>||&#xa0;||&#xa0;||<span title="If n = Sum c_i 10^i then a(n) = Sum c_i 2^i.">A028897</span>
|-
| q=3 ||<span title="Numbers n whose base 3 representation contains no 2.">A005836<sup>1</sup></span>||<center>&mdash;</center>||<span title="a(n) = Sum_{i=0..m} d(i)*3^i, where Sum_{i=0..m} d(i)*4^i is the base-4 representation of n.">A215090</span>||&#xa0;||<span title="a(n) = Sum_{i=0..m} d(i)*3^i, where Sum_{i=0..m} d(i)*6^i is the base-6 representation of n.">A215092<sup>2</sup></span>||&#xa0;||&#xa0;||&#xa0;||<span title="Map n = Sum c_i 10^i to a(n) = Sum c_i 3^i.">A028898</span>
|-
| q=4 ||<span title="Moser-de Bruijn sequence: sums of distinct powers of 4.">A000695</span>||<span title="Numbers with no 3''s in base-4 expansion.">A023717</span>||<center>&mdash;</center>||<span title="a(n) = Sum_{i=0..m} d(i)*4^i, where Sum_{i=0..m} d(i)*5^i is the base-5 representation of n.">A303787</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||<span title="Map n = Sum c_i 10^i to a(n) = Sum c_i 4^i.">A028899</span>
|-
| q=5 ||<span title="Sums of distinct powers of 5.">A033042</span>||<span title="Positive numbers n such that the base 5 representation of n contains no 3 or 4.">A037453<sup>2</sup></span>||<span title="Sum{d(i)*5^i: i=0,1,...,m}, where Sum{d(i)*4^i: i=0,1,...,m} is the base 4 representation of n.">A037459<sup>2</sup></span>||<center>&mdash;</center>||<span title="a(n) = Sum_{i=0..m} d(i)*5^i, where Sum_{i=0..m} d(i)*6^i is the base-6 representation of n.">A303788</span>||&#xa0;||&#xa0;||&#xa0;||<span title="Map n = Sum c_i 10^i to a(n) = Sum c_i 5^i.">A028900</span>
|-
| q=6 ||<span title="Sums of distinct powers of 6.">A033043</span>||<span title="a(n) = Sum_{i=0..m} d(i)*6^i, where Sum_{i=0..m} d(i)*3^i is the base 3 representation of n.">A037454</span>||<span title="a(n)=Sum{d(i)*6^i: i=0,1,...,m}, where Sum{d(i)*4^i: i=0,1,...,m} is the base 4 representation of n.">A037460</span>||<span title="Sum{d(i)*6^i: i=0,1,...,m}, where Sum{d(i)*5^i: i=0,1,...,m} is the base 5 representation of n.">A037465</span>||<center>&mdash;</center>||<span title="a(n) = Sum_{i=0..m} d(i)*6^i, where Sum_{i=0..m} d(i)*7^i is the base-7 representation of n.">A303789</span>||&#xa0;||&#xa0;||<span title="Map n = Sum c_i 10^i to a(n) = Sum c_i 6^i.">A028901</span>
|-
| q=7 ||<span title="Sums of distinct powers of 7.">A033044<sup>1</sup></span>||<span title="a(n)=Sum{d(i)*7^i: i=0,1,...,m}, where Sum{d(i)*3^i: i=0,1,...,m} is the base 3 representation of n.">A037455</span>||<span title="a(n)=Sum{d(i)*7^i: i=0,1,...,m}, where Sum{d(i)*4^i: i=0,1,...,m} is the base 4 representation of n.">A037461<sup>2</sup></span>||<span title="a(n)=Sum{d(i)*7^i: i=0,1,...,m}, where Sum{d(i)*5^i: i=0,1,...,m} is the base 5 representation of n.">A037466</span>||<span title="a(n)=Sum{d(i)*7^i: i=0,1,...,m}, where Sum{d(i)*6^i: i=0,1,...,m} is the base 6 representation of n.">A037470</span>||<center>&mdash;</center>||&#xa0;||&#xa0;||<span title="Map n = Sum c_i 10^i to a(n) = Sum c_i 7^i.">A028902</span>
|-
| q=8 ||<span title="Sums of distinct powers of 8.">A033045</span>||<span title="a(n)=Sum{d(i)*8^i: i=0,1,...,m}, where Sum{d(i)*3^i: i=0,1,...,m} is the base 3 representation of n.">A037456</span>||<span title="a(n) = Sum_{i = 0..m} d(i)*8^i, where Sum_{i = 0..m} d(i)*4^i is the base 4 representation of n.">A037462</span>||<span title="Sum{d(i)*8^i: i=0,1,...,m}, where Sum{d(i)*5^i: i=0,1,...,m} is the base 5 representation of n.">A037467</span>||<span title="a(n)=Sum{d(i)*8^i: i=0,1,...,m}, where Sum{d(i)*6^i: i=0,1,...,m} is the base 6 representation of n.">A037471</span>||<span title="a(n) = Sum{d(i)*8^i: i=0,1,...,m}, where Sum{d(i)*7^i: i=0,1,...,m} is the base 7 representation of n.">A037474</span>||<center>&mdash;</center>||&#xa0;||<span title="Map n = Sum c_i 10^i to a(n) = Sum c_i 8^i.">A028903</span>
|-
| q=9 ||<span title="Sums of distinct powers of 9.">A033046</span>||&#xa0;||<span title="a(n)=Sum{d(i)*9^i: i=0,1,...,m}, where Sum{d(i)*4^i: i=0,1,...,m} is the base 4 representation of n.">A037463</span>||<span title="a(n)=Sum{d(i)*9^i: i=0,1,...,m}, where Sum{d(i)*5^i: i=0,1,...,m} is the base 5 representation of n.">A037468</span>||<span title="a(n)=Sum{d(i)*9^i: i=0,1,...,m}, where Sum{d(i)*6^i: i=0,1,...,m} is the base 6 representation of n.">A037472</span>||<span title="a(n)=Sum{d(i)*9^i: i=0,1,...,m}, where Sum{d(i)*7^i: i=0,1,...,m} is the base 7 representation of n.">A037475</span>||<span title="a(n) = Sum{d(i)*9^i: i=0,1,...,m}, where Sum{d(i)*8^i: i=0,1,...,m} is the base 8 representation of n.">A037477</span>||<center>&mdash;</center>||<span title="Map n = Sum c_i 10^i to a(n) = Sum c_i 9^i.">A028904</span>
|-
| q=10 ||<span title="The binary numbers (or binary words, or binary vectors): numbers written in base 2.">A007088</span>||<span title="Numbers in base 3.">A007089</span>||<span title="Numbers in base 4.">A007090</span>||<span title="Numbers in base 5.">A007091</span>||<span title="Numbers in base 6.">A007092</span>||<span title="Numbers in base 7.">A007093</span>||<span title="Numbers in base 8.">A007094</span>||<span title=" Numbers in base 9.">A007095</span><br><span title="a(n)=Sum{d(i)*10^i: i=0,1,...,m}, where Sum{d(i)*9^i: i=0,1,...,m} is the base 9 representation of n.">A037479<sup>2</sup></span>||<center>&mdash;</center>
|-
| q=11 ||<span title="Sums of distinct powers of 11.">A033047</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;
|-
| q=12 ||<span title="Sums of distinct powers of 12.">A033048</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||<span title="Numbers in base-12 representation that can be written with decimal digits.">A102487<sup>1</sup></span>
|-
| q=13 ||<span title="Sums of distinct powers of 13.">A033049</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||<span title="If n = c0 + c1*10 + c2*10^2 + ...cn*10^n then a(n) = c0 + c1*13 + c2*13^2 + ...cn*13^k.">A094823</span>
|-
| q=14 ||<span title="Numbers whose set of base 14 digits is {0,1}.">A033050</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;
|-
| q=15 ||<span title="Numbers whose set of base 15 digits is {0,1}.">A033051</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;
|-
| q=16 ||<span title="a(1) = 1, a(2n) = 16a(n), a(2n+1) = a(2n)+1.">A033052</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||<span title="Take the decimal representation of n and read it as if it were written in hexadecimal.">A102489</span>
|-
| q=17 ||<span title="a(0)=0, a(1)=1, a(2n)=17*a(n), a(2n+1)=a(2n)+1.">A197351</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;
|-
| q=18 ||<span title="a(0)=0, a(1)=1, a(2n)=18*a(n), a(2n+1)=a(2n)+1.">A197352</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;
|-
| q=19 ||<span title="a(0)=0, a(1)=1, a(2n)=19*a(n), a(2n+1)=a(2n)+1.">A197353</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;
|-
| q=20 ||<span title="Sum of distinct powers of 20; i.e., numbers with digits in {0,1} base 20; i.e., write n in base 2 and read as if written in base 20.">A063012</span>||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||&#xa0;||<span title="Numbers whose base-20 representation can be written with decimal digits.">A102491<sup>1</sup></span>
|-
|}
<sup>1</sup> These sequences have offset 1 and start with n=0.<br>
<sup>2</sup> These sequences have offset 1 and start with n=1.<br>
All other sequences have offset 0 and start with n=0.<br>
===Sums of distinct powers of q===
The first column (b=2) of the table above shows the sequences for ''Sums of distinct powers of q'', since the binary digits in n enumerate all such powers.
===Examples===
A037454: 3[n]6
n =    0  1  2  3  4  5  6  7  8  9  10  11
a(n) = 0, 1, 2, 6, 7, 8, 12, 13, 14, 36, 37, 38, ...
n = 11: 11<sub>10</sub> = 102<sub>3</sub> -&gt; 102<sub>6</sub> = 1*6^2 + 0*6^1 + 2*6^0 = 38<sub>10</sub> = a(11)
===Programs===
* (Mathematica)
b:=3; q:=6; Table[FromDigits[RealDigits[n, b], q], {n, 0, 100}]
* (PARI)
b=3; q=6; for(n=0,100,print1(fromdigits(digits(n, b), q),","));
* Java ([https://github.com/archmageirvine/joeis jOEIS])
java -cp joeis.jar [https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a037/A037454.java irvine.oeis.a037.A037454] 3 6

Latest revision as of 18:10, 6 March 2022

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:

  1. Determine the denomiator polynomials den above, and take their coefficients as the signature for a linear recurrence with constant coefficients.
  2. 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.
  3. 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.

Retrieved from "http://teherba.org/tehowiki/index.php?title=Talk:Main_Page&oldid=412"