A124425 Number of partitions of the set {1,2,...,n} having no blocks with all entries of the same parity.

1, 0, 1, 1, 3, 7, 25, 79, 339, 1351, 6721, 31831, 179643, 979567, 6166105, 37852039, 262308819, 1784037031, 13471274401, 100285059751, 818288740923, 6604485845167, 57836113793305, 502235849694679, 4693153430067699, 43572170967012871, 432360767273547841

Offset: 0

Author

Emeric Deutsch, Nov 01 2006

Keywords

• nonn

Comments

Column 0 of A124424.

Examples

			a(4) = 3 because we have 1234, 14|23 and 12|34.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..400

Crossrefs

Cf. A000110, A124418, A124419, A124420, A124421, A124422, A124423, A124424.

Programs

Maple

Q[0]:=1: for n from 1 to 27 do if n mod 2 = 1 then Q[n]:=expand(t*diff(Q[n-1],t)+x*diff(Q[n-1],s)+x*diff(Q[n-1],x)+t*Q[n-1]) else Q[n]:=expand(x*diff(Q[n-1],t)+s*diff(Q[n-1],s)+x*diff(Q[n-1],x)+s*Q[n-1]) fi od: seq(subs({t=0,s=0,x=1},Q[n]),n=0..27);
# second Maple program:
a:= proc(n) local g, u; g:= floor(n/2); u:= ceil(n/2);
      add(Stirling2(g, k)*Stirling2(u, k)*k!, k=0..g)
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 24 2013

Mathematica

a[n_] := Module[{g=Floor[n/2], u=Ceiling[n/2]}, Sum[StirlingS2[g, k]*StirlingS2[u, k]*k!, {k, 0, g}]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)

Formula

a(n) = Q[n](0,0,1), where the polynomials Q[n]=Q[n](t,s,x) are defined by Q[0]=1; Q[n]=t*dQ[n-1]/dt + x*dQ[n-1]/ds + x*dQ[n-1]/dx + t*Q[n-1] if n is odd and Q[n]=x*dQ[n-1]/dt + s*dQ[n-1]/ds + x*dQ[n-1]/dx + s*Q[n-1] if n is even.

a(n) = Sum_{k=0..floor(n/2)} Stirling2(floor(n/2),k)*Stirling2(ceiling(n/2),k)*k!. - Alois P. Heinz, Oct 24 2013