login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002846 Number of ways of transforming a set of n indistinguishable objects into n singletons via a sequence of n-1 refinements.
(Formerly M1251 N0478)
43

%I M1251 N0478 #72 Sep 23 2019 10:10:52

%S 1,1,1,2,4,11,33,116,435,1832,8167,39700,201785,1099449,6237505,

%T 37406458,232176847,1513796040,10162373172,71158660160,511957012509,

%U 3819416719742,29195604706757,230713267586731,1861978821637735,15484368121967620,131388840051760458

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

%C 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 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 Then a(n) is the number of paths of length n-1 in L(n) that join n^1 to 1^n.

%C 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A002846/b002846.txt">Table of n, a(n) for n = 1..80</a>

%H 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 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 Olivier Gérard, <a href="/A002846/a002846.png">The ranked posets L(2),...,L(8)</a>

%H Gus Wiseman, <a href="http://imgur.com/a/UYxDJ">Hasse Diagrams of Partition Refinement Posets n=1..9</a>

%H 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 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 a(5) = 4 because there are 4 paths from top to bottom in this lattice:

%e .

%e ooooo

%e / \

%e o.oooo oo.ooo

%e | X |

%e o.o.ooo o.oo.oo

%e \ /

%e o.o.o.oo

%e |

%e o.o.o.o.o

%e .

%e (This is the ranked poset L(5), but drawn vertically rather than horizontally.)

%p v:= l-> [seq(`if`(i=1 or l[i]>l[i-1], seq(subs(1=[][], sort(subsop(

%p i=[j, l[i]-j][], l))), j=1..l[i]/2), [][]), i=1..nops(l))]:

%p b:= proc(l) option remember; `if`(max(l)<2, 1, add(b(h), h=v(l))) end:

%p a:= n-> b([n]):

%p seq(a(n), n=1..30); # _Alois P. Heinz_, Sep 22 2019

%t <<posets.m Table[Build[NumP[n], np]; Last@MaximalChainsDown@np, {n, 1, 25}] (* _Mitch Harris_, Jan 19 2006 *)

%o (Sage) def A002846(n): return Posets.IntegerPartitions(n).chain_polynomial().leading_coefficient() # _Max Alekseyev_, Dec 23 2015

%Y See A213242, A213385, A213427 for related sequences, A327643.

%K nonn,nice

%O 1,4

%A _N. J. A. Sloane_. Entry revised by _N. J. A. Sloane_, Jun 11 2012

%E a(17)-a(25) from _Mitch Harris_, Jan 19 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 06:34 EDT 2024. Contains 371265 sequences. (Running on oeis4.)