A095989 INVERTi transform applied to the ordered Bell numbers.

1, 2, 8, 48, 368, 3376, 35824, 430512, 5773936, 85482032, 1384936688, 24380214960, 463522810736, 9468048895792, 206831329017328, 4812581925690288, 118843801816575088, 3104590192664327216, 85544737118902122224, 2479681575659312797872, 75434373300016828382576

Offset

1,2

Comments

A set composition of n is an ordered sequence [S_1, S_2, ..., S_k] where S_i subset of [n] all disjoint and the union of all S_i is [n] (see A000670). A set composition is atomic if S_1 union ... union S_j does not equal [r] for any r < n and j < k. a(n) is the number of atomic set compositions.

A preference function of n is a word of length n where all the numbers 1 through k occur at least once for some k <= n (see A000670). A preference function is atomic if no strict leading subword contains the only occurrences in the word of the letters 1 through j < k. a(n) is the number of atomic preference functions.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..400

Hugo Mlodecki, Decompositions of packed words and self duality of Word Quasisymmetric Functions, arXiv:2205.13949 [math.CO], 2022. See Table 2 p. 8.

Formula

G.f.: 1 - 1/Sum_{k>=0} A000670(k)*q^k.

G.f.: x/(1-2x/(1-2x/(1-4x/(1-3x/(1-6x/(1-4x/(1-8x/(1-5x/(1-...(continued fraction). - Philippe Deléham, Nov 22 2011

G.f.: (1-T(0))/x, where T(k) = 1 - x*(k+1)/(1 - 2*x*(k+1)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 29 2013

Let A(x) be the g.f. A095989, B(x) the g.f. A000670, then A(x) = (1 - 1/B(x))/x. - Sergei N. Gladkovskii, Nov 29 2013

a(n) ~ n! / (2 * log(2)^(n+1)). - Vaclav Kotesovec, Oct 09 2019

Example

Atomic set compositions a(1)=1: [{1}]; a(2)=2: [{12}], [{2},{1}]; a(3)=8: [{123}], [{2},{13}], [{3}, {12}], [{23}, {1}], [{13},{2}], [{2},{3},{1}], [{3},{1},{2}], [{3},{2},{1}].
Atomic preference functions a(1) = 1: 1; a(2)=2: 11, 21; a(3)=8: 111, 212, 221, 211, 121, 312, 231, 321.

Maple

A000670 := proc(n) option remember; local k; if n <=1 then 1 else add(binomial(n, k)*A000670(n-k), k=1..n); fi; end: add(A000670(k)*x^k, k=0..20): series(1-1/%, x, 21): [seq(coeff(%, x, i), i=1..20)];

Mathematica

max = 20; Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)*(i+r)^(n-r)/(i!*(k-i-r)!), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1; s = 1 - 1/Sum[ Fubini[k, 1] q^k, {k, 0, max}] + O[q]^max; CoefficientList[s/q, q] (* Jean-François Alcover, Mar 31 2016 *)

Crossrefs

Cf. A000670, A074664, A095993.

Sequence in context: A003576 A225042 A326887 * A177388 A211196 A334856

Adjacent sequences: A095986 A095987 A095988 * A095990 A095991 A095992

Keyword

nonn

Author

Mike Zabrocki, Jul 18 2004

Status

approved