A165968 Number of pairings disjoint to a given pairing, and containing a given pair not in the given pairing.

0, 1, 2, 10, 68, 604, 6584, 85048, 1269680, 21505552, 407414816, 8535396256, 195927013952, 4890027052480, 131842951699328, 3818743350945664, 118253903175951104, 3898687202158805248, 136339489775029813760, 5040776996774472673792

Offset: 1

Author

Lewis Mammel (l_mammel(AT)att.net), Oct 02 2009

Keywords

• nonn

Comments

The formula is derived by an application of the principle of inclusion and exclusion.

In reference to A053871, it is observed that the set of pairings disjoint to a given pairing can be partitioned into 2n-2 equivalent sets according to the 2n-2 pairs containing a given item. So it is seen that each term of that sequence must be divisible by 2n-2, giving the corresponding term of this sequence. However, the formula given here is derived independently.

Hankel transform of a(n+1) is A168467. Binomial transform of a(n+1) is A001147(n+1). - Paul Barry, Jan 26 2011

a(n) is a subset of the set of pairings of the first 2n integers (A001147) in another way: forbidding pairs of the form (2k,2k+1) for all k. - Olivier Gérard, Feb 08 2011

Examples

			a(1) = 0 trivially.
a(2) = 1 since there is a unique pairing disjoint to the canonical pairing, 01 23, and containing any of the 4 pairs not in the canonical pairing.
a(3) = 2 since there are 2 pairings disjoint to the canonical pairing, 01 23 45, and containing the pair 02, not in the canonical pairing: 02 14 35 and 02 15 34.
		

References

• John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, Chapter 3

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..405
• Jean-Luc Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016).
• Marilena Barnabei, Niccolò Castronuovo, and Matteo Silimbani, Hertzsprung patterns on involutions, arXiv:2412.03449 [math.CO], 2024. See p. 10.
• Célia Biane, Greg Hampikian, Sergey Kirgizov, and Khaydar Nurligareev, Endhered patterns in matchings and RNA, arXiv:2404.18802 [math.CO], 2024. See pp. 8-9.

Crossrefs

Cf. A001147, the double factorial.

Cf. also A053871.

Cf. A168467.

Programs

Maple

a:= n-> add((-1)^(n-k-1)*binomial(n-1,k)*(2*(k+1))!/(2^(k+1)*(k+1)!), k=0..n-1):
seq(a(n), n=0..20);

Mathematica

a[n_] := Sum[(-1)^(n-k-2)* Binomial[n-2, k]*(2*(k+1))!/(2^(k+1)*(k+1)!) , {k, 0, n-2}]; a /@ Range[20]
(* Jean-François Alcover, Jul 11 2011, after Maple *)
CoefficientList[Series[-1+1/(E^x*Sqrt[1-2*x]) + Sqrt[2]*DawsonF[1/Sqrt[2]] + Sqrt[-Pi/(2*E)]*Erf[Sqrt[-1/2+x]],{x,0,20}],x]*Range[0,20]! (* Vaclav Kotesovec, Feb 04 2014 *)

bc

define a(n)
{
    auto sign, i,s;
    s=0; sign = 1;
    for ( i=0 ; i<=n-1 ; i++ ) {
        s = s + sign * ffac(n-1-i) * c( n-2, i );
        sign = sign * -1;
    }
    return s;
}
/* returns (2n-1)!! */
define ffac( n )
{
    if ( n <= 1 ) return 1;
    return  (2*n-1)* ffac(n-1);
}
/* returns combinations of n things taken i at a time */
define c(n,i)
{
    auto j,s;
    s=1;
    if ( n < 0 ) return 0;
    for ( j=0 ; j
				

Formula

a(n) = (2n-3)!! - C(n-2,1) * (2n-5)!! + ... +/- C(n-2,n-1)*3!! -/+ 1.

a(n) = (2*n-4)*a(n-1) +(2*n-6)*a(n-2) for n>2. - Gary Detlefs, Jul 11 2010

G.f.: x/(1-2x/(1-3x/(1+x-4x/(1-5x/(1+x-6x/(1-7x/(1+x-8x/(1-... (continued fraction). - Paul Barry, Jan 26 2011

a(n) = Sum_{k=0..n-1} (-1)^(n-k-1)*C(n-1,k)*(2*(k+1))!/(2^(k+1)*(k+1)!). - Paul Barry, Jan 26 2011

Conjecture: a(n) +2*(-n+1)*a(n-1) +2*(-n+2)*a(n-2)=0. - R. J. Mathar, Nov 15 2012

G.f.: x/G(0) where G(k) = 1 - 2*x*(2*k+1) - x^2*(2*k+2)*(2*k+3)/G(k+1) (continued fraction). - Sergei N. Gladkovskii, Jan 13 2013

G.f.: Q(0)-1, where Q(k) = 1 - x*(k+1)/( x*(k+1) - (1 +x)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 21 2013

a(n) ~ 2^(n-1/2) * n^(n-1) / exp(n+1/2). - Vaclav Kotesovec, Feb 04 2014

a(n) = A053871(n)/(2n-2) for n>1.

a(n) * (2n-2) satisfies the recurrence of A053871, so Detlef's conjecture was correct. And if we rewrite Mathar's conjecture as b(n) = 2*(n-1)*b(n-1) +2*(n-2)*b(n-2) it becomes quite clear that Mathar's b(n) = a(n-1). - Sergey Kirgizov, Jun 03 2022