|
Search: id:A098742
|
|
|
| A098742 |
|
Number of indecomposable set partitions of [1..n] without singletons. |
|
+0
3
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
0,5
|
|
|
COMMENT
|
After a(3) = 1, always divisble by 3 (in A008585). a(n) is 3 times a prime (A001748) when n = 5, 6, 11, 14, 15, 16, 19. - Jonathan Vos Post (jvospost3(AT)gmail.com), 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!
|
|
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.: A(x) = 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 (pauldhanna(AT)juno.com), Jan 17 2006
|
|
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.]
|
|
CROSSREFS
|
Cf. A000296, A074664.
Cf. A001748, A008585.
Sequence in context: A049151 A087289 A084508 this_sequence A009212 A001930 A049425
Adjacent sequences: A098739 A098740 A098741 this_sequence A098743 A098744 A098745
|
|
KEYWORD
|
nice,nonn,easy
|
|
AUTHOR
|
D. E. Knuth, Oct 01 2004
|
|
EXTENSIONS
|
More terms from Vladeta Jovovic (vladeta(AT)Eunet.yu), Oct 21 2004
|
|
|
Search completed in 0.002 seconds
|
