cp's OEIS Frontend

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

%I A098742 #58 Mar 17 2020 13:49:31
%S A098742 0,0,1,1,3,9,33,135,609,2985,15747,88761,531561,3366567,22462017,
%T A098742 157363329,1154257683,8841865833,70573741857,585753925047,
%U A098742 5046128460801,45044554041897,416005748766771,3969321053484921,39077616720410409
%N A098742 Number of indecomposable set partitions of [1..n] without singletons.
%C A098742 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
%D A098742 D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.7, Problem 26.
%D A098742 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!
%H A098742 Alois P. Heinz, <a href="/A098742/b098742.txt">Table of n, a(n) for n = 0..500</a>
%F A098742 If f(z) is the generating function for A074664, then a(z)=zf(z)/(1+z-f(z)).
%F A098742 Also, if g(z) is the generating function for A000296, then a(z) = 1-1/g(z).
%F A098742 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
%F A098742 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:
%F A098742 G.f.: -x + 2*x/E(0) where E(k)= 1 + 1/(1 + 2*x/(1 - 2*(k+2)*x/E(k+1))).
%F A098742 G.f.: 1 - x*U(0,1/x) where U(k,x)= x - k - (k+1)/U(k+1,x).
%F A098742 G.f.: (1+x)*x/G(0) - x where G(k) = 1 + x - x*(k+1)/(1 - x/G(k+1)).
%F A098742 G.f.: x/Q(0) - x where Q(k)= 1 + x/(x*k-x-1)/Q(k+1).
%F A098742 G.f.: 1 - Q(0) where Q(k)= 1 + x - x/(1 - x*(k+1)/Q(k+1)).
%F A098742 G.f.: 1-x-1/Q(0) where Q(k)= 1 + x/(1 - x - x*(k+1)/(x + 1/Q(k+1))). (End)
%e A098742 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.]
%p A098742 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
%t A098742 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 *)
%o A098742 (Sage)
%o A098742 def A098742_list(dim):
%o A098742     T = matrix(ZZ,dim,dim)
%o A098742     for n in range(dim): T[n,n] = 1
%o A098742     for n in (1..dim-1):
%o A098742         for k in (0..n-1):
%o A098742             T[n,k] = T[n-1,k-1]+(k+1)*T[n-1,k]+(k+2)*T[n-1,k+1]
%o A098742     return [0,0]+list(T.column(0))
%o A098742 A098742_list(23) # - _Peter Luschny_, Sep 20 2012
%Y A098742 Cf. A000296, A074664, A001748, A008585.
%K A098742 nice,nonn,easy
%O A098742 0,5
%A A098742 _Don Knuth_, Oct 01 2004
%E A098742 More terms from _Vladeta Jovovic_, Oct 21 2004