A052848 Number of ordered set partitions with a designated element in each block and no block containing less than two elements.

1, 0, 2, 3, 28, 125, 1146, 8827, 94200, 1007001, 12814390, 172114151, 2584755636, 41436880069, 721702509906, 13397081295795, 266105607506416, 5605474012933169, 125164378600050798, 2948082261121889983, 73122068527848758700, 1903894649651935410141

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• nonn
• easy

Comments

a(n) is the number of functional digraphs on {1,2,...,n} such that no node is at a distance greater than one from a cycle (A006153) and every recurrent element has at least one nonrecurrent element mapped to it. - Geoffrey Critzer, Dec 07 2012

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..434
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 816

Crossrefs

Cf. A000296.

Programs

Maple

spec := [S,{B=Prod(Z,C),C=Set(Z,1 <= card),S=Sequence(B)},labeled]: seq(combstruct[count](spec, size=n), n=0..20);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1,
      add(a(n-j)*binomial(n, j)*j, j=2..n))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, May 11 2016

Mathematica

nn=20; a=x Exp[x]; First[Range[0,nn]! CoefficientList[Series[1/(1-x (Exp[x]-1+y)), {x,0,nn}], {y,x}]] Range[0,nn]! (* Geoffrey Critzer, Dec 07 2012 *)

Maxima

a(n):=n!*sum((k!*stirling2(n-k,k))/(n-k)!,k,0,n/2); /* Vladimir Kruchinin, Nov 16 2011 */

Formula

E.g.f.: -1/(-1+x*exp(x)-x).

a(n) = n!*Sum_{k=0..floor(n/2)} k!*Stirling2(n-k,k)/(n-k)!. - Vladimir Kruchinin, Nov 16 2011

a(n) ~ n!/(1+r+r^2) * r^(n+2), where r = 1.23997788765655... is the root of the equation log(1+r)=1/r. - Vaclav Kotesovec, Oct 05 2013

a(0) = 1; a(n) = n * Sum_{k=2..n} binomial(n-1,k-1) * a(n-k). - Seiichi Manyama, Dec 04 2023

Extensions

Better name from Geoffrey Critzer, Dec 10 2012