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

%I #37 Dec 11 2023 08:27:37

%S 0,1,8,49,284,1658,9974,62375,406832,2769493,19668054,145559632,

%T 1121153604,8974604065,74553168520,641808575961,5718014325296,

%U 52653303354906,500515404889978,4905937052293759,49530189989912312,514541524981377909,5494885265473192914

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

%C 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.

%C One of the statistics used to compute the supercharacter table is the number of arcs in P (that is, the cardinality |P| of P).

%C The sequence we have is arcs(n) = Sum_{P in S(n)} |P|.

%H Seiichi Manyama, <a href="/A200660/b200660.txt">Table of n, a(n) for n = 1..500</a>

%H 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, <a href="http://arxiv.org/abs/1009.4134">Supercharacters, symmetric functions in noncommuting variables, and related Hopf algebras</a>, arXiv:1009.4134 [math.CO], 2010-2011.

%H C. André, <a href="https://doi.org/10.1006/jabr.2001.8734">Basic characters of the unitriangular group</a>, Journal of Algebra, 175 (1995), 287-319.

%F a(n) = Sum_{k=1..n} Stirling2(n,k) * k * (n-k). - _Ilya Gutkovskiy_, Apr 06 2021

%F a(n) = Sum_{k=n..n*(n+1)/2} (k-n) * A367955(n,k). - _Alois P. Heinz_, Dec 11 2023

%p b:=proc(n,k) option remember;

%p if n=1 and k=1 then RETURN(1) fi;

%p if k=1 then RETURN(b(n-1,n-1)) fi;

%p b(n,k-1)+b(n-1,k-1)

%p end:

%p arcs:=proc(n) local res,k;

%p res:=0;

%p for k to n-1 do res:=res+ k*b(n,k) od;

%p res

%p end:

%p seq(arcs(n),n=1..34);

%t 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]];

%t arcs[n_] := Module[{res = 0, k}, For[k = 1, k <= n-1, k++, res = res + k * b[n, k]]; res];

%t Array[arcs, 34] (* _Jean-François Alcover_, Nov 25 2017, translated from Maple *)

%Y Cf. A011971 (sequence is computed from Aitken's array b(n,k) arcs(n) = Sum_{k=1..n-1} k*b(n,k)).

%Y Cf. A200580, A200673 (other statistics related to supercharacter table).

%Y Cf. A367955.

%K nonn

%O 1,3

%A _Nantel Bergeron_, Nov 20 2011