A008826 -id:A008826 - cp's OEIS frontend

A005121 Number of ultradissimilarity relations on an n-set.

1, 1, 4, 32, 436, 9012, 262760, 10270696, 518277560, 32795928016, 2542945605432, 237106822506952, 26173354092593696, 3375693096567983232, 502995942483693043200, 85750135569136650473360, 16583651916595710735271248, 3611157196483089769387182064, 879518067472225603327860638128

Offset: 1

N. J. A. Sloane

First column in A154960. - Mats Granvik, Jan 18 2009

Number of chains from minimum to maximum in the lattice of set partitions of {1, ..., n} ordered by refinement. - Gus Wiseman, Jul 22 2018

			From _Gus Wiseman_, Jul 22 2018: (Start)
The (3) = 4 chains from minimum to maximum in the lattice of set partitions of {1,2,3}:
  {{1},{2},{3}} < {{1,2,3}}
  {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}
  {{1},{2},{3}} < {{2},{1,3}} < {{1,2,3}}
  {{1},{2},{3}} < {{3},{1,2}} < {{1,2,3}}
(End)

L. Babai and T. Lengyel, A convergence criterion for recurrent sequences with application to the partition lattice, Analysis 12 (1992), 109-119.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 316-321.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..100
L. Babai and T. Lengyel, A convergence criterion for recurrent sequences with application to the partition lattice, Analysis 12 (1992), 109-119.
D. Barsky, J.-P. Bézivin, p-adic Properties of Lengyel's Numbers, Journal of Integer Sequences, 17 (2014), #14.7.3.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 170 - _N. J. A. Sloane_, Apr 18 2014
Steven R. Finch, Lengyel's Constant [Broken link]
Steven R. Finch, Lengyel's Constant [From the Wayback machine]
T. Lengyel, On a recurrence involving Stirling numbers, Europ. J. Combin., 5 (1984), 313-321.
T. Lengyel, On some 2-adic properties of a recurrence involving Stirling numbers, p-Adic Numbers Ultrametric Anal. Appl. 4, No. 3, 179-186 (2012).
F. Murtagh, Counting dendrograms: a survey, Discrete Appl. Math., 7 (1984), 191-199.
T. Prellberg, On the asymptotic analysis of a class of linear recurrences (slides).
M. Schader, Hierarchical analysis: classification with ordinal object dissimilarities, Metrika, 27 (1980), 127-132.
M. Schader, Hierarchical analysis: classification with ordinal object dissimilarities, Metrika, 27 (1980), 127-132. [Annotated scanned copy]
M. Schader, Letter to N. J. A. Sloane, Aug 25 1981.
Eric Weisstein's World of Mathematics, Lengyel's Constant

Row sums of A008826.

Cf. A000110, A000258, A002846, A006541, A006472, A213427, A265947, A317145.

a[1] = 1; a[n_] := a[n] = Sum[StirlingS2[n, k]*a[k], {k, 1, n-1}]; Array[a, 19]
(* Jean-François Alcover, Jun 24 2011, after Vladeta Jovovic *)

{a(n) = local(A); if( n<1, 0, for(k=1, n, A = truncate(A) + x*O(x^k); A = x - A + subst(A, x, exp(x + x*O(x^k)) - 1)); n! * polcoeff(A, n))} /* Michael Somos, Sep 22 2007 */

a(n) = Sum_{i=1..n-1} N_i(n), where N_k(m) = Sum_{j=k..m-1} Stirling2(m, j)*N_{k-1}(j), m=3..n, k=2..m-1; N_1(2)=N_1(3)=...=N_1(n)=1.
a(n) = Sum_{k=1..n-1} Stirling2(n, k)*a(k) [Lengyel]. - Vladeta Jovovic, Apr 16 2003
E.g.f. satisfies Z(z) = 1/2 * (Z(exp(z)-1) - z). [Lengyel]
Asymptotic growth: a(n) ~ C_L*(n!)^2*(2log(2))^(-n)*n^(-1-1/3*log(2)) (Babai and Lengyel), with C_L = 1.0986858055... = A086053 [Flajolet and Salvy].
Sum_{k>=1} a(k-1)/fallfac(n,k) = -1/n^2 + 2*Sum_{k>=1} a(k-1)/n^k, with the falling factorials fallfac(n,k) = Product_{j=0..k-1}(n-j). - Vaclav Kotesovec, Aug 04 2015

More terms from Vladeta Jovovic, Apr 16 2003

A330935 Irregular triangle read by rows where T(n,k) is the number of length-k chains from minimum to maximum in the poset of factorizations of n into factors > 1, ordered by refinement.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, 1, 3, 2, 1, 0, 1, 2, 1, 0, 1, 2, 0, 1, 0, 1, 1, 0, 1, 5, 5, 0, 1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 1, 0, 1, 5, 8, 4, 0, 1, 0, 1, 0, 1, 0, 1, 7, 7, 1, 0, 1, 0, 1, 0, 1, 5, 5, 1, 0, 1

Offset: 1

Gus Wiseman, Jan 04 2020

This poset is equivalent to the poset of multiset partitions of the prime indices of n, ordered by refinement.

			Triangle begins:
   1:          16: 0 1 3 2    31: 1            46: 0 1
   2: 1        17: 1          32: 0 1 5 8 4    47: 1
   3: 1        18: 0 1 2      33: 0 1          48: 0 1 10 23 15
   4: 0 1      19: 1          34: 0 1          49: 0 1
   5: 1        20: 0 1 2      35: 0 1          50: 0 1 2
   6: 0 1      21: 0 1        36: 0 1 7 7      51: 0 1
   7: 1        22: 0 1        37: 1            52: 0 1 2
   8: 0 1 1    23: 1          38: 0 1          53: 1
   9: 0 1      24: 0 1 5 5    39: 0 1          54: 0 1 5 5
  10: 0 1      25: 0 1        40: 0 1 5 5      55: 0 1
  11: 1        26: 0 1        41: 1            56: 0 1 5 5
  12: 0 1 2    27: 0 1 1      42: 0 1 3        57: 0 1
  13: 1        28: 0 1 2      43: 1            58: 0 1
  14: 0 1      29: 1          44: 0 1 2        59: 1
  15: 0 1      30: 0 1 3      45: 0 1 2        60: 0 1 9 11
Row n = 48 counts the following chains (minimum and maximum not shown):
  ()  (6*8)      (2*3*8)->(6*8)       (2*2*2*6)->(2*4*6)->(6*8)
      (2*24)     (2*4*6)->(6*8)       (2*2*3*4)->(2*3*8)->(6*8)
      (3*16)     (2*3*8)->(2*24)      (2*2*3*4)->(2*4*6)->(6*8)
      (4*12)     (2*3*8)->(3*16)      (2*2*2*6)->(2*4*6)->(2*24)
      (2*3*8)    (2*4*6)->(2*24)      (2*2*2*6)->(2*4*6)->(4*12)
      (2*4*6)    (2*4*6)->(4*12)      (2*2*3*4)->(2*3*8)->(2*24)
      (3*4*4)    (3*4*4)->(3*16)      (2*2*3*4)->(2*3*8)->(3*16)
      (2*2*12)   (3*4*4)->(4*12)      (2*2*3*4)->(2*4*6)->(2*24)
      (2*2*2*6)  (2*2*12)->(2*24)     (2*2*3*4)->(2*4*6)->(4*12)
      (2*2*3*4)  (2*2*12)->(4*12)     (2*2*3*4)->(3*4*4)->(3*16)
                 (2*2*2*6)->(6*8)     (2*2*3*4)->(3*4*4)->(4*12)
                 (2*2*3*4)->(6*8)     (2*2*2*6)->(2*2*12)->(2*24)
                 (2*2*2*6)->(2*24)    (2*2*2*6)->(2*2*12)->(4*12)
                 (2*2*2*6)->(4*12)    (2*2*3*4)->(2*2*12)->(2*24)
                 (2*2*3*4)->(2*24)    (2*2*3*4)->(2*2*12)->(4*12)
                 (2*2*3*4)->(3*16)
                 (2*2*3*4)->(4*12)
                 (2*2*2*6)->(2*4*6)
                 (2*2*3*4)->(2*3*8)
                 (2*2*3*4)->(2*4*6)
                 (2*2*3*4)->(3*4*4)
                 (2*2*2*6)->(2*2*12)
                 (2*2*3*4)->(2*2*12)

Row lengths are A001222.
Row sums are A317176.
Column k = 1 is A010051.
Column k = 2 is A066247.
Column k = 3 is A330936.
Final terms of each row are A317145.
The version for set partitions is A008826, with row sums A005121.
The version for integer partitions is A330785, with row sums A213427.
Cf. A001055, A002846, A003238, A007716, A281118, A292504, A292505, A318812, A330665, A330727.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
upfacs[q_]:=Union[Sort/@Join@@@Tuples[facs/@q]];
paths[eds_,start_,end_]:=If[start==end,Prepend[#,{}],#]&[Join@@Table[Prepend[#,e]&/@paths[eds,Last[e],end],{e,Select[eds,First[#]==start&]}]];
Table[Length[Select[paths[Join@@Table[{y,#}&/@DeleteCases[upfacs[y],y],{y,facs[n]}],{n},First[facs[n]]],Length[#]==k-1&]],{n,100},{k,PrimeOmega[n]}]

T(2^n,k) = A330785(n,k).

T(n,1) + T(n,2) = 1.

A008827 Number of proper partitions of a set of n labeled elements.

Original entry on oeis.org

0, 3, 13, 50, 201, 875, 4138, 21145, 115973, 678568, 4213595, 27644435, 190899320, 1382958543, 10480142145, 82864869802, 682076806157, 5832742205055, 51724158235370, 474869816156749, 4506715738447321, 44152005855084344, 445958869294805287, 4638590332229999351

Offset: 2

N. J. A. Sloane

nonn

Previous name: Coefficients from fractional iteration of exp(x) - 1.
From Harry Richman, Mar 18 2023: (Start)
A "proper partition" of a set is a set partition in which there is more than one part, and there is some part which has more than one element.
a(n) is the number of chains of length 2 from the top element to the bottom element in the partition lattice on n labeled objects.
(End)

			For n = 3 there are a(3) = 3 proper partitions of {1,2,3}, which can be represented {12|3}, {13|2}, {23|1}.
For n = 4 there are a(4) = 13 proper partitions of {1,2,3,4}, which can be represented {123|4}, {124|3}, {134|2}, {234|1}, {12|34}, {13|24}, {14|23}, {12|3|4}, {13|2|4}, {14|2|3}, {23|1|4}, {24|1|3}, {34|1|2}.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.

Vincenzo Librandi, Table of n, a(n) for n = 2..200
Ivo Rosenberg, The number of maximal closed classes in the set of functions over a finite domain, J. Combinatorial Theory Ser. A 14 (1973), 1-7. See Table I (it is not certain that this is the same sequence. - _N. J. A. Sloane_, Jun 25 2015)
Ivo Rosenberg and N. J. A. Sloane, Correspondence, 1971

Cf. A000110, A008826.

List([3..30], n-> Bell(n)-2); # G. C. Greubel, Sep 13 2019

[Bell(n) -2: n in [3..30]]; // G. C. Greubel, Sep 13 2019

seq(combinat[bell](n)-2, n=2..31); # Zerinvary Lajos, Sep 29 2006

Table[BellB[n] - 2, {n, 3, 30}] (* Vladimir Joseph Stephan Orlovsky, Jul 06 2011 *)

a(n)=sum(j=2,n--,(j+1)*stirling(n,j,2)) \\ Charles R Greathouse IV, Jul 06 2011

[bell_number(n)-2 for n in (3..30)] # G. C. Greubel, Sep 13 2019

a(n) = A000110(n) - 2.

More terms from Vladeta Jovovic, Jan 02 2004

Name changed and a(2)=0 prepended by Harry Richman, Mar 18 2023

A330727 Irregular triangle read by rows where T(n,k) is the number of balanced reduced multisystems of depth k whose degrees (atom multiplicities) are the prime indices of n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 1, 3, 1, 7, 7, 1, 5, 5, 1, 5, 9, 5, 1, 9, 11, 1, 9, 28, 36, 16, 1, 10, 24, 16, 1, 14, 38, 27, 1, 13, 18, 1, 13, 69, 160, 164, 61, 1, 24, 79, 62, 1, 20, 160, 580, 1022, 855, 272, 1, 19, 59, 45, 1, 27, 138, 232, 123, 1, 17, 77, 121, 61

Offset: 2

Gus Wiseman, Jan 04 2020

A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. A multiset whose multiplicities are the prime indices of n (such as row n of A305936) is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

			Triangle begins:
   {}
   1
   1
   1   1
   1   2
   1   3   2
   1   3
   1   7   7
   1   5   5
   1   5   9   5
   1   9  11
   1   9  28  36  16
   1  10  24  16
   1  14  38  27
   1  13  18
   1  13  69 160 164  61
   1  24  79  62
For example, row n = 12 counts the following multisystems:
  {1,1,2,3}  {{1},{1,2,3}}    {{{1}},{{1},{2,3}}}
             {{1,1},{2,3}}    {{{1,1}},{{2},{3}}}
             {{1,2},{1,3}}    {{{1}},{{2},{1,3}}}
             {{2},{1,1,3}}    {{{1,2}},{{1},{3}}}
             {{3},{1,1,2}}    {{{1}},{{3},{1,2}}}
             {{1},{1},{2,3}}  {{{1,3}},{{1},{2}}}
             {{1},{2},{1,3}}  {{{2}},{{1},{1,3}}}
             {{1},{3},{1,2}}  {{{2}},{{3},{1,1}}}
             {{2},{3},{1,1}}  {{{2,3}},{{1},{1}}}
                              {{{3}},{{1},{1,2}}}
                              {{{3}},{{2},{1,1}}}

Row sums are A318846.
Final terms in each row are A330728.
Row prime(n) is row n of A330784.
Row 2^n is row n of A008826.
Row n is row A181821(n) of A330667.
Column k = 3 is A318284(n) - 2 for n > 2.
Cf. A000111, A002846, A005121, A292504, A318812, A318813, A318847, A318848, A318849, A330475, A330666, A330935.

nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[Reverse[FactorInteger[n]],{p_,k_}:>Table[PrimePi[p],{k}]]]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
totm[m_]:=Prepend[Join@@Table[totm[p],{p,Select[mps[m],1

T(2^n,k) = A008826(n,k).

A059355 Number of chains of n-3 partitions in the reduced partition lattice on n elements.

Original entry on oeis.org

1, 13, 205, 4245, 114345, 3919860, 167310360, 8719666200, 545594049000, 40394317194000, 3494634235092000, 349446163958892000, 40005208010427660000, 5199553600938496800000, 761551300698921532800000, 124863678342008772566400000, 22782147644564103946550400000

Offset: 3

N. J. A. Sloane, Jan 27 2001

nonn

The reduced partition lattice on n elements is the lattice of set partitions ordered by refinement, with the minimum and maximum partitions removed. A chain in a lattice is a subset of lattice elements which is totally ordered. The reduced partition lattice on n elements is ranked, with rank n-2, so a maximal chain has n-2 partitions. - Harry Richman, Mar 30 2023

			From _Harry Richman_, Mar 30 2023: (Start)
For n = 4, a chain of 1 partition is just a partition in the reduced partition lattice. There are 13 such partitions:
  {123|4}
  {124|3}
  {134|2}
  {1|234}
  {12|34}
  {13|24}
  {14|23}
  {12|3|4}
  {13|2|4}
  {14|2|3}
  {1|23|4}
  {1|24|3}
  {1|2|34}
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.

Alois P. Heinz, Table of n, a(n) for n = 3..269

A diagonal of triangle in A008826.

b:= proc(n) option remember; expand(`if`(n=1, 1,
      add(Stirling2(n, j)*b(j)*x, j=0..n-1)))
    end:
a:= n-> coeff(b(n), x, n-2):
seq(a(n), n=3..20);  # Alois P. Heinz, Mar 31 2023

a[1, ] = 1; a[n, x_] := a[n, x] = Sum[StirlingS2[n, k]*a[k, x]*x, {k, 0, n-1}]; Table[CoefficientList[a[n, x], x][[-2]], {n, 3, 17}] (* Jean-François Alcover, Nov 28 2013, after Vladeta Jovovic *)

More terms from Vladeta Jovovic, Jan 02 2004

Name changed by Harry Richman, Mar 30 2023

A330785 Triangle read by rows where T(n,k) is the number of chains of length k from minimum to maximum in the poset of integer partitions of n ordered by refinement.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 5, 8, 4, 0, 1, 9, 25, 28, 11, 0, 1, 13, 57, 111, 99, 33, 0, 1, 20, 129, 379, 561, 408, 116, 0, 1, 28, 253, 1057, 2332, 2805, 1739, 435, 0, 1, 40, 496, 2833, 8695, 15271, 15373, 8253, 1832, 0, 1, 54, 898, 6824, 28071, 67790, 98946, 85870, 40789, 8167

Offset: 1

Gus Wiseman, Jan 03 2020

			Triangle begins:
   1
   0   1
   0   1   1
   0   1   3   2
   0   1   5   8   4
   0   1   9  25  28  11
   0   1  13  57 111  99  33
   0   1  20 129 379 561 408 116
Row n = 5 counts the following chains (minimum and maximum not shown):
  ()  (14)    (113)->(14)    (1112)->(113)->(14)
      (23)    (113)->(23)    (1112)->(113)->(23)
      (113)   (122)->(14)    (1112)->(122)->(14)
      (122)   (122)->(23)    (1112)->(122)->(23)
      (1112)  (1112)->(14)
              (1112)->(23)
              (1112)->(113)
              (1112)->(122)

Row sums are A213427.
Main diagonal is A002846.
Column k=3 is A007042.
Dominated by A330784.
The version for set partitions is A008826.
The version for factorizations is A330935.
Cf. A000111, A000258, A000311, A005121, A141268, A196545, A265947, A300383, A306186, A317141, A317176, A318813, A320160, A330679.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
upr[q_]:=Union[Sort/@Apply[Plus,mps[q],{2}]];
paths[eds_,start_,end_]:=If[start==end,Prepend[#,{}],#]&[Join@@Table[Prepend[#,e]&/@paths[eds,Last[e],end],{e,Select[eds,First[#]==start&]}]];
Table[Length[Select[paths[Join@@Table[{y,#}&/@DeleteCases[upr[y],y],{y,Sort/@IntegerPartitions[n]}],ConstantArray[1,n],{n}],Length[#]==k-1&]],{n,8},{k,n}]

T(n,k) = A330935(2^n,k).

cp's OEIS Frontend

A005121 Number of ultradissimilarity relations on an n-set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A330935 Irregular triangle read by rows where T(n,k) is the number of length-k chains from minimum to maximum in the poset of factorizations of n into factors > 1, ordered by refinement.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A008827 Number of proper partitions of a set of n labeled elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A330727 Irregular triangle read by rows where T(n,k) is the number of balanced reduced multisystems of depth k whose degrees (atom multiplicities) are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A059355 Number of chains of n-3 partitions in the reduced partition lattice on n elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A330785 Triangle read by rows where T(n,k) is the number of chains of length k from minimum to maximum in the poset of integer partitions of n ordered by refinement.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula