login
This site is supported by donations 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
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

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(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}]

CROSSREFS

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

Sequence in context: A184243 A135281 A068465 * A209771 A209751 A275381

Adjacent sequences:  A217873 A217874 A217875 * A217877 A217878 A217879

KEYWORD

nonn,tabf

AUTHOR

David Callan, Oct 14 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 11 18:50 EST 2019. Contains 329031 sequences. (Running on oeis4.)