|
%I #67 Oct 01 2019 09:34:29
%S 1,1,2,1,3,4,1,4,7,8,1,5,11,15,16,1,7,19,30,35,36,1,8,29,56,73,79,80,
%T 1,10,44,107,161,186,193,194,1,12,66,200,363,462,497,505,506,1,14,96,
%U 372,837,1222,1392,1439,1448,1449,1,16,136,680,1963,3435,4282
%N Triangle T(n,k), read by rows, giving the total number of inequivalent binary linear [n,i] codes with no column of zeros, summed for i <= k (n >= 1, 1 <= k <= n).
%C From _Petros Hadjicostas_, Sep 30 2019: (Start)
%C It seems that Harald Fripertinger at his website defines T(n,k) = T(n,n) for k > n (and thus he gets an orthogonal array). It seems that T(n,n) = A034343(n).
%C It seems that T(n,k=2) = A001399(n) for n >= 2 (with A001399(n=1) = T(1,1)); T(n,k=3) = A034337(n) for n >= 3 (with A034337(n) = T(n,n) for 1 <= n <= 2); T(n,k=4) = A034338(n) for n >= 4 (with A034338(n) = T(n,n) for 1 <= n <= 3); and so on. See the Crossrefs below for more information.
%C To get the g.f. of column k (starting at n = 0 with T(n=0,k) := 1 rather than at n = k), modify the Sage program below (cf. function f).
%C (End)
%H Discrete algorithms at the University of Bayreuth, <a href="http://www.algorithm.uni-bayreuth.de/en/research/SYMMETRICA/">Symmetrica</a>. [This package was used to compute T_{nk2} using the cycle index of PGL_k(2).]
%H Harald Fripertinger, <a href="http://www.mathe2.uni-bayreuth.de/frib/codes/tables.html">Isometry Classes of Codes</a>.
%H Harald Fripertinger, <a href="http://www.mathe2.uni-bayreuth.de/frib/codes/tables_3.html">Tnk2: Number of the isometry classes of all binary (n,r)-codes for 1 <= r <= k without zero-columns</a>. [This is a rectangular array whose lower triangle contains T(n,k).]
%H Harald Fripertinger, <a href="https://imsc.uni-graz.at/fripertinger/codes_bms.html">Enumeration of isometry classes of linear (n,k)-codes over GF(q) in SYMMETRICA</a>, Bayreuther Mathematische Schriften 49 (1995), 215-223. [See pp. 216-218. A C-program is given for calculating T_{nk2} in Symmetrica.]
%H Harald Fripertinger, <a href="https://doi.org/10.1016/S0024-3795(96)00530-7">Cycle of indices of linear, affine, and projective groups</a>, Linear Algebra and its Applications 263 (1997), 133-156. [See p. 152 for the computation of T_{nk2}.]
%H H. Fripertinger and A. Kerber, <a href="https://doi.org/10.1007/3-540-60114-7_15">Isometry classes of indecomposable linear codes</a>. In: G. Cohen, M. Giusti, T. Mora (eds), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, 11th International Symposium, AAECC 1995, Lect. Notes Comp. Sci. 948 (1995), pp. 194-204. [Apparently, the notation for T(n,k) is T_{nk2}.]
%H David Slepian, <a href="https://archive.org/details/bstj39-5-1219">Some further theory of group codes</a>, Bell System Tech. J. 39(5) (1960), 1219-1252.
%H David Slepian, <a href="https://doi.org/10.1002/j.1538-7305.1960.tb03958.x">Some further theory of group codes</a>, Bell System Tech. J. 39(5) (1960), 1219-1252.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cycle_index">Cycle index</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Projective_linear_group">Projective linear group</a>.
%H <a href="/index/Coa#codes_binary_linear">Index entries for sequences related to binary linear codes</a>
%e Triangle T(n,k) (with rows n >= 1 and columns k >= 1) begins as follows:
%e 1;
%e 1, 2;
%e 1, 3, 4;
%e 1, 4, 7, 8;
%e 1, 5, 11, 15, 16;
%e 1, 7, 19, 30, 35, 36;
%e 1, 8, 29, 56, 73, 79, 80;
%e 1, 10, 44, 107, 161, 186, 193, 194; ...
%p # We illustrate how to get a g.f. for column k in Maple when k is small.
%p with(GroupTheory);
%p G := ProjectiveGeneralLinearGroup(4, 2);
%p GroupOrder(G);
%p # We get that the order is 20160.
%p f:=CycleIndexPolynomial(G, [x||(1..20160)]);
%p # We get
%p # 1/20160*x1^15 + 1/192*x1^7*x2^4 + 1/96*x1^3*x2^6 + 1/16*x1^3*x2^2*x4^2 +
%p # 1/18*x1^3*x3^4 + 1/6*x1*x2*x3^2*x6 + 1/8*x1*x2*x4^3 + 1/180*x3^5 + 2/7*x1*x7^2 +
%p # 1/12*x3*x6^2 + 1/15*x5^3 + 2/15*x15
%p # The only dummy variables that appear are x1, x2, x3, x4, x5, x6, x7, and x15.
%p g:=subs(x1 = 1/(1 - y), subs(x2 = 1/(-y^2 + 1), subs(x3 = 1/(-y^3 + 1), subs(x4 = 1/(-y^4 + 1), subs(x5 = 1/(-y^5 + 1), subs(x6 = 1/(-y^6 + 1), subs(x7 = 1/(-y^7 + 1), subs(x15 = 1/(-y^15 + 1), f))))))));
%p # Then we take a Taylor expansion of the above g.f.
%p taylor(g,y=0,50);
%p # We get a Taylor expansion for column k = 4 (i.e., A034338).
%p # _Petros Hadjicostas_, Sep 30 2019
%o (Sage) # Fripertinger's method to find the g.f. of column k for small k:
%o def A076832col(k, length):
%o G = PSL(k, GF(2))
%o D = G.cycle_index()
%o f = sum(i[1]*prod(1/(1-x^j) for j in i[0]) for i in D)
%o return f.taylor(x, 0, length).list()
%o # For instance the Taylor expansion for column k = 4 gives A034338:
%o print(A076832col(4, 30)) # _Petros Hadjicostas_, Sep 30 2019
%Y Columns give truncated versions of A001399 (k = 2), A034337 (k = 3), A034338 (k = 4), A034339 (k = 5), A034340 (k = 6), A034341 (k = 7), A034342 (k = 8), and A034343 (? main diagonal).
%Y Cf. A034253, A076831.
%K nonn,tabl
%O 1,3
%A _N. J. A. Sloane_, Nov 21 2002
%E Revised by _N. J. A. Sloane_, Mar 01 2004
|
