A200660 Sum of the number of arcs describing the set partitions of {1,2,...,n}.

0, 1, 8, 49, 284, 1658, 9974, 62375, 406832, 2769493, 19668054, 145559632, 1121153604, 8974604065, 74553168520, 641808575961, 5718014325296, 52653303354906, 500515404889978, 4905937052293759, 49530189989912312, 514541524981377909, 5494885265473192914

Offset: 1

Author

Nantel Bergeron, Nov 20 2011

Keywords

• nonn

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

• Seiichi Manyama, Table of n, a(n) for n = 1..500
• 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.
• C. André, Basic characters of the unitriangular group, Journal of Algebra, 175 (1995), 287-319.

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

Cf. A367955.

Programs

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];
Array[arcs, 34] (* Jean-François Alcover, Nov 25 2017, translated from Maple *)

Formula

a(n) = Sum_{k=1..n} Stirling2(n,k) * k * (n-k). - Ilya Gutkovskiy, Apr 06 2021

a(n) = Sum_{k=n..n*(n+1)/2} (k-n) * A367955(n,k). - Alois P. Heinz, Dec 11 2023