|
|
A200660
|
|
Sum of the number of arcs describing the set partitions of {1,2,...,n}.
|
|
4
|
|
|
0, 1, 8, 49, 284, 1658, 9974, 62375, 406832, 2769493, 19668054, 145559632, 1121153604, 8974604065, 74553168520, 641808575961, 5718014325296, 52653303354906, 500515404889978, 4905937052293759, 49530189989912312, 514541524981377909, 5494885265473192914
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Supercharacter theory of unipotent upper triangular matrices over a finite field F(2) is indexed by set partitions S(n) of {1,2,...,n} where a set partition P of {1,2,...,n} is a subset { (i,j) : 1 <= i < j <= n} such that (i,j) in P implies (i,k),(k,j) are not in P for all i < l < j.
One of the statistics used to compute the supercharacter table is the number of arcs in P (that is, the cardinality |P| of P).
The sequence we have is arcs(n) = Sum_{P in S(n)} |P|.
|
|
LINKS
|
M. Aguiar, C. Andre, C. Benedetti, N. Bergeron, Z. Chen, P. Diaconis, A. Hendrickson, S. Hsiao, I. M. Isaacs, A. Jedwab, K. Johnson, G. Karaali, A. Lauve, T. Le, S. Lewis, H. Li, K. Magaard, E. Marberg, J-C. Novelli, A. Pang, F. Saliola, L. Tevlin, J-Y. Thibon, N. Thiem, V. Venkateswaran, C. R. Vinroot, N. Yan, and M. Zabrocki, Supercharacters, symmetric functions in noncommuting variables, and related Hopf algebras, arXiv:1009.4134 [math.CO], 2010-2011.
|
|
FORMULA
|
a(n) = Sum_{k=1..n} Stirling2(n,k) * k * (n-k). - Ilya Gutkovskiy, Apr 06 2021
|
|
MAPLE
|
b:=proc(n, k) option remember;
if n=1 and k=1 then RETURN(1) fi;
if k=1 then RETURN(b(n-1, n-1)) fi;
b(n, k-1)+b(n-1, k-1)
end:
arcs:=proc(n) local res, k;
res:=0;
for k to n-1 do res:=res+ k*b(n, k) od;
res
end:
seq(arcs(n), n=1..34);
|
|
MATHEMATICA
|
b[n_, k_] := b[n, k] = Which[n == 1 && k == 1, 1, k == 1, b[n - 1, n - 1], True, b[n, k - 1] + b[n - 1, k - 1]];
arcs[n_] := Module[{res = 0, k}, For[k = 1, k <= n-1, k++, res = res + k * b[n, k]]; res];
|
|
CROSSREFS
|
Cf. A011971 (sequence is computed from Aitken's array b(n,k) arcs(n) = Sum_{k=1..n-1} k*b(n,k)).
Cf. A200580, A200673 (other statistics related to supercharacter table).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|