A007047 Number of chains in power set of n-set.

1, 3, 11, 51, 299, 2163, 18731, 189171, 2183339, 28349043, 408990251, 6490530291, 112366270379, 2107433393523, 42565371881771, 921132763911411, 21262618727925419, 521483068116543603, 13542138653027381291, 371206349277313644531

Offset: 0

Author

N. J. A. Sloane, Roger B. Nelsen

Keywords

• nonn
• nice
• easy

Comments

Stirling transform of A052849(n-1) = [1,2,4,12,48,...] is a(n-1) =[1,3,11,51,299,...]. - Michael Somos, Mar 04 2004

It is interesting to note that a chain in the power set of a set X can be thought of as a fuzzy subset of X and conversely. Chains originating with empty set are fuzzy subsets with empty core and those chains not ending with the whole set are with support strictly contained in X. - Venkat Murali (v.murali(AT)ru.ac.za), May 18 2005

Equals the binomial transform of A000629: (1, 2, 6, 26, 150, 1082, ...) and the double binomial transform of A000670: (1, 1, 3, 13, 75, 541, ...). - Gary W. Adamson, Aug 04 2009

Row sums of A038719. - Peter Bala, Jul 09 2014

Also the number of restricted barred preferential arrangements of an n-set having two bars, where one fixed section is a free section and the other two sections are restricted sections. - Sithembele Nkonkobe, Jun 16 2015

The number of all predictable outcomes of a race between a given number registered competitors, where clean finishes, dead heats (ties), disqualifications, cancellations and their combinations are all counted. (11 outcomes for two competitors, 51 for three, 299 for four, etc.. Example for two competitors shown below.) - Gergely Földvári, Jul 28 2024

Examples

			If there are two registered competitors, A and B, in a race, the total number of predictable outcomes counting all possibilities of clean finishes (f), dead heats (t), disqualifications (d), cancellations (c) and their combinations is 11 (eleven). Here is the breakdown: AfBf, BfAf, AtBt, AfBd, AfBc, BfAd, BfAc, AdBd, AcBc, AdBc, AcBd. - _Gergely Földvári_, Jul 28 2024
		

References

• V. Murali, Counting fuzzy subsets of a finite set, preprint, Rhodes University, Grahamstown 6140, South Africa, 2003.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..424 (first 101 terms from T. D. Noe)
• Paul Barry, General Eulerian Polynomials as Moments Using Exponential Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.9.6.
• Lisa Berry, Stefan Forcey, Maria Ronco, and Patrick Showers, Species substitution, graph suspension, and graded hopf algebras of painted tree polytopes.
• Gergely Földvári, the total number of all predictable outcomes of a race between "k" number of registered competitors: Race Outcome Formula
• Jun Ma, S.-M. Ma, and Y.-N. Yeh, Recurrence relations for binomial-Eulerian polynomials, arXiv preprint arXiv:1711.09016 [math.CO], 2017.
• T. Manneville and V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015-2016.
• Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics (2022) Vol. 10, No. 7, 1161.
• V. Murali, Number of fuzzy subsets of a finite set, fuzzy systems research group, Universities of Rhodes and Fort Hare. [broken link]
• V. Murali and B. B. Makamba, Finite Fuzzy Sets, International Journal of General Systems, Vol. 34, No. 1 (2005), pp. 61-75.
• R. B. Nelsen, Letter to N. J. A. Sloane, Aug. 1991
• R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1991), 23-31.
• S. Nkonkobe and V. Murali, A study of a family of generating functions of Nelsen-Schmidt type and some identities on restricted barred preferential arrangements, arXiv:1503.06172 [math.CO], Apr 2015.
• Index entries for sequences related to posets

Crossrefs

Cf. A000629, A000629, A000670. Row sums of A038719.

Programs

Haskell

a007047 = sum . a038719_row  -- Reinhard Zumkeller, Feb 05 2014

Maple

P := proc(n,x) option remember; if n = 0 then 1 else
   (n*x+2*(1-x))*P(n-1,x)+x*(1-x)*diff(P(n-1,x),x);
   expand(%) fi end:
A007047 := n -> 2^n*subs(x=1/2, P(n,x)):
seq(A007047(n), n=0..19);  # Peter Luschny, Mar 07 2014
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 4,
      add(b(n-j)*binomial(n, j), j=1..n))
    end:
a:= n-> `if`(n=0, 1, b(n)-1):
seq(a(n), n=0..21);  # Alois P. Heinz, Feb 07 2020

Mathematica

Table[LerchPhi[1/2, -n, 2]/2, {n, 0, 10}] (* Vladimir Reshetnikov, Feb 16 2011 *)
Table[2*PolyLog[-n, 1/2] - 1 , {n, 0, 19}] (* Jean-François Alcover, Aug 14 2013 *)
With[{nn=20},CoefficientList[Series[Exp[2x]/(2-Exp[x]),{x,0,nn}],x] Range[ 0,nn]!] (* Harvey P. Dale, Dec 08 2015 *)
Table[-(-1)^k HurwitzLerchPhi[2, -k, -1], {k, 0, 30}] (* Federico Provvedi,Sep 05 2020 *)
a[n_]:= a[n] = 2^n + Sum[Binomial[n, k]*a[k], {k, 0, n-1}]; Table[a[n], {n, 0, 20}] (* Rajesh Kumar Mohapatra, Jul 02 2025 *)
a[0] = 1; a[n_]:= a[n] = 2^n + Sum[Binomial[n, k]*a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 20}] (* Rajesh Kumar Mohapatra, Jul 02 2025 *)

PARI

a(n)=if(n<0,0,n!*polcoeff(subst((y+1)^2/(1-y),y,exp(x+x*O(x^n))-1),n));

PARI

my(x='x+O('x^66)); Vec(serlaplace(exp(2*x)/(2-exp(x)))) \\ Joerg Arndt, Aug 14 2013

Formula

E.g.f.: exp(2*x)/(2-exp(x)).

a(n) = Sum_{k>=1} (k+1)^n/2^k = 2*A000629(n)-1. - Benoit Cloitre, Sep 08 2002

a(n) = one less than sum of quotients with numerator 4 times (n!)((k_1 + k_2 + ... + k_n)!) and with denominator (k_1!k_2!...k_n!)(1!^k_1 2!^k_2...n!^k_n) where the sum is taken over all partitions 1*k_1 + 2*k_2 + ... + n*k_n = n. E.g. a(1) = 3 because the membership value of x to {x} is either 1, alpha with 0 < alpha < 1 or 0. a(2) = 11 since the membership values x and y to {x, y} are 1 >= alpha >= beta >= 0 for {empty set, x, y} in that order or {empty set, y, x} exercising all possible > or = . - Venkat Murali (v.murali(AT)ru.ac.za), May 18 2005

G.f.: 1/Q(0), where Q(k) = 1 - 3*x*(k+1) - 2*x^2*(k+1)*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 02 2013

a(n) ~ 2*n! / (log(2))^(n+1). - Vaclav Kotesovec, Sep 27 2017

a(n) = 4 * A000670(n) - 1 for n > 0. - Alois P. Heinz, Feb 07 2020

a(n) = -(-1)^n Phi(2,-n,-1), where Phi(z,s,a) is the Lerch zeta function. - Federico Provvedi, Sep 05 2020

a(n) = 1 + 2 * Sum_{k=0..n-1} (-1)^(n-k-1) * binomial(n,k) * a(k). - Ilya Gutkovskiy, Apr 28 2021

From Rajesh Kumar Mohapatra, Jul 02 2025: (Start)

a(n) = 2*A000629(n) - 1.

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

a(n) = 2^n + Sum_{k=1..n} binomial(n,k) * a(n-k), a(0) = 1. (End)