login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A331955 Triangle T(n,k) of number of chains of length k in partitions of an n-set ordered by refinement. 3
1, 0, 1, 0, 2, 1, 0, 5, 7, 3, 0, 15, 45, 49, 18, 0, 52, 306, 640, 565, 180, 0, 203, 2268, 8176, 13055, 9645, 2700, 0, 877, 18425, 108388, 279349, 359555, 227745, 56700, 0, 4140, 163754, 1523922, 5967927, 11918270, 12822110, 7095060, 1587600 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Also the number of chains of equivalence relations of length k on a set of n-points.

Number of chains of length k in Stirling numbers of the second kind.

Number of chains of length k in the unordered partition of {1,2,...,n}.

Number of k-level fuzzy equivalence matrices of order n.

LINKS

Alois P. Heinz, Rows n = 0..140, flattened

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.

V. Murali, Combinatorics of counting finite fuzzy subsets, Fuzzy Sets Syst., 157(17)(2006), 2403-2411.

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

FORMULA

T(0, 0) = 1, T(0, k) = 0 for k > 0.

T(n, k) = Sum_{i_k=k..n} (Sum_{i_(k-1)=k-1..i_k - 1} (... (Sum_{i_2=2..i_3 - 1} (Sum_{i_1=1..i_2 - 1} Stirling2(n,i_k) * Stirling2(i_k,i_(k-1)) * ... * Stirling2(i_3,i_2) * Stirling2(i_2,i_1)))...)), where 1 <= k <= n.

EXAMPLE

The triangle T(n,k) begins:

n\k 0   1     2      3      4       5     6     7...

0   1

1   0   1

2   0   2     1

3   0   5     7      3

4   0  15    45     49     18

5   0  52   306    640    565    180

6   0 203  2268   8176  13055   9645   2700

7   0 877 18425 108388 279349 359555 227745 56700

...

The T(3,2) = 7 in the lattice of set partitions of {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,3},{2}} < {{1,2,3}},

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

MAPLE

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

      add(`if`(k=1, 1, b(v, k-1, 1))*Stirling2(n, v), v=k..n-t)))

    end:

T:= (n, k)-> b(n, k, 0):

seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Feb 07 2020

MATHEMATICA

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

T[n_, k_] := b[n, k, 0];

Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-Fran├žois Alcover, Feb 08 2020, after Alois P. Heinz *)

PROG

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

T(n, k) = b(n, k, 0);

matrix(8, 8, n, k, T(n-1, k-1) \\ to see the triangle \\ Michel Marcus, Feb 08 2020

CROSSREFS

Cf. A000007 (column k=0), A000110 (column k=1), A006472 (diagonal), A330804 (row sums).

T(2n,n) gives A332244.

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

Sequence in context: A292323 A059720 A140589 * A185209 A316659 A241218

Adjacent sequences:  A331952 A331953 A331954 * A331956 A331957 A331958

KEYWORD

nonn,tabl

AUTHOR

S. R. Kannan, Rajesh Kumar Mohapatra, Feb 02 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 June 7 01:26 EDT 2020. Contains 334836 sequences. (Running on oeis4.)