login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A331957 Number of rooted chains in set partitions of {1, 2, ..., n}. 5
1, 1, 2, 8, 64, 872, 18024, 525520, 20541392, 1036555120, 65591856032, 5085891210864, 474213645013904, 52346708185187392, 6751386193135966464, 1005991884967386086400, 171500271138273300946720, 33167303833191421470542496, 7222314392966179538774364128, 1759036134944451206655721276256 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also the number of chains of Stirling numbers of the second kind such that the first term of the chains is either {{1}, {2}, ..., {n}} or {{1,2,...,n}}.

Number of rooted fuzzy equivalence matrices of order n.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..261

S. R. Kannan and Rajesh Kumar Mohapatra, Counting the Number of Non-Equivalent Classes of Fuzzy Matrices Using Combinatorial Techniques, arXiv preprint arXiv:1909.13678 [math.GM], 2019.

V. Murali, Equivalent finite fuzzy sets and Stirling numbers, Inf. Sci., 174 (2005), 251-263.

R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1) (1991), 23-31.

FORMULA

a(n) = Sum_{k=0..n} A331956(n,k).

EXAMPLE

The a(3) = 8 in the lattice of set partitions of {1,2,3}:

{{1},{2},{3}},

{{1},{2},{3}} < {{1,2},{3}},

{{1},{2},{3}} < {{1,3},{2}},

{{1},{2},{3}} < {{1},{2,3}},

{{1},{2},{3}} < {{1,2,3}},

{{1},{2},{3}} < {{1,2},{3}} < {{1,2,3}},

{{1},{2},{3}} < {{1,3},{2}} < {{1,2,3}},

{{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}.

Or,

{{1,2,3}},

{{1,2,3}} > {{1,2},{3}},

{{1,2,3}} > {{1,3},{2}},

{{1,2,3}} > {{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}}.

MAPLE

b:= proc(n, k, t) option remember; `if`(k<0 or k>n, 0, `if`(k=1 or

      {n, k}={0}, 1, add(b(v, k-1, 1)*Stirling2(n, v), v=k..n-t)))

    end:

a:= n-> add(b(n, k, 0), k=0..n):

seq(a(n), n=0..20);  # Alois P. Heinz, Feb 09 2020

MATHEMATICA

b[n_, k_, t_] := b[n, k, t] = If[k < 0 || k > n, 0, If[k == 1 || Union@{n, k} =={0}, 1, Sum[b[v, k - 1, 1]*StirlingS2[n, v], {v, k, n - t}]]];

a[n_] := Sum[b[n, k, 0], {k, 0, n}];

a /@ Range[0, 30]

PROG

(PARI) b(n, k, t) = {if (k < 0, return(0)); if ((n==0) && (k==0), return (1)); if ((k==1) && (n>0), return(1)); sum(v = k, n - t, if (k==1, 1, b(v, k-1, 1))*stirling(n, v, 2)); }

a(n) = sum(k=0, n, b(n, k, 0); ); \\ Michel Marcus, Feb 09 2020

CROSSREFS

Row sums of A331956.

Cf. A000110, A058692, A006472.

Cf. A008277, A048993, A328044, A330301, A330302.

Sequence in context: A153531 A153560 A321059 * A134956 A011803 A007625

Adjacent sequences:  A331954 A331955 A331956 * A331958 A331959 A331960

KEYWORD

nonn

AUTHOR

S. R. Kannan, Rajesh Kumar Mohapatra, Feb 02 2020

EXTENSIONS

More terms from Michel Marcus, Feb 08 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 27 03:09 EST 2022. Contains 350601 sequences. (Running on oeis4.)