|
%I #13 Mar 11 2014 09:10:59
%S 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,
%T 984,336,60,5,4427,3555,1248,240,25,1,16526,13334,4764,956,110,6,
%U 64351,52252,19023,3984,505,36,1,259471,211646,78101,16836,2261,182,7
%N Triangle read by rows: distribution of adjacent transpositions in involutions.
%C 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).
%C It appears that each column is a palindromic linear combination of the entries a[n] := T(n,0) in column 0:
%C T(n,1) = a[n] - a[n-1] + a[n-2],
%C T(n,2) = (a[n] - 2 a[n-1] + 2 a[n-2] - 2 a[n-3] + a[n-4])/2,
%C 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,
%C 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,
%C 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.
%C 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).
%C Conjecture: The asymptotic distribution of adjacent transpositions in involutions is Poisson with mean 1.
%D 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.
%H Alois P. Heinz, <a href="/A217876/b217876.txt">Rows n = 0..200, flattened</a>
%e Triangle starts at n=0, k=0:
%e ..1
%e ..1
%e ..1 ...1
%e ..2 ...2
%e ..5 ...4 ...1
%e .13 ..10 ...3
%e .37 ..29 ...9 ...1
%e 112 ..88 ..28 ...4
%e 363 .288 ..96 ..16 ...1
%e T(5,2) = 3 counts, in cycle form, {(12),(34),(5)}, {(12),(3),(45)}, and {(1),(23),(45)} because each contains 2 adjacent transpositions.
%p b:= proc(n, s) option remember; `if`(n=0, 1, `if`(n in s,
%p b(n-1, s minus {n}), expand(b(n-1, s)+add(`if`(i in s, 0,
%p `if`(i=n-1, x, 1)*b(n-1, s union {i})), i=1..n-1))))
%p end:
%p T:= n->(p->seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):
%p seq(T(n), n=0..14); # _Alois P. Heinz_, Mar 10 2014
%t 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 T[n_, k_] /; k < 0 || k > n/2 := 0;
%t T[0, 0] = 1; T[1, 0] = 1; T[2, 0] = 1;
%t 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 T[n_, k_, j_] /; n <= 1 && k >= 1 := 0;
%t T[n_, k_, j_] /; k < 0 := 0;
%t T[n_, k_, j_] /; 0 <= n <= 1 && k == 0 := 1;
%t T[n_, k_, j_] /; j <= 0 || j >= n := T[n, k];
%t 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];
%t Table[T[n, k], {n, 0, 15}, {k, 0, n/2}]
%Y Column k=0 is A170941. Row sums are A000085.
%K nonn,tabf
%O 0,5
%A _David Callan_, Oct 14 2012
|
