A098742 Number of indecomposable set partitions of [1..n] without singletons.

0, 0, 1, 1, 3, 9, 33, 135, 609, 2985, 15747, 88761, 531561, 3366567, 22462017, 157363329, 1154257683, 8841865833, 70573741857, 585753925047, 5046128460801, 45044554041897, 416005748766771, 3969321053484921, 39077616720410409

Offset

0,5

Comments

After a(3) = 1, always divisible by 3. a(n) is 3 times a prime (A001748) when n = 5, 6, 11, 14, 15, 16, 19. - Jonathan Vos Post, Jun 22 2008

References

D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.7, Problem 26.

George Puttenham, The Arte of English Poesie (1589), page 72, can be said to have stated the problem; but he omitted one case for n=5 and 22 cases for n=6, so he must have had other constraints in mind!

Links

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

Formula

If f(z) is the generating function for A074664, then a(z)=zf(z)/(1+z-f(z)).

Also, if g(z) is the generating function for A000296, then a(z) = 1-1/g(z).

O.g.f.: x^2/(1-x-2*x^2/(1-2*x-3*x^2/(1-3*x-4*x^2/(1-... -n*x-(n+1)*x^2/(1- ...)))))) (continued fraction). - Paul D. Hanna, Jan 17 2006

From Sergei N. Gladkovskii, Sep 20 2012, Nov 04 2012, Feb 04 2013, Feb 23 2013, Apr 18 2013, May 12 2013: (Start) Continued fractions:

G.f.: -x + 2*x/E(0) where E(k)= 1 + 1/(1 + 2*x/(1 - 2*(k+2)*x/E(k+1))).

G.f.: 1 - x*U(0,1/x) where U(k,x)= x - k - (k+1)/U(k+1,x).

G.f.: (1+x)*x/G(0) - x where G(k) = 1 + x - x*(k+1)/(1 - x/G(k+1)).

G.f.: x/Q(0) - x where Q(k)= 1 + x/(x*k-x-1)/Q(k+1).

G.f.: 1 - Q(0) where Q(k)= 1 + x - x/(1 - x*(k+1)/Q(k+1)).

G.f.: 1-x-1/Q(0) where Q(k)= 1 + x/(1 - x - x*(k+1)/(x + 1/Q(k+1))). (End)

Example

a(5)=9 because of the set partitions 135|24, 134|25, 125|34, 145|23, 15|234, 13|245, 124|35, 12345, 14|235. [Puttenham missed the last of these.]

Maple

F:= proc(n) option remember; convert(series(1 -1/add(coeff(series(exp(exp(x)-1), x, n+1), x, j)*j!*x^j, j=0..n), x, n+1), polynom) end: a:= n-> coeff(series(x*F(n)/(1+x-F(n)), x, n+1), x, n): seq(a(n), n=0..24); # Alois P. Heinz, Sep 05 2008

Mathematica

f[n_] := f[n] = Normal[ Series[ 1-1/Sum[ SeriesCoefficient[ Series[ Exp[Exp[x] - 1], {x, 0, n + 1}], {x, 0, j}]*j!*x^j, {j, 0, n}], {x, 0, n + 1}]]; a[0] = 0; a[n_] := SeriesCoefficient[ Series[ x*(f[n]/(1 + x - f[n])), {x, 0, n + 1}], {x, 0, n}]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, translated from Maple *)

Prog

(Sage)
def A098742_list(dim):
    T = matrix(ZZ, dim, dim)
    for n in range(dim): T[n, n] = 1
    for n in (1..dim-1):
        for k in (0..n-1):
            T[n, k] = T[n-1, k-1]+(k+1)*T[n-1, k]+(k+2)*T[n-1, k+1]
    return [0, 0]+list(T.column(0))
A098742_list(23) # - Peter Luschny, Sep 20 2012

Crossrefs

Cf. A000296, A074664, A001748, A008585.

Sequence in context: A217617 A320181 A238113 * A320182 A320183 A320184

Adjacent sequences: A098739 A098740 A098741 * A098743 A098744 A098745

Keyword

nice,nonn,easy

Author

Don Knuth, Oct 01 2004

Extensions

More terms from Vladeta Jovovic, Oct 21 2004

Status

approved