login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A217876 Triangle read by rows: distribution of adjacent transpositions in involutions. 2

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 31 04:27 EST 2023. Contains 359947 sequences. (Running on oeis4.)