A217876 Triangle read by rows: distribution of adjacent transpositions in involutions.

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

Offset: 0

Author

David Callan, Oct 14 2012

Keywords

• nonn
• tabf

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.

Examples

			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.
		

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

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

Crossrefs

Column k=0 is A170941. Row sums are A000085.

Programs

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, {})):
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}]