cp's OEIS Frontend

A002846 Number of ways of transforming a set of n indistinguishable objects into n singletons via a sequence of n-1 refinements.

%I A002846 M1251 N0478 #72 Sep 23 2019 10:10:52
%S A002846 1,1,1,2,4,11,33,116,435,1832,8167,39700,201785,1099449,6237505,
%T A002846 37406458,232176847,1513796040,10162373172,71158660160,511957012509,
%U A002846 3819416719742,29195604706757,230713267586731,1861978821637735,15484368121967620,131388840051760458
%N A002846 Number of ways of transforming a set of n indistinguishable objects into n singletons via a sequence of n-1 refinements.
%C A002846 Construct the ranked poset L(n) whose nodes are the A000041(n) partitions of n, with all the partitions into the same number of parts having the same rank. A partition into k parts is joined to a partition into k+1 parts if the latter is a refinement of the former.
%C A002846 The partition n^1 is at the left and the partition 1^n at the right. The illustration by _Olivier Gérard_ shows the posets L(2) through L(8).
%C A002846 Then a(n) is the number of paths of length n-1 in L(n) that join n^1 to 1^n.
%C A002846 Stated another way, a(n) is the number of maximal chains in the ranked poset L(n). (This poset is not a lattice for n > 4.) - Comments corrected by _Gus Wiseman_, May 01 2016
%D A002846 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002846 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002846 Alois P. Heinz, <a href="/A002846/b002846.txt">Table of n, a(n) for n = 1..80</a>
%H A002846 P. Erdős, R. K. Guy and J. W. Moon, <a href="http://jlms.oxfordjournals.org/content/s2-9/4/565.extract">On refining partitions</a>, J. London Math. Soc., 9 (1975), 565-570.
%H A002846 R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: <a href="/A002572/a002572.jpg">front</a>, <a href="/A002572/a002572_1.jpg">back</a> [Annotated scanned copy, with permission]
%H A002846 Olivier Gérard, <a href="/A002846/a002846.png">The ranked posets L(2),...,L(8)</a>
%H A002846 Gus Wiseman, <a href="http://imgur.com/a/UYxDJ">Hasse Diagrams of Partition Refinement Posets n=1..9</a>
%H A002846 Gus Wiseman, <a href="/A002846/a002846_1.png">Hasse Diagrams of Partition Refinement Posets n=1..9, Version 1</a>, [Cached copy, with permission]
%H A002846 Gus Wiseman, <a href="/A002846/a002846_2.png">Hasse Diagrams of Partition Refinement Posets n=1..9, Version 2</a>, [Cached copy, with permission]
%e A002846 a(5) = 4 because there are 4 paths from top to bottom in this lattice:
%e A002846   .
%e A002846        ooooo
%e A002846      /      \
%e A002846   o.oooo   oo.ooo
%e A002846     |    X    |
%e A002846   o.o.ooo  o.oo.oo
%e A002846      \       /
%e A002846       o.o.o.oo
%e A002846           |
%e A002846       o.o.o.o.o
%e A002846   .
%e A002846 (This is the ranked poset L(5), but drawn vertically rather than horizontally.)
%p A002846 v:= l-> [seq(`if`(i=1 or l[i]>l[i-1], seq(subs(1=[][], sort(subsop(
%p A002846          i=[j, l[i]-j][], l))), j=1..l[i]/2), [][]), i=1..nops(l))]:
%p A002846 b:= proc(l) option remember; `if`(max(l)<2, 1, add(b(h), h=v(l))) end:
%p A002846 a:= n-> b([n]):
%p A002846 seq(a(n), n=1..30);  # _Alois P. Heinz_, Sep 22 2019
%t A002846 <<posets.m Table[Build[NumP[n], np]; Last@MaximalChainsDown@np, {n, 1, 25}] (* _Mitch Harris_, Jan 19 2006 *)
%o A002846 (Sage) def A002846(n): return Posets.IntegerPartitions(n).chain_polynomial().leading_coefficient()  # _Max Alekseyev_, Dec 23 2015
%Y A002846 See A213242, A213385, A213427 for related sequences, A327643.
%K A002846 nonn,nice
%O A002846 1,4
%A A002846 _N. J. A. Sloane_. Entry revised by _N. J. A. Sloane_, Jun 11 2012
%E A002846 a(17)-a(25) from _Mitch Harris_, Jan 19 2006