A270882 Triangle read by rows: D*(n,m) is the number of direct-sum decompositions of a finite vector space of dimension n with m blocks over GF(2) with a block containing any given nonzero vector.
1, 0, 1, 0, 1, 2, 0, 1, 16, 12, 0, 1, 176, 560, 224, 0, 1, 3456, 40000, 53760, 13440, 0, 1, 128000, 5848832, 20951040, 15554560, 2666496, 0, 1, 9115648, 1934195712, 17826414592, 30398054400, 14335082496, 1791885312, 0, 1, 1259921408, 1510821195776, 37083513880576, 134908940386304, 133854174117888, 43693331447808, 4161269661696
Offset: 0
Examples
Triangle begins: 1; 0, 1; 0, 1, 2; 0, 1, 16, 12; 0, 1, 176, 560, 224; 0, 1, 3456, 40000, 53760, 13440; 0, 1, 128000, 5848832, 20951040, 15554560, 2666496; ...
Links
- Jinyuan Wang, Rows n = 0..10 of triangle, flattened
- David Ellerman, The number of direct-sum decompositions of a finite vector space, arXiv:1603.07619 [math.CO], 2016.
- David Ellerman, The Quantum Logic of Direct-Sum Decompositions, arXiv preprint arXiv:1604.01087 [quant-ph], 2016. See Section 7.5.
Crossrefs
The main diagonal appears to match A377642. - Nikita Babich, Nov 17 2024
Programs
-
Mathematica
(* about 40 seconds on a laptop computer *) g[n_] := q^Binomial[n, 2] * FunctionExpand[QFactorial[n, q]]*(q - 1)^n /. q -> 2; d[k_, m_] :=Map[PadRight[#, 10] &,Table[Table[Total[Map[g[n]/Apply[Times, g[#]]/Apply[Times, Table[Count[#, i], {i, 1, n}]!] &,IntegerPartitions[n, {j}]]], {j, 1, n}], {n, 1, 10}]][[k, m]];d[0, m_] := If[m == 0, 1, 0]; d[k_, 0] := If[k == 0, 1, 0];s[n_, m_] :=Sum[FunctionExpand[QBinomial[n - 1, k, 2]]*2^(k (n - k))*d[k, m - 1], {k, 0, n - 1}]; Table[Table[s[n, m], {m, 1, n}], {n, 1,7}] (* Geoffrey Critzer, May 20 2017 *)
Formula
Recurrence: a(n) = Sum_{k=0..n-1} q-binomial(n-1,k)*q^(n*(n-k))*D_q(k,m-1) where D_q(k,m-1) is given by A270880 for q = 2 and where the q-binomial for q = 2 is given by A022166. This formula is the q-analog of summation formula for the Stirling numbers of the second kind A008277 so when q = 1, it reduces to that formula. - David P. Ellerman, Mar 26 2016
Extensions
Name extended by David P. Ellerman, Mar 26 2016
Row 8 from Geoffrey Critzer, May 20 2017