CINXE.COM
A007837 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A007837 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A007837" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA007837">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A007837 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A007837 </div> <div class=seqname> Number of partitions of n-set with distinct block sizes. </div> </div> <div class=scorerefs> 102 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, 1, 1, 4, 5, 16, 82, 169, 541, 2272, 17966, 44419, 201830, 802751, 4897453, 52275409, 166257661, 840363296, 4321172134, 24358246735, 183351656650, 2762567051857, 10112898715063, 62269802986835, 343651382271526, 2352104168848091, 15649414071734847</div> <div class=seqdatalinks> (<a href="/A007837/list">list</a>; <a href="/A007837/graph">graph</a>; <a href="/search?q=A007837+-id:A007837">refs</a>; <a href="/A007837/listen">listen</a>; <a href="/history?seq=A007837">history</a>; <a href="/search?q=id:A007837&fmt=text">text</a>; <a href="/A007837/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,4</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline> Conjecture: the Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for all primes p and positive integers n and k. Cf. <a href="/A185895" title="Exponential generating function is (1-x^1/1!)(1-x^2/2!)(1-x^3/3!)....">A185895</a>. - <a href="/wiki/User:Peter_Bala">Peter Bala</a>, Mar 17 2022</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>Alois P. Heinz, <a href="/A007837/b007837.txt">Table of n, a(n) for n = 0..700</a></div> <div class=sectline>Philippe Flajolet, 脡ric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, <a href="http://arxiv.org/abs/math/0606370">A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics</a>, Fig. 3, arXiv:math/0606370 [math.CO], 2006.</div> <div class=sectline>Knopfmacher, A., Odlyzko, A. M., Pittel, B., Richmond, L. B., Stark, D., Szekeres, G. and Wormald, N. C., <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v6i1r2">The asymptotic number of set partitions with unequal block sizes</a>, Electron. J. Combin., 6 (1999), no. 1, Research Paper 2, 36 pp.</div> <div class=sectline>Gus Wiseman, <a href="/A038041/a038041.txt">Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.</a></div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>E.g.f.: Product_{m >= 1} (1+x^m/m!).</div> <div class=sectline>a(n) = Sum_{k=1..n} (n-1)!/(n-k)!*b(k)*a(n-k), where b(k) = Sum_{d divides k} (-d)*(-d!)^(-k/d) and a(0) = 1. - <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a>, Oct 13 2002</div> <div class=sectline>E.g.f.: exp(Sum_{k>=1} Sum_{j>=1} (-1)^(k+1)*x^(j*k)/(k*(j!)^k)). - <a href="/wiki/User:Ilya_Gutkovskiy">Ilya Gutkovskiy</a>, Jun 18 2018</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>From <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Jul 13 2019: (Start)</div> <div class=sectline>The a(1) = 1 through a(5) = 16 set partitions with distinct block sizes:</div> <div class=sectline> {{1}} {{1,2}} {{1,2,3}} {{1,2,3,4}} {{1,2,3,4,5}}</div> <div class=sectline> {{1},{2,3}} {{1},{2,3,4}} {{1},{2,3,4,5}}</div> <div class=sectline> {{1,2},{3}} {{1,2,3},{4}} {{1,2},{3,4,5}}</div> <div class=sectline> {{1,3},{2}} {{1,2,4},{3}} {{1,2,3},{4,5}}</div> <div class=sectline> {{1,3,4},{2}} {{1,2,3,4},{5}}</div> <div class=sectline> {{1,2,3,5},{4}}</div> <div class=sectline> {{1,2,4},{3,5}}</div> <div class=sectline> {{1,2,4,5},{3}}</div> <div class=sectline> {{1,2,5},{3,4}}</div> <div class=sectline> {{1,3},{2,4,5}}</div> <div class=sectline> {{1,3,4},{2,5}}</div> <div class=sectline> {{1,3,4,5},{2}}</div> <div class=sectline> {{1,3,5},{2,4}}</div> <div class=sectline> {{1,4},{2,3,5}}</div> <div class=sectline> {{1,4,5},{2,3}}</div> <div class=sectline> {{1,5},{2,3,4}}</div> <div class=sectline>(End)</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline>a:= proc(n) option remember; `if`(n=0, 1, add(add((-d)*(-d!)^(-k/d),</div> <div class=sectline> d=numtheory[divisors](k))*(n-1)!/(n-k)!*a(n-k), k=1..n))</div> <div class=sectline> end:</div> <div class=sectline>seq(a(n), n=0..30); # <a href="/wiki/User:Alois_P._Heinz">Alois P. Heinz</a>, Sep 06 2008</div> <div class=sectline># second Maple program:</div> <div class=sectline><a href="/A007837" title="Number of partitions of n-set with distinct block sizes.">A007837</a> := proc(n) option remember; local k; `if`(n = 0, 1,</div> <div class=sectline>add(binomial(n-1, k-1) * <a href="/A182927" title="Row sums of A182928.">A182927</a>(k) * <a href="/A007837" title="Number of partitions of n-set with distinct block sizes.">A007837</a>(n-k), k = 1..n)) end:</div> <div class=sectline>seq(<a href="/A007837" title="Number of partitions of n-set with distinct block sizes.">A007837</a>(i), i=0..24); # <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Apr 25 2011</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>nn=20; p=Product[1+x^i/i!, {i, 1, nn}]; Drop[Range[0, nn]!CoefficientList[ Series[p, {x, 0, nn}], x], 1] (* <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Sep 22 2012 *)</div> <div class=sectline>a[0]=1; a[n_] := a[n] = Sum[(n-1)!/(n-k)!*DivisorSum[k, -#*(-#!)^(-k/#)&]* a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 30}] (* <a href="/wiki/User:Jean-Fran莽ois_Alcover">Jean-Fran莽ois Alcover</a>, Nov 23 2015, after <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a> *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(PARI) {my(n=20); Vec(serlaplace(prod(k=1, n, (1+x^k/k!) + O(x*x^n))))} \\ <a href="/wiki/User:Andrew_Howroyd">Andrew Howroyd</a>, Dec 21 2017</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Row sums of <a href="/A131632" title="Triangle T(n,k) read by rows = number of partitions of n-set into k blocks with distinct sizes, k = 1..A003056(n).">A131632</a> or <a href="/A262072" title="Number T(n,k) of partitions of an n-set with distinct block sizes and maximal block size equal to k; triangle T(n,k), n>=0, ...">A262072</a> or <a href="/A262078" title="Number T(n,k) of partitions of an n-set with distinct block sizes and maximal block size equal to k; triangle T(n,k), k>=0, ...">A262078</a> or <a href="/A309992" title="Triangle T(n,k) whose n-th row lists in increasing order the multinomial coefficients M(n;lambda), where lambda ranges over ...">A309992</a>.</div> <div class=sectline>Cf. <a href="/A000110" title="Bell or exponential numbers: number of ways to partition a set of n labeled elements.">A000110</a>, <a href="/A005651" title="Sum of multinomial coefficients (n_1+n_2+...)!/(n_1!*n_2!*...) where (n_1, n_2, ...) runs over all integer partitions of n.">A005651</a>, <a href="/A007838" title="Number of permutations of n elements with distinct cycle lengths.">A007838</a>, <a href="/A032011" title="Partition n labeled elements into sets of different sizes and order the sets.">A032011</a>, <a href="/A035470" title="Number of ways to break {1,2,3,...,n} into sets with equal sums.">A035470</a>, <a href="/A038041" title="Number of ways to partition an n-set into subsets of equal size.">A038041</a>, <a href="/A178682" title="The number of functions f:{1,2,...,n}->{1,2,...,n} such that the number of elements that are mapped to m is divisible by m.">A178682</a>, <a href="/A265950" title="Expansion of Product_{k>=1} (1 + k!*x^k).">A265950</a>, <a href="/A271423" title="Number T(n,k) of set partitions of [n] with maximal block length multiplicity equal to k; triangle T(n,k), n>=0, 0<=k<=n, re...">A271423</a>, <a href="/A275780" title="Number of set partitions of [n] into blocks with distinct element sums.">A275780</a>, <a href="/A326026" title="Number of non-isomorphic multiset partitions of weight n where each part has a different length.">A326026</a>, <a href="/A326514" title="Number of factorizations of n into factors > 1 where each factor has a different number of prime factors counted with multip...">A326514</a>, <a href="/A326517" title="Number of normal multiset partitions of weight n where each part has a different size.">A326517</a>, <a href="/A326533" title="MM-numbers of multiset partitions where each part has a different length.">A326533</a>.</div> <div class=sectline>Column k=0 of <a href="/A327869" title="Sum T(n,k) of multinomials M(n; lambda), where lambda ranges over all partitions of n into distinct parts incorporating k; t...">A327869</a>.</div> <div class=sectline>Sequence in context: <a href="/A110278" title="Values of n such that the perfect deficiency (A109883) of n and n+1 are both squares.">A110278</a> <a href="/A013628" title="Triangle of coefficients in expansion of (4+5x)^n.">A013628</a> <a href="/A127007" title="a(n) = number of n-digit terms in A108571.">A127007</a> * <a href="/A032219" title="Number of ways to partition n labeled elements into pie slices of different sizes allowing the pie to be turned over.">A032219</a> <a href="/A372802" title="Number of partitions of [n] having exactly one block of maximal size and one block of minimal size (and any number of non-ex...">A372802</a> <a href="/A032144" title="Number of ways to partition n labeled elements into pie slices of different sizes.">A032144</a></div> <div class=sectline>Adjacent sequences: <a href="/A007834" title="Number of point labeled reduced 5-free two-graphs with n nodes.">A007834</a> <a href="/A007835" title="Number of unordered sets of pairs (in-degree, out-degree) for nodes of directed trees on n unlabeled nodes (the edges are di...">A007835</a> <a href="/A007836" title="Springer numbers associated with symplectic group.">A007836</a> * <a href="/A007838" title="Number of permutations of n elements with distinct cycle lengths.">A007838</a> <a href="/A007839" title="Number of polynomials of degree n over GF(2) in which the degrees of all irreducible factors are distinct.">A007839</a> <a href="/A007840" title="Number of factorizations of permutations of n letters into ordered cycles.">A007840</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:Arnold_Knopfmacher">Arnold Knopfmacher</a></div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>More terms from <a href="/wiki/User:Christian_G._Bower">Christian G. Bower</a></div> <div class=sectline>a(0)=1 prepended by <a href="/wiki/User:Alois_P._Heinz">Alois P. Heinz</a>, Aug 29 2015</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified April 7 07:49 EDT 2025. Contains 382552 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>