

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[n1] + a[n2],
T(n,2) = (a[n]  2 a[n1] + 2 a[n2]  2 a[n3] + a[n4])/2,
T(n,3) = (a[n]  3 a[n1] + 3 a[n2]  4 a[n3] + 3 a[n4]  3 a[n5] + a[n6])/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 pseudoknots: Graph theoretical and combinatorial properties, Bull. Math. Biol. (1999) Vol 61 Issue 3, 43767.


LINKS

Alois P. Heinz, Rows n = 0..200, flattened


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(n1, s minus {n}), expand(b(n1, s)+add(`if`(i in s, 0,
`if`(i=n1, x, 1)*b(n1, s union {i})), i=1..n1))))
end:
T:= n>(p>seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):
seq(T(n), n=0..14); # Alois P. Heinz, Mar 10 2014


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

Column k=0 is A170941. Row sums are A000085.
Sequence in context: A356891 A135281 A068465 * A209771 A209751 A275381
Adjacent sequences: A217873 A217874 A217875 * A217877 A217878 A217879


KEYWORD

nonn,tabf


AUTHOR

David Callan, Oct 14 2012


STATUS

approved



