1,3

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.

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

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

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

(Other) /* Usage in cygwin: bc pairs.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<i ; j++ ){

s = s*(n-j)/(j+1)

}

return ( s )

}

Cf. A001147, the double factorial

a(n) is 1/(2n-2) times the corresponding term of A053871

Sequence in context: A136633 A082580 A136658 this_sequence A104098 A056755 A123617

Adjacent sequences: A165965 A165966 A165967 this_sequence A165969 A165970 A165971

nonn

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