|
| |
|
|
A172236
|
|
Array T(n,k) = n*T(n,k-1) + T(n,k-2) read by upward antidiagonals, starting T(n,0) = 0, T(n,1) = 1.
|
|
50
|
|
|
|
0, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 5, 3, 0, 1, 4, 10, 12, 5, 0, 1, 5, 17, 33, 29, 8, 0, 1, 6, 26, 72, 109, 70, 13, 0, 1, 7, 37, 135, 305, 360, 169, 21, 0, 1, 8, 50, 228, 701, 1292, 1189, 408, 34, 0, 1, 9, 65, 357, 1405, 3640, 5473, 3927, 985, 55, 0, 1, 10, 82, 528, 2549, 8658, 18901, 23184, 12970, 2378, 89, 0, 1, 11, 101, 747, 4289, 18200, 53353, 98145, 98209, 42837, 5741, 144
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,9
|
|
|
COMMENTS
|
Equals A073133 with an additional column T(.,0).
If the first column and top row are deleted, antidiagonal reading yields A118243.
Adding a top row of 1's and antidiagonal reading downwards yields A157103.
Antidiagonal sums are 0, 1, 2, 5, 12, 32, 93, 297, 1035, 3911, 15917, 69350, ....
All rows have strong divisibility, that is, gcd(T(n,k_1),T(n,k_2)) = T(n,gcd(k_1,k_2)) holds for all k_1, k_2 >= 0.
Let E(n,m) be the smallest number l such that m divides T(n,l), we have: for odd primes p that are not divisible by n^2 + 4, E(n,p) divides p - ((n^2+4)/p) if p == 3 (mod 4) and (p - ((n^2+4)/p))/2 if p == 1 (mod 4). E(n,p) = p for odd primes p that are divisible by n^2 + 4. E(n,2) = 2 for even n and 3 for odd n. Here ((n^2+4)/p) is the Legendre symbol. A prime p such that p^2 divides T(n,E(n,p)) is called an n-Wall-Sun-Sun prime.
E(n,p^e) <= p^(e-1)*E(n,p) for all primes p. If p^2 does not divide T(n,E(n,p)), then E(n,p^e) = p^(e-1)*E(n,p) for all exponent e. Specially, for primes p >= 5 that are divisible by n^2 + 4, p^2 is never divisible by T(n,p), so E(n,p^e) = p^e as described above. E(n,m_1*m_2) = lcm(E(n,m_1),E(n,m_2)) if gcd(m_1,m_2) = 1.
Let pi(n,m) be the Pisano period of T(n,k) modulo m, i.e, the smallest number l such that T(n,k+1) == T(n,k) (mod m) holds for all k >= 0, we have: for odd primes p that are not divisible by n^2 - 4, pi(n,p) divides p - 1 if ((n^2+4)/p) = 1 and 2(p+1) if ((n^2+4)/p) = -1. pi(n,p) = 4p for odd primes p that are divisible by n^2 + 4. pi(n,2) = 2 even n and 3 for odd n.
pi(n,p^e) <= p^(e-1)*pi(n,p) for all primes p. If p^2 does not divide T(n,E(n,p)), then pi(n,p^e) = p^(e-1)*pi(n,p) for all exponent e. Specially, for primes p >= 5 that are divisible by n^2 + 4, p^2 is never divisible by T(n,p), so pi(n,p^e) = 4p^e as described above. pi(n,m_1*m_2) = lcm(pi(n,m_1),pi(n,m_2)) if gcd(m_1,m_2) = 1.
If n != 2, the largest possible value of pi(n,m)/m is 4 for even n and 6 for odd n. For even n, pi(n,p^e) = 4p^e; for odd n, pi(n,2p^e) = 12p^e, where p is any odd prime factor of n^2 + 4. For n = 2 it is 8/3, obtained by m = 3^e.
Let z(n,m) be the number of zeros in a period of T(n,k) modulo m, i.e., z(n,m) = pi(n,m)/E(n,m), then we have: z(n,p) = 4 for odd primes p that are divisible by n^2 + 4. For other odd primes p, z(n,p) = 4 if E(n,p) is odd; 1 if E(n,p) is even but not divisible by 4; 2 if E(n,p) is divisible by 4; see the table below. z(n,2) = z(n,4) = 1.
Among all values of z(n,p) when p runs through all odd primes that are not divisible by n^2 + 4, we have:
((n^2+4)/p)...p mod 8....proportion of 1.....proportion of 2.....proportion of 4
......1..........1......1/6 (conjectured)...2/3 (conjectured)...1/6 (conjectured)*
......1..........5......1/2 (conjectured)...........0...........1/2 (conjectured)*
......1.........3,7.............1...................0...................0
.....-1.........1,5.............0...................0...................1
.....-1.........3,7.............0...................1...................0
* The result is that among all odd primes that are not divisible by n^2 + 4, 7/24 of them are with z(n,p) = 1, 5/12 are with z(n,p) = 2 and 7/24 are with z(n,p) = 4 if n^2 + 4 is a twice a square; 1/3 of them are with z(n,p) = 1, 1/3 are with z(n,p) = 2 and 1/3 are with z(n,p) = 4 otherwise. [Corrected by Jianing Song, Jul 06 2019]
z(n,p^e) = z(n,p) for all odd primes p; z(n,2^e) = 1 for even n and 2 for odd n, e >= 3.
(End)
Removing the first (n=0) row of A352361 gives this sequence.
Row n is the n-metallonacci sequence.
T(n,k) is (for k>0) the number of tilings of a (k-1)-board (a board with dimensions (k-1) X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are n kinds of squares available. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = (((n + sqrt(n^2 + 4))/2)^k - ((n-sqrt(n^2 + 4))/2)^k)/sqrt(n^2 + 4), n >= 1, k >= 0. - Jianing Song, Jun 27 2018
For n >= 1, Sum_{i=1..k} 1/T(n,2^i) = ((u^(2^k-1) + v^(2^k-1))/(u + v)) * (1/T(n,2^k)), where u = (n + sqrt(n^2 + 4))/2, v = (n - sqrt(n^2 + 4))/2 are the two roots of the polynomial x^2 - n*x - 1. As a result, Sum_{i>=1} 1/T(n,2^i) = (n^2 + 4 - n*sqrt(n^2 + 4))/(2*n). - Jianing Song, Apr 21 2019
|
|
|
EXAMPLE
|
The array starts in row n = 1 with columns k >= 0 as
0 1 1 2 3 5 8
0 1 2 5 12 29 70
0 1 3 10 33 109 360
0 1 4 17 72 305 1292
0 1 5 26 135 701 3640
0 1 6 37 228 1405 8658
0 1 7 50 357 2549 18200
0 1 8 65 528 4289 34840
0 1 9 82 747 6805 61992
0 1 10 101 1020 10301 104030
0 1 11 122 1353 15005 166408
|
|
|
MATHEMATICA
|
f[0, a_] := 0; f[1, a_] := 1;
f[n_, a_] := f[n, a] = a*f[n - 1, a] + f[n - 2, a];
m1 = Table[f[n, a], {n, 0, 10}, {a, 1, 11}];
Table[Table[m1[[m, n - m + 1]], {m, 1, n}], {n, 1, 10}];
Flatten[%]
|
|
|
PROG
|
(PARI) T(n, k) = if (k==0, 0, if (k==1, 1, n*T(n, k-1) + T(n, k-2)));
(PARI) T(n, k) = ([n, 1; 1, 0]^k)[2, 1] \\ Jianing Song, Nov 10 2018
|
|
|
CROSSREFS
|
Cf. A000045 (first row), A000129 (2nd row), A006190 (3rd row), A001076 (4th row), A052918 (5th row), A005668 (6th row), A054413 (7th row), A041025 (8th row), A099371 (9th row), A041041 (10th row), A049666 (11th row), A041061 (12th row), A140455 (13th row), A041085 (14th row), A154597 (15th row), A041113 (16th row), A178765 (17th row), A041145 (18th row), A243399 (19th row), A041181 (20th row). (Note that there are offset shifts for rows n = 5, 7, 8, 10, 12, 14, 16..20.)
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
