A194924 The number of set partitions of {1,2,...,n} into exactly two subsets A,B such that the greatest common divisor of |A| and |B| = 1.

1, 3, 4, 15, 6, 63, 64, 171, 130, 1023, 804, 4095, 2380, 7920, 16384, 65535, 40410, 262143, 246640, 582771, 695860, 4194303, 2884776, 13455325, 11576916, 44739243, 65924824, 268435455, 176422980, 1073741823, 1073741824, 2669774811, 3128164186, 11421338075

Offset

2,2

Comments

a(p)=2^(p-1)-1 = S2(p,2) where p is a prime and S2(n,k) is the Stirling number of the second kind.

a(n) is the coefficient of x^n/n! in the Taylor series expansion of B(A(x)) where A(x)= Sum_{over positive integers relatively prime to n}x^n/n! and B(x)=x^2/2!.

Links

Alois P. Heinz, Table of n, a(n) for n = 2..1000

Maple

a:= n-> `if`(n=2, 1, add(`if`(igcd(k, n-k)=1,
                     binomial(n, k), 0), k=1..iquo(n, 2))):
seq(a(n), n=2..50); # Alois P. Heinz, Nov 02 2011

Mathematica

f[list_]:=x^First[list]/First[list]!+x^Last[list]/Last[list]!;
Prepend[Table[a=Total[Map[f, Select[IntegerPartitions[n, 2], Apply[GCD, #]==1&]]]; Last[Range[0, n]! CoefficientList[Series[a^2/2!, {x, 0, n}], x]], {n, 3, 30}], 1]
(* Second program: *)
a[n_] := If[n == 2, 1, Sum[If[GCD[k, n-k] == 1, Binomial[n, k], 0], {k, 1, Quotient[n, 2]}]];
a /@ Range[2, 50] (* Jean-François Alcover, Jun 09 2021, after Alois P. Heinz *)

Crossrefs

Column k=2 of A280880.

Sequence in context: A343939 A157351 A071167 * A205489 A343935 A280685

Adjacent sequences: A194921 A194922 A194923 * A194925 A194926 A194927

Keyword

nonn

Author

Geoffrey Critzer, Oct 12 2011

Status

approved