A259454 Triangle T(n,k) (0 <= k <= n) read by rows, arising from the study of rook polynomials.
1, 1, 3, 1, 6, 7, 1, 9, 22, 14, 1, 12, 46, 64, 26, 1, 15, 79, 177, 162, 46, 1, 18, 121, 380, 571, 374, 79, 1, 21, 172, 700, 1496, 1632, 809, 133, 1, 24, 232, 1164, 3261, 5116, 4270, 1668, 221, 1, 27, 301, 1799, 6271, 13013, 15754, 10446, 3316, 364
Offset: 0
Examples
Triangle T(n,k) begins: 1; 1, 3; 1, 6, 7; 1, 9, 22, 14; 1, 12, 46, 64, 26; 1, 15, 79, 177, 162, 46; 1, 18, 121, 380, 571, 374, 79; 1, 21, 172, 700, 1496, 1632, 809, 133; 1, 24, 232, 1164, 3261, 5116, 4270, 1668, 221; G.f. = 1 + (1 + 3*t)*u + (1 + 6*t + 7*t^2)*u^2 + ...
Links
- Alois P. Heinz, Rows n = 0..140, flattened
- J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy] (See triangle on page 18)
Programs
-
Maple
T:= proc(n, k) option remember; `if`(k<0 or k>n, 0, T(n-1, k) +2*T(n-1, k-1) +T(n-2, k-1) -T(n-3, k-3) +`if`(n=k, 1, 0)) end: seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Jul 02 2015 -
Mathematica
T[n_, k_] /; 0 <= k <= n := T[n, k] = T[n-1, k] + 2*T[n-1, k-1] + T[n-2, k - 1] - T[n-3, k-3] + Boole[n == k]; T[, ] = 0; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 18 2016 *)
-
PARI
{T(n, k) = polcoeff( polcoeff( 1 / ((1 - y*x) * (1 - (1 + 2*y)*x - y*x^2 + y^3*x^3)) + x * O(x^n), n), k)}; /* Michael Somos, Aug 26 2015 */
Formula
From Eq. (11) of Riordan (1954): T(n,k) = T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-3,k-3) + delta(n,k), where delta(n,k)=1 iff n=k, otherwise 0.
Sum_{n, k} T(n, k) * x^n*y^k = 1 / ((1 - y*x) * (1 - (1 + 2*y)*x - y*x^2 + y^3*x^3)). - Michael Somos, Aug 26 2015
Extensions
More terms from Alois P. Heinz, Jul 02 2015
Comments