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

Author

Mike Zabrocki, Jul 18 2004

Keywords

• nonn

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.

Examples

			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.
		

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.

Crossrefs

Cf. A000670, A074664, A095993.

Programs

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 *)

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