A330302 -id:A330302 - cp's OEIS frontend

A331957 Number of rooted chains in set partitions of {1, 2, ..., n}.

1, 1, 2, 8, 64, 872, 18024, 525520, 20541392, 1036555120, 65591856032, 5085891210864, 474213645013904, 52346708185187392, 6751386193135966464, 1005991884967386086400, 171500271138273300946720, 33167303833191421470542496, 7222314392966179538774364128, 1759036134944451206655721276256

Offset: 0

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

nonn

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.

			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}}.

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.

Row sums of A331956.
Cf. A000110, A058692, A006472.
Cf. A008277, A048993, A328044, A330301, A330302.
Cf. A086053.

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

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]

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

from sympy.functions.combinatorial.numbers import stirling as s
from functools import cache
@cache
def a(n): return 1 + sum(s(n, k) * a(k) for k in range(1, n)) # David Radcliffe, Jul 01 2025

a(n) = Sum_{k=0..n} A331956(n,k).
Conjecture from Mikhail Kurkov, Jun 25 2025: (Start)
a(n) = R(n,0) where
  R(0,0) = 1,
  R(n,k) = (k+1) * Sum_{j=k..n-1} R(n-1,j) for 0 <= k < n,
  R(n,n) = Sum_{j=0..n-1} R(n,j). (End)
a(n) ~ A086053 * n!^2 / (2^(n-1) * log(2)^n * n^(1 + log(2)/3)). - Vaclav Kotesovec, Jul 01 2025
a(n) = 1 + Sum_{k=1..n-1} Stirling2(n,k)*a(k). - Rajesh Kumar Mohapatra, Jul 01 2025

More terms from Michel Marcus, Feb 08 2020

A330804 Number of chains in partitions of [n] ordered by refinement.

Original entry on oeis.org

1, 1, 3, 15, 127, 1743, 36047, 1051039, 41082783, 2073110239, 131183712063, 10171782421727, 948427290027807, 104693416370374783, 13502772386271932927, 2011983769934772172799, 343000542276546601893439, 66334607666382842941084991, 14444628785932359077548728255, 3518072269888902413311442552511

Offset: 0

S. R. Kannan, Rajesh Kumar Mohapatra, Jan 01 2020

nonn

Also the number of fuzzy equivalence matrices of order n.
Number of chains of equivalence relations on a set of n-elements.
Number of chains in Stirling numbers of the second kind.
Number of chains in the unordered partition of {1,...,n}.

			Consider the set S = {1, 2, 3}. The a(3) = 5+ 7+ 3 = 15 in the lattice of set partitions of {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},{2},{3}} < {{1,3},{2}}  {{1},{2},{3}} < {{1,3},{2}} < {{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,2,3}}      {{1,2},{3}} < {{1,2,3}}
               {{1,3},{2}} < {{1,2,3}}
               {{1},{2,3}} < {{1,2,3}}

Alois P. Heinz, Table of n, a(n) for n = 0..262
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.

Cf. A008277, A048993, A000110, A143494, A006472.
Cf. A007047, A328044, A330301, A330302, A331955.
Cf. A131407, A086053.

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:
a:= n-> add(b(n, k, 0), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 07 2020
# second Maple program:
a:= proc(n) option remember; uses combinat;
      bell(n) + add(stirling2(n, i)*a(i), i=1..n-1)
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Sep 03 2020

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}]]];
a[n_] := Sum[b[n, k, 0], {k, 0, n}];
a /@ Range[0, 20] (* Jean-François Alcover, Feb 08 2020, after Alois P. Heinz *)

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));}
a(n) = sum(k=0, n, b(n, k, 0);); \\ Michel Marcus, Feb 08 2020

a(n) = Sum_{k=0..n} A331955(n,k).
a(n) = Bell(n) + Sum_{i=1..n-1} Stirling2(n,i)*a(i). - Alois P. Heinz, Sep 03 2020
a(n) ~ A086053 * n!^2 / (2^(n-2) * log(2)^n * n^(1 + log(2)/3)). - Vaclav Kotesovec, Jul 01 2025
a(n) = 2 * A331957(n) - 1 = 4 * A005121(n) - 1 for n > 1. - Rajesh Kumar Mohapatra, Jul 01 2025

More terms from Michel Marcus, Feb 07 2020

A331955 Triangle T(n,k) of number of chains of length k in partitions of an n-set ordered by refinement.

Original entry on oeis.org

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

Offset: 0

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

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.

			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}}.

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.

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.

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

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 *)
T[n_, k_] := T[n, k] = If[k < 0 || k > n, 0, If[(n == 0 && k == 0), 1, If[k == 1, BellB[n], Sum[If[r >= 0, StirlingS2[n, r]*T[r, k - 1], 0], {r, k - 1, n - 1}]]]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Rajesh Kumar Mohapatra, Jul 02 2025 *)

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

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.
T(n,k) = Sum_{j=k-1..n-1} Stirling2(n,j)*T(j,k-1), 2 <= k <= n; T(n,1) = Bell(n), n >= 1; T(n,0) = A000007(n). - Rajesh Kumar Mohapatra, Jul 01 2025

A331956 Triangle T(n,k) read by rows: number of rooted chains of length k in set partitions of n labeled points.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 4, 3, 0, 1, 14, 31, 18, 0, 1, 51, 255, 385, 180, 0, 1, 202, 2066, 6110, 6945, 2700, 0, 1, 876, 17549, 90839, 188510, 171045, 56700, 0, 1, 4139, 159615, 1364307, 4603620, 7314650, 5507460, 1587600

Offset: 0

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

Also the number of chains of length k in unordered set partitions of {1,2,...,n} such that the first term of the chains is either {{1}, {2},...,{n}} or {{1,2,..,n}}.

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

			Triangle T(n,k) begins:
n\k | 0 1   2     3     4      5      6     7
----+-----------------------------------------
  0 | 1
  1 | 0 1
  2 | 0 1   1
  3 | 0 1   4     3
  4 | 0 1  14    31    18
  5 | 0 1  51   255   385    180
  6 | 0 1 202  2066  6110   6945   2700
  7 | 0 1 876 17549 90839 188510 171045 56700
  ...
The T(3,2) = 4 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}}.
Or,
{{1,2,3}} > {{1,2},{3}},
{{1,2,3}} > {{1,3},{2}},
{{1,2,3}} > {{1},{2,3}},
{{1,2,3}} > {{1},{2},{3}}.

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.
R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1) (1991), 23-31.

Cf. A000007 (column k=0), A057427 (column k=1), A058692 (column k=2), A006472 (diagonal), A331957 (row sums).

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

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:
T:= (n, k)-> b(n, k, 0):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Feb 09 2020

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}]]];
T[n_, k_] := b[n, k, 0];
Table[T[n, k], {n, 0, 20}, {k, 0, n}] // Flatten

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));}
T(n, k) = b(n, k, 0);
matrix(8,8,n, k, T(n-1, k-1)) \\ to see the triangle \\ Michel Marcus, Feb 09 2020

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

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

A330032 The number of chains of strictly rooted upper triangular or lower triangular matrices of order n.

Original entry on oeis.org

1, 2, 26, 9366, 204495126, 460566381955706, 162249649997008147763642, 12595124129900132067036747870669270, 288398561903310939256721956218813835167026180310, 2510964964470962082968627390938311899485883615067802615950711482

Offset: 0

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

nonn

Also, the number of chains in the power set of (n^2-n)/2-elements such that the first term of the chains is either an empty set or a set of (n^2-n)/2-elements.
The number of rooted chains of 2-element subsets of {0,1, 2, ..., n} that contain no consecutive integers.
The number of distinct rooted reflexive symmetric fuzzy matrices of order n.
The number of chains in the set consisting of all n X n reflexive symmetric matrices such that the first term of the chains is either reflexive symmetric matrix or unit matrix.

Alois P. Heinz, Table of n, a(n) for n = 0..28
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.
R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1) (1991), 23-31.
M. Tărnăuceanu, The number of chains of subgroups of a finite elementary abelian p-group, arXiv preprint arXiv:1506.08298 [math.GR], 2015.

Cf. A000629, A038719, A007047, A328044, A330301, A330302, A330804, A331957.

a(n) = A000629((n^2-n)/2).

Missing term a(6) = 162249649997008147763642 inserted by Georg Fischer, Jul 15 2024

A329712 The number of rooted chains in the lattice of (0, 1) matrices of order n.

Original entry on oeis.org

1, 2, 150, 14174522, 10631309363962710, 213394730876951551651166996282, 288398561903310939256721956218813835167026180310, 55313586130829865212025793302979452922870356482030868613037427298852922

Offset: 0

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

nonn

Also, the number of n X n distinct rooted fuzzy matrices.
The number of chains in the power set of n^2-elements such that the first term of the chains is either an empty set or a set of n^2-elements.
The number of chains in the collection of all binary (crisp or Boolean or logical) matrices of order n such that the first term of the chains is either null matrix or unit matrix.

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 and B. Makamba, Finite Fuzzy Sets, Int. J. Gen. Syst., Vol. 34 (1) (2005), pp. 61-75.
R. B. Nelsen and H. Schmidt, Jr., Chains in power sets, Math. Mag., 64 (1) (1991), 23-31.
M. Tărnăuceanu, The number of chains of subgroups of a finite elementary abelian p-group, arXiv preprint arXiv:1506.08298 [math.GR], 2015.

Cf. A000629, A038719, A007047, A328044, A330301, A330302, A330804, A331957.

a(n) = A000629(n^2).

A329911 The number of rooted chains of reflexive matrices of order n.

Original entry on oeis.org

1, 1, 6, 9366, 56183135190, 5355375592488768406230, 22807137588023760967484928392369803926, 9821625950779149908637519199878777711089567893389821437206

Offset: 0

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

nonn

Also, the number of n X n distinct rooted reflexive fuzzy matrices.
The number of chains in the power set of (n^2-n)-elements such that the first term of the chains is either an empty set or a set of (n^2-n)-elements.
The number of chains in the collection of all reflexive matrices of order n such that the first term of the chains is either identity matrix or unit matrix.

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, Combinatorics of counting finite fuzzy subsets, Fuzzy Sets Syst., 157(17)(2006), 2403-2411.
M. Tărnăuceanu, The number of chains of subgroups of a finite elementary abelian p-group, arXiv preprint arXiv:1506.08298 [math.GR], 2015.

Cf. A000629, A038719, A007047, A328044, A330301, A330302, A330804, A331957.

a(n) = A000629(n^2-n).

cp's OEIS Frontend

A331957 Number of rooted chains in set partitions of {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A330804 Number of chains in partitions of [n] ordered by refinement.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A331955 Triangle T(n,k) of number of chains of length k in partitions of an n-set ordered by refinement.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A331956 Triangle T(n,k) read by rows: number of rooted chains of length k in set partitions of n labeled points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A330032 The number of chains of strictly rooted upper triangular or lower triangular matrices of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A329712 The number of rooted chains in the lattice of (0, 1) matrices of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A329911 The number of rooted chains of reflexive matrices of order n.

Views

Author

Keywords

Comments

Links

Crossrefs