|
| |
|
|
A217876
|
|
Triangle read by rows: distribution of adjacent transpositions in involutions.
|
|
2
|
|
|
|
1, 1, 1, 1, 2, 2, 5, 4, 1, 13, 10, 3, 37, 29, 9, 1, 112, 88, 28, 4, 363, 288, 96, 16, 1, 1235, 984, 336, 60, 5, 4427, 3555, 1248, 240, 25, 1, 16526, 13334, 4764, 956, 110, 6, 64351, 52252, 19023, 3984, 505, 36, 1, 259471, 211646, 78101, 16836, 2261, 182, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
T(n,k) is the number of involutions on [n] containing exactly k adjacent transpositions. The Mathematica recurrence below is based on considerations and manipulations similar to those in the Stadler and Haslinger reference for the case k=0 (Theorem 5 in Section 3).
It appears that each column is a palindromic linear combination of the entries a[n] := T(n,0) in column 0:
T(n,1) = a[n] - a[n-1] + a[n-2],
T(n,2) = (a[n] - 2 a[n-1] + 2 a[n-2] - 2 a[n-3] + a[n-4])/2,
T(n,3) = (a[n] - 3 a[n-1] + 3 a[n-2] - 4 a[n-3] + 3 a[n-4] - 3 a[n-5] + a[n-6])/6,
T(n,4) = (a[n] - 4 a[n - 1] + 4 a[n - 2] - 4 a[n - 3] + 4 a[n - 4] - 4 a[n - 5] + 4 a[n - 6] - 4 a[n - 7] + a[n - 8])/24,
T(n,5) = (a[n] - 5 a[n - 1] + 5 a[n - 2] + 4 a[n - 5] + 5 a[n - 8] - 5 a[n - 9] + a[n - 10])/120.
It appears that each diagonal is a polynomial function: topmost entries are 1, second entries are k+1, third entries are (k+1)^2, fourth entries are 1/3 (1 + k) (2 + k) (3 + 2 k), fifth entries are 1/12 (1 + k) (2 + k) (30 + 23 k + 5 k^2), sixth entries are 1/60 (1 + k) (2 + k) (3 + k) (130 + 77 k + 13 k^2), seventh entries are 1/180 (1 + k) (2 + k) (3 + k) (1110 + 821 k + 210 k^2 + 19 k^3).
Conjecture: The asymptotic distribution of adjacent transpositions in involutions is Poisson with mean 1.
|
|
|
REFERENCES
|
P. Stadler and C. Haslinger, RNA structures with pseudo-knots: Graph theoretical and combinatorial properties, Bull. Math. Biol. (1999) Vol 61 Issue 3, 437-67.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Triangle starts at n=0, k=0:
..1
..1
..1 ...1
..2 ...2
..5 ...4 ...1
.13 ..10 ...3
.37 ..29 ...9 ...1
112 ..88 ..28 ...4
363 .288 ..96 ..16 ...1
T(5,2) = 3 counts, in cycle form, {(12),(34),(5)}, {(12),(3),(45)}, and {(1),(23),(45)} because each contains 2 adjacent transpositions.
|
|
|
MAPLE
|
b:= proc(n, s) option remember; `if`(n=0, 1, `if`(n in s,
b(n-1, s minus {n}), expand(b(n-1, s)+add(`if`(i in s, 0,
`if`(i=n-1, x, 1)*b(n-1, s union {i})), i=1..n-1))))
end:
T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):
|
|
|
MATHEMATICA
|
Clear[T]; (* T(n, k, j) is the number of involutions on [n] containing k adjacent transpositions but not the adjacent transposition (j, j+1) *)
T[n_, k_] /; k < 0 || k > n/2 := 0;
T[0, 0] = 1; T[1, 0] = 1; T[2, 0] = 1;
T[n_, k_] := T[n, k] = T[n - 1, k] + T[n - 2, k - 1] - T[n - 3, k] - T[n - 4, k - 1] + T[n - 4, k] + Sum[T[n - 2, k, j], {j, 0, n - 2}];
T[n_, k_, j_] /; n <= 1 && k >= 1 := 0;
T[n_, k_, j_] /; k < 0 := 0;
T[n_, k_, j_] /; 0 <= n <= 1 && k == 0 := 1;
T[n_, k_, j_] /; j <= 0 || j >= n := T[n, k];
T[n_, k_, j_] /; n >= 2 && k >= 0 := T[n, k, j] = T[n - 2, k, j - 1] + T[n, k] - T[n - 2, k] - T[n - 2, k - 1, j - 1];
Table[T[n, k], {n, 0, 15}, {k, 0, n/2}]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
