A381842 Triangle read by rows: T(n,k) is the number of non-equivalent subsets of size k in S_n, 0 <= k <= n!.

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 4, 10, 41, 103, 309, 691, 1458, 2448, 3703, 4587, 5050, 4587, 3703, 2448, 1458, 691, 309, 103, 41, 10, 4, 1, 1, 1, 1, 6, 37, 715, 13710, 256751, 4140666, 58402198, 726296995, 8060937770, 80604620206, 732149722382

Offset: 0

Author

Raghavendra Tripathi, Mar 09 2025

Keywords

• nonn
• tabf

Comments

We say two subsets A, B of size k are equivalent if there are permutations p, q in S_n such that pAq=B.

The n-th row contains n! + 1 entries corresponding to subsets of S_n of size 0 to n!.

Examples

			Triangle begins:
  [0] 1, 1;
  [1] 1, 1;
  [2] 1, 1, 1;
  [3] 1, 1, 2, 2, 2, 1, 1;
  [4] 1, 1, 4, 10, 41, 103, 309, 691, 1458, 2448, 3703, 4587, 5050, ...;
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..880 (rows 0..6)
• Aman Kushwaha and Raghavendra Tripathi, A note on Erdős matrices and Marcus-Ree inequality, arXiv:2503.09542 [math.MG], 2025. See p. 12.

Crossrefs

Cf. A000041, A362763 (up to conjugation).

Formula

T(n, 1) = 1.

T(n, 2) = A000041(n) - 1.

T(n, k) = T(n, n!-k).

Extensions

a(39) onwards from Andrew Howroyd, Mar 09 2025