A256033 Number of idempotents of rank 1 in partition monoid P_n.

1, 5, 43, 529, 8451, 167397, 3984807, 111319257, 3583777723, 131082199809, 5385265586075, 246172834737485, 12422776100542887, 687441750763500441, 41475644663003037947, 2714680813135603845921

Offset: 1

Author

N. J. A. Sloane, Mar 14 2015

Keywords

• nonn

Links

• I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, et al., Enumeration of idempotents in diagram semigroups and algebras, arXiv preprint arXiv:1408.2021 [math.GR], 2014. See Table 3.

Crossrefs

Cf. A060639, A256034.

Programs

Maple

e256033 := proc(n,r,s)
    option remember;
    local resu,m,a,b;
    if n <= 0 then
        return 0;
    end if;
    if s = 1 then
        combinat[stirling2](n,r) ;
    elif r= 1 then
        combinat[stirling2](n,s) ;
    else
        resu := s*procname(n-1,r-1,s)+r*procname(n-1,r,s-1)+r*s*procname(n-1,r,s) ;
        for m from 1 to n-2 do
        for a from 1 to r-1 do
        for b from 1 to s-1 do
            resu := resu + binomial(n-2,m) *(a*(s-b)+b*(r-a))
                *procname(m,a,b)*procname(n-m-1,r-a,s-b);
        end do:
        end do:
        end do:
        resu ;
    end if;
end proc:
A256033 := proc(n)
    a := 0 ;
    for r from 1 to n do
    for s from 1 to n do
        a  := a+r*s*e256033(n,r,s) ;
    end do;
    end do;
end proc:
seq(A256033(n),n=1..16) ; # R. J. Mathar, Mar 23 2015

Mathematica

f[n_, r_, s_] := f[n, r, s] = Module[{resu, m, a, b}, Which[n <= 0, 0, s == 1, StirlingS2[n, r], r == 1, StirlingS2[n, s], True, resu = s*f[n - 1, r - 1, s] + r*f[n - 1, r, s - 1] + r*s*f[n - 1, r, s]; Do[resu += Binomial[n - 2, m]*(b*(r - a) + a*(s - b))*f[m, a, b]*f[-m + n - 1, r - a, s - b], {m, n}, {a, r - 1}, {b, s - 1}]; resu]];
a[n_] := Module[{b = 0}, Do[b += r*s*f[n, r, s], {r, n}, {s, n}]; b];
Array[a, 16] (* Jean-François Alcover, Nov 23 2017, after R. J. Mathar *)

Sage

@cached_function
def F(n, r, s):
    if n <= 0: return 0
    if s == 1: return stirling_number2(n, r)
    if r == 1: return stirling_number2(n, s)
    ret = s*F(n-1,r-1,s)+r*F(n-1,r,s-1)+r*s*F(n-1,r,s)
    for m in (1..n-2):
        for a in (1..r-1):
            for b in (1..s-1):
                ret += binomial(n-2,m)*(a*(s-b)+b*(r-a))*F(m,a,b)*F(n-m-1,r-a,s-b)
    return ret
@cached_function
def A256033(n):
    a = 0
    for r in (1..n):
        for s in (1..n):
            a += r*s*F(n, r, s)
    return a
[A256033(n) for n in (1..9)] # Peter Luschny, Jan 17 2016