A075729 -id:A075729 - cp's OEIS frontend

A331608 E.g.f.: exp(1 / (1 - sinh(x)) - 1).

1, 1, 3, 14, 85, 632, 5559, 56352, 645929, 8252352, 116189291, 1786361216, 29764770941, 534082233856, 10264484355103, 210312181051392, 4575364233983057, 105310034714202112, 2556360647841415379, 65261358332774277120, 1747713179543456515749

Offset: 0

Ilya Gutkovskiy, Jan 22 2020

nonn

Cf. A003704, A003724, A006154, A075729, A331607, A331611.

nmax = 20; CoefficientList[Series[Exp[1/(1 - Sinh[x]) - 1], {x, 0, nmax}], x] Range[0, nmax]!
A006154[n_] := Sum[Sum[(-1)^j (k - 2 j)^n Binomial[k, j]/2^k, {j, 0, k}], {k, 1, n}]; a[0] = 1; a[n_] := a[n] = Sum[Binomial[n - 1, k - 1] A006154[k] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 20}]

a(0) = 1; a(n) = Sum_{k=1..n} binomial(n-1,k-1) * A006154(k) * a(n-k).

a(n) ~ exp(1/(2^(3/2) * log(1 + sqrt(2))) - 3/4 + 2^(3/4) * sqrt(n) / sqrt(log(1 + sqrt(2))) - n) * n^(n - 1/4) / (2^(5/8) * log(1 + sqrt(2))^(n + 1/4)). - Vaclav Kotesovec, Jan 27 2020

A097236 Number of hierarchical orderings ("societies") with at least 2 elements ("individuals") on each level for n labeled elements.

Original entry on oeis.org

0, 1, 1, 10, 31, 271, 1534, 14393, 117653, 1253524, 13140557, 160679069, 2026451948, 28278471729, 413532314433, 6516434058758, 107958571213579, 1899723866781859, 35092386753388698, 682552407940860353, 13893916425860413469, 296049402365644855888

Offset: 1

Thomas Wieder, Aug 02 2004

nonn

			a(4) = 10. Let : denote the partition of n labeled individuals 1,2,3,4 into x=2 sets (i.e. "societies"). E.g., in 12:34 one has a single society with members 1 and 2 and a further single society with members 3 and 4. Let | denote a higher level (within a single society), e.g., in 1|2 the individual 2 is one level up with respect to individual 1. The order of individuals on a level is insignificant, e.g. 12|34 is equivalent to 21|43.
For n = 4 and x = 2 one has 1234; 12:34; 13:24; 14:23; 12|34; 31|42; 43|21; 24|13; 21|34; 43|12; which gives 10 different hierarchical societies with at least 2 labeled individuals per level.

Alois P. Heinz, Table of n, a(n) for n = 1..175
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Cf. A075729, A097237, A226572.

with(combstruct); SetSeqSetxL:=[T,{T=Set(S), S=Sequence(U,card>=1), U=Set(Z,card >= 2)},labeled];
# where x is an integer 1, 2, 3,... ; x=2 gives 2 individuals per level.
seq (count (SetSeqSetxL,size=j), j=1..20);

terms = 22;
CoefficientList[ Exp[-(-Exp[z]+1+z)/(2-Exp[z]+z)] + O[z]^(terms+1), z] *  Range[0, terms]! // Rest (* Jean-François Alcover, Aug 06 2018 *)

E.g.f.: exp(-(-exp(z)+1+z)/(2-exp(z)+z)).

a(n) ~ exp(1/(2*(c-2)) + 1/(2*(c-1)^2) + 2*sqrt(n/((c-2)*(c-1))) - n - 1) * n^(n-1/4) / (sqrt(2) * (c-1)^(1/4) * (c-2)^(n+1/4)), where c = -LambertW(-1, -exp(-2)) = A226572 = 3.14619322062... . - Vaclav Kotesovec, Sep 08 2014

A143463 Number of multiple hierarchies for n labeled elements.

Original entry on oeis.org

1, 4, 20, 133, 1047, 9754, 103203, 1229330, 16198452, 234110702, 3675679471, 62287376870, 1132138152251, 21963847972941, 452786198062541, 9881445268293457, 227522503290656371, 5510876754647261442, 140040543831299600637, 3724688873146823853387

Offset: 1

Thomas Wieder, Aug 17 2008

nonn

The n labeled elements 1,2,3,...,n can be distributed in A005651(n) ways onto the levels of a single hierarchy. For the present sequence we distributed the n elements onto 1 up to n separate hierarchies. a(n) gives the number of such separate hierarchies for given n.
A hierarchy is a distribution of elements onto levels. Within a hierarchy the occupation number of level l_j is <= the occupation numbers of the levels l_i with i < j. Let the colon ":" separate two levels l_i and l_(j=i+1). Then we may have 1,2,3:4,5, but 1,2:3,4,5 is forbidden since the higher level has a greater occupation number. On the other hand, for a hierarchical ordering the second configuration is allowed.
The present sequence is the Exp transform of A005651.
The present sequence is related to A075729 which gives the number of separated hierarchical orderings. A034691 gives the number of separated hierarchical orderings for unlabeled elements. Thus we have
Hierarchies on elements:
........ unlabeled labeled
single   A000041   A005651
multiple A001970   A143463
Hierarchical orderings on elements:
........ unlabeled labeled
single   A000079   A000670
multiple A034691   A075729

			Let "|" separate two hierarchies. Then we have
n=1 gives 1 arrangement:
1
n=2 gives 4 arrangements:
1,2 1:2 2:1 1|2
n=3 gives 20 arrangements:
1,2,3 1,2:3 1:2:3 1,2|3 1:2|3 1|2|3
1,3:2 3:1:2 1,3|2 1:3|2
2,3:1 2:3:1 2,3|1 2:3|1
1:3:2 2:1|3
2:1:3 3:1|2
3:2:1 3:2|1

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 1..430 (first 200 terms from Alois P. Heinz)
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89.
Thomas Wieder, The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. [From _Thomas Wieder_, Nov 14 2009]

Cf. A000041, A005651, A001970, A143463, A000079, A000670, A034691, A075729.

There is a similar formula for A075729. - Thomas Wieder, Sep 09 2008

A143463:=proc(n::integer)
# Begonnen am: 14.08.2008
# Letzte Aenderung: 14.08.2008
# Subroutines required: ListeMengenzerlegungenAuf, A005651.
local iverbose, Liste, Zerlegungen, Zerlegung, Produkt, Summe, Untermenge, ZahlElemente;
iverbose:=0;
Liste:=[seq( i, i=1..n )];
Zerlegungen:=ListeMengenzerlegungenAuf(Liste);
Summe:=0;
if iverbose=1 then
print("Zerlegungen: ",Zerlegungen);
end if;
for Zerlegung in Zerlegungen do
Produkt:=1;
if iverbose=1 then
print("Zerlegung: ",Zerlegung);
end if;
# Eine Zerlegung besteht aus Untermengen.
for Untermenge in Zerlegung do
ZahlElemente:=nops(Untermenge);
Produkt:=Produkt*A005651(ZahlElemente);
if iverbose=1 then
print("Untermenge: ",Untermenge,"A005651(ZahlElemente)",A005651(ZahlElemente));
end if;
# Ende der Schleife in der Zerlegung.
od;
Summe:=Summe+Produkt;
# Ende der Schleife ueber die Zerlegungen.
od;
print("Resultat:",Summe);
end proc;
A143463 := proc(n::integer) local k,A005651,Resultat; A005651:=array(1..20): A005651[1]:=1: A005651[2]:=3: A005651[3]:=10: A005651[4]:=47: A005651[5]:=246: A005651[6]:=1602: A005651[7]:=11481: A005651[8]:=95503: A005651[9]:=871030: A005651[10]:=8879558: A005651[11]:=98329551: A005651[12]:=1191578522: A005651[13]:=15543026747: A005651[14]:=218668538441: A005651[15]:=3285749117475: A005651[16]:=52700813279423: A005651[17]:=896697825211142: A005651[18]:=16160442591627990: A005651[19]:=307183340680888755: A005651[20]:=6147451460222703502: if n = 0 then Resultat:=1: RETURN(Resultat); end if; Resultat:=0: for k from 1 to n do Resultat:=Resultat+(A143463(n-k)*A005651[k])/((n-k)!*(k-1)!): od; Resultat:=Resultat*(n-1)!; RETURN(Resultat); end proc; [From Thomas Wieder, Sep 09 2008]
# second Maple program:
with(numtheory):
b:= proc(k) option remember; add(d/d!^(k/d), d=divisors(k)) end:
c:= proc(n) option remember; `if`(n=0, 1,
      add((n-1)!/ (n-k)!* b(k) * c(n-k), k=1..n))
    end:
a:= proc(n) option remember; `if`(n=0, 1,
       c(n) +add(binomial(n-1, k-1) *c(k) *a(n-k), k=1..n-1))
    end:
seq(a(n), n=1..25);  # Alois P. Heinz, Oct 10 2008

nmax=20; Rest[CoefficientList[Series[Exp[Product[1/(1-x^k/k!),{k,1,nmax}]-1],{x,0,nmax}],x] * Range[0,nmax]!] (* Vaclav Kotesovec, May 11 2015 *)

Consider the set partitions of the n-set {1,2,...,n}. As usual, Bell(n) denotes the Bell numbers. The i-th set partition SP(i)={U(1),...,U(Z(i))} consists of Z(i) subsets U(j) with j=1,2,...,Z(i). |U(j)| is the number of elements in U(j). Then a(n) = Sum_{i=1..Bell(n)} Product_{j=1..Z(i)} A005651(|U(j)|). E.g.f.: series((1/exp(1))*exp(mul(1/(1-x^k/k!), k=1..12)), x=0,12);
a(n) = (n-1)! * Sum_{k=1..n} (a(n-k) A005651(k))/((n-k)! (k-1)!). - Thomas Wieder, Sep 09 2008
a(n) = Sum_{k=1..n} binomial(n-1,k-1)*A005651(k)*a(n-k) and a(0)=1. - Thomas Wieder, Sep 12 2008

Partially edited by N. J. A. Sloane, Aug 24 2008

More terms from Alois P. Heinz, Oct 10 2008

A331611 E.g.f.: exp(1 / (2 - cosh(x)) - 1) (even powers only).

Original entry on oeis.org

1, 1, 10, 241, 10585, 732826, 73233205, 9955632961, 1764233731270, 394629336427021, 108652463882802505, 36084903957564392206, 14217903951354603567385, 6554505383225768210009041, 3493988190176442653240091010, 2131975894217009666242489287001

Offset: 0

Ilya Gutkovskiy, Jan 22 2020

nonn

Cf. A005046, A050351, A075729, A094088, A331608, A331612.

nmax = 15; Table[(CoefficientList[Series[Exp[1/(2 - Cosh[x]) - 1], {x, 0, 2 nmax}], x] Range[0, 2 nmax]!)[[n]], {n, 1, 2 nmax + 1, 2}]
A094088[0] = 1; A094088[n_] := A094088[n] = Sum[Binomial[2 n, 2 k] A094088[n - k], {k, 1, n}]; a[0] = 1; a[n_] := a[n] = Sum[Binomial[2 n - 1, 2 k - 1] A094088[k] a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 15}]

a(0) = 1; a(n) = Sum_{k=1..n} binomial(2*n-1,2*k-1) * A094088(k) * a(n-k).

a(n) ~ 2^(2*n + 1/4) * exp(1/(2*sqrt(3)*log(2 + sqrt(3))) - 2/3 + sqrt(8*n/log(2 + sqrt(3)))/3^(1/4) - 2*n) * n^(2*n - 1/4) / (3^(1/8) * log(2 + sqrt(3))^(2*n + 1/4)). - Vaclav Kotesovec, Jan 26 2020

A075744 Hierarchies of hierarchies.

Original entry on oeis.org

1, 1, 5, 36, 338, 3898, 53173, 835992, 14864340, 294606273, 6434871231, 153473830678, 3966604562709, 110386840008838, 3289768253831145, 104502173165838799, 3523895395660532937, 125689588963370029163, 4726867751402704638366, 186902021178952943036080

Offset: 0

N. J. A. Sloane, Oct 15 2002

nonn

Stirling transform of A084357 = number of sets of sets of lists. - Thomas Wieder, Jun 19 2005

T. D. Noe, Table of n, a(n) for n=0..100

Cf. A075729, A075756.

Cf. A084357.

m = 20;
f[x_] = Exp[1/(2 - Exp[x]) - 1];
CoefficientList[Exp[f[x] - 1] + O[x]^m, x]*Range[0, m - 1]! (* Jean-François Alcover, Feb 24 2019 *)

E.g.f.: exp(f(x)-1) where f(x) = e.g.f. for A075729.

A089378 Number of one-step transitions between all unlabeled hierarchies of n elements.

Original entry on oeis.org

0, 6, 24, 104, 382, 1414, 4870

Offset: 1

Thomas Wieder, Dec 27 2003

nonn

For given n (= number of elements) we consider two hierarchies H1 and H2. We ask whether a one-step transition is possible from H1 to H2 (if it is possible, then there is also a one-step transition from H2 to H1). In a one-step transition just one single element is moved from its position in H1 to its position in H2.
For example, consider n=4 and H1 = [[2], [2]], H2 = [[2], [1, 1]]. H1 consists of two subhierarchies S1H1 = [2] and S2H1 = [2] with two elements on level 1 in both cases. In H2, we have S1H2 = [2] and S2H2 = [1,1] which means one element on level 1 and one element on level 2 in S2H2. A one-step transition is possible, just move one element in S2H1 (or S1H1) from level 1 to level 2.
As a counterexample, for H1 = [[2], [2]] and H2 = [[1], [1, 1, 1]], a one-step transition does not exist; one needs to move two elements here. For given n, consider the set of all possible unlabeled hierarchies.
How many one-step transitions exist among them? (We count H1 -> H2 and H2 -> H1 as one transition only, not two. The transition H1 -> H1 is a zero-step transition and is not counted.) Answer: For unlabeled hierarchies, one has (with NOOST = number of one-step transitions) n = 1, NOOST = 0; n = 2, NOOST = 3; n = 3, NOOST = 12; n = 4, NOOST = 51; n = 5, NOOST = 175; n = 6, NOOST = 570; n = 7, NOOST = 1914.
We may ask for the number of one-step transitions (NOOST) between all unlabeled hierarchies of n elements with the restriction that no subhierarchies are allowed. As an example, consider n = 4 and the hierarchy H1 = [[2,2]] with two elements on level 1 and two on level 2. Starting from H1 the hierarchies [[1, 3]], [[2, 1, 1]], [[1, 2, 1]] can be reached by moving one element only, but [[1, 1, 2]] cannot be reached in a one-step transitition. The solution is n = 1, NOOST = 0; n = 2, NOOST = 1; n = 3, NOOST = 4; n = 4, NOOST = 13; n = 5, NOOST = 38; n = 6, NOOST = 104; n = 7, NOOST = 272; n = 8, NOOST = 688; n = 9, NOOST = 1696. This is sequence A049611.

			Consider the unlabeled hierarchies for n = 3 elements. Take for example H1 = [1,2] and H2 = [1,1,1]. A one-step transition is possible between H1 and H2 by moving one element of the second level (occupied by two elements) of H1 on the third level, which gives H2.
As a counterexample, consider H1 and H3 = [[1], [1], [1]]. H3 consists of three subhierarchies. In order to get from H1 to H3 one needs to move two elements; no one-step transition is possible.

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Cf. A034691, A049611, A075729, A093694.

A (rather long) Maple program is available from the author.

A109092 Number of hierarchical orderings for n labeled elements with 2 possible classes A and B for levels l>=2. Labeled analog of A104460.

Original entry on oeis.org

1, 6, 53, 619, 8972, 155067, 3109269, 70893872, 1810283331, 51151579619, 1583934062306, 53322541667501, 1938521128765093, 75673000809822670, 3156390306304019025, 140076451219218605087, 6589244960448222899044, 327461842184597424792623, 17141751726301435708168665

Offset: 1

Thomas Wieder, Jun 18 2005

nonn

			Let | denote a separator among different hierarchies of the hierarchical ordering. Let : denote a separator between levels in a hierarchy.
Furthermore, let a[1], a[2],... denote labeled elements.
An element a[i] will be written as a[i,A] if it falls into class A and as a[i,B] if it falls into class B. Note that at level l=1 no classes appear.
Then a(2) = 6 because a[1]a[2], a[1]|a[2], a[1]:a[2,A], a[2]:a[1,A], a[1]:a[2,B], a[2]:a[1,B].

Alois P. Heinz, Table of n, a(n) for n = 1..140
Robert Gill, The number of elements in a generalized partition semilattice, Discrete mathematics 186.1-3 (1998): 125-134. See Example 2.
Norihiro Nakashima, Shuhei Tsujie, Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species, arXiv:1904.09748 [math.CO], 2019.
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89.

Cf. A075729, A104460.

with(combstruct): A109092 := [T, {T=Set(Sequence(S,card>=1)), S=Sequence(U,card>=1), U=Set(Z,card>=1)},labeled]; seq(count(A109092, size=j), j=1..20);

With[{nn=20},CoefficientList[Series[Exp[-(Exp[x]-1)/(-3+2Exp[x])],{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Sep 16 2016 *)

G.f.: exp(-(exp(z)-1)/(-3+2*exp(z))).

A109186 Number of hierarchical orderings of n unlabeled elements where levels are clustered. Labeled analog of A104525.

Original entry on oeis.org

1, 5, 36, 340, 3968, 55045, 883578, 16092772, 327632793, 7369013917, 181373908752, 4847134062319, 139729893353690, 4320778186663065, 142630863311312977, 5005242986601625051, 186036975046460920033, 7299970808014926301354, 301529053235119043206790

Offset: 1

Thomas Wieder, Jun 21 2005, Mar 29 2008

nonn

A109186 is the exp transform of A083355. [From Thomas Wieder, Sep 12 2008]

			a(2) = 5 because [a_{1}a_{2}], [a_{1}]:[a_{2}], [a_{2}]:[a_{1}], [a_{1}]|[a_{2}], [a_{1}][a_{2}].

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Alois P. Heinz, Table of n, a(n) for n = 1..150
Thomas Wieder, Discussion of A109186

Cf. A075729, A104525.

Cf. A104525, A083355, A075729.

Test := [T, {T=Set(S,card>=1), S=Sequence(Set(U,card>=1),card>=1), U=Set(Z,card>=1)}, labeled]; seq(count(Test,size=j),j=1..20);

G.f.: exp(-(-1+exp(exp(z)-1))/(-2+exp(exp(z)-1)))-1.

a(n) = sum_{k=1}^{n} C(n-1,k-1) A083355 a(n-k) and a(0)=1. [From Thomas Wieder, Sep 12 2008]

A136722 Number of preferential arrangements (or hierarchical orderings) on the connected graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 8, 48, 336, 3584, 54592, 1422976, 66836480, 5998884352, 1030861378560, 335994532814848, 206175878632321024, 237596569295651315712, 514414692643000188272640, 2096154545790162572944244736, 16113456361117058761983824232448, 234269143891823701379016369973493760

Offset: 0

Thomas Wieder, Jan 19 2008

			There are A001349(3)=2 connected graphs for n=3 unlabeled elements:
The chain
o-o-o
and the triangle
. o
/..\
o - o.
There are a(3)=8 hierarchical orders on these two graphs.
The chain gives us 6 orderings:
o-o-o
o
|
o-o
. o
/..\
o . o
o . o
.\./
. o
o-o
|
o
o
|
o
|
o
The triangle gives us two orderings:
. o
/..\
o - o
o - o
\../
. o

Cf. A001349, A011782, A136723, A034691, A075729.

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A136722(n):
    if n == 0: return 1
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n<Chai Wah Wu, Jul 03 2024

a(n)=A001349(n)*A011782(n).

More terms from Alois P. Heinz, Apr 21 2012

A354290 Expansion of e.g.f. exp(f(x) - 1) where f(x) = 1/(3 - 2*exp(x)).

Original entry on oeis.org

1, 2, 14, 142, 1878, 30494, 585398, 12946910, 323717622, 9020101470, 276940926646, 9283709731806, 337237965060982, 13191050077634654, 552593521885522486, 24677110613547498718, 1169994350288769049334, 58684818937875321715038

Offset: 0

Seiichi Manyama, May 23 2022

nonn

Cf. A075729, A354291.

Cf. A004123, A354286, A354288.

my(N=20, x='x+O('x^N)); Vec(serlaplace(exp(2*(exp(x)-1)/(3-2*exp(x)))))

a_vector(n) = my(v=vector(n+1)); v[1]=1; for(i=1, n, v[i+1]=sum(j=1, i, sum(k=0, j, 2^k*k!*stirling(j, k, 2))*binomial(i-1, j-1)*v[i-j+1])); v;

a(0) = 1; a(n) = Sum_{k=1..n} A004123(k+1) * binomial(n-1,k-1) * a(n-k).
a(n) = Sum_{k=0..n} 2^k * A000262(k) * Stirling2(n,k).
a(n) ~ exp(1/(6*log(3/2)) - 5/6 + 2*sqrt(n)/sqrt(3*log(3/2)) - n) * (n^(n - 1/4) / (sqrt(2) * 3^(1/4) * log(3/2)^(n + 1/4))). - Vaclav Kotesovec, May 23 2022

cp's OEIS Frontend

A331608 E.g.f.: exp(1 / (1 - sinh(x)) - 1).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A097236 Number of hierarchical orderings ("societies") with at least 2 elements ("individuals") on each level for n labeled elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A143463 Number of multiple hierarchies for n labeled elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A331611 E.g.f.: exp(1 / (2 - cosh(x)) - 1) (even powers only).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A075744 Hierarchies of hierarchies.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A089378 Number of one-step transitions between all unlabeled hierarchies of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A109092 Number of hierarchical orderings for n labeled elements with 2 possible classes A and B for levels l>=2. Labeled analog of A104460.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A109186 Number of hierarchical orderings of n unlabeled elements where levels are clustered. Labeled analog of A104525.

Views

Author

Keywords

Comments

Examples

References

Links