login
Triangle read by rows: T(n,k) = number of inequivalent linear [n,k] binary codes without 0 columns (n >= 1, 1 <= k <= n).
38

%I #60 Oct 03 2019 02:52:28

%S 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,1,6,12,11,5,1,1,7,21,27,17,6,1,1,9,34,

%T 63,54,25,7,1,1,11,54,134,163,99,35,8,1,1,13,82,276,465,385,170,47,9,

%U 1,1,15,120,544,1283,1472,847,277,61,10,1,1,18,174,1048,3480

%N Triangle read by rows: T(n,k) = number of inequivalent linear [n,k] binary codes without 0 columns (n >= 1, 1 <= k <= n).

%C "A linear (n, k)-code has columns of zeros, if and only if there is some i ∈ n such that x_i = 0 for all codewords x, and so we should exclude such columns." [Fripertinger and Kerber (1995, p. 196)] - _Petros Hadjicostas_, Sep 30 2019

%H Discrete algorithms at the University of Bayreuth, <a href="http://www.algorithm.uni-bayreuth.de/en/research/SYMMETRICA/">Symmetrica</a>.

%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_4.html">Snk2: Number of the isometry classes of all binary (n,k)-codes without zero-columns</a>. [This is a lower triangular array whose lower triangle contains T(n,k). In the papers, the notation S_{nk2} is used.]

%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. [Here S_{nk2} = T(n,k).]

%H Petros Hadjicostas, <a href="/A034253/a034253.txt">Generating function for column k = 4</a>. [Cf. A034345.]

%H Petros Hadjicostas, <a href="/A034253/a034253_1.txt">Generating function for column k = 5</a>. [Cf. A034346.]

%H Petros Hadjicostas, <a href="/A034253/a034253_2.txt">Generating function for column k = 6</a>. [Cf. A034347.]

%H Petr Lisonek, <a href="https://doi.org/10.1016/j.jcta.2006.06.013">Combinatorial families enumerated by quasi-polynomials</a>, J. Combin. Theory Ser. A 114(4) (2007), 619-630. [See Section 5.]

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

%F From _Petros Hadjicostas_, Sep 30 2019: (Start)

%F T(n,k=2) = floor(n/2) + floor((n^2 + 6)/12) = A253186(n).

%F T(n,k) = A076832(n,k) - A076832(n,k-1) for n, k >= 1, where we define A076832(n,0) := 0 for n >= 1.

%F G.f. for column k=2: (x^3 - x - 1)*x^2/((x^2 + x + 1)*(x + 1)*(x - 1)^3).

%F G.f. for column k=3: (x^12 - 2*x^11 + x^10 - x^9 - x^6 + x^4 - x - 1)*x^3/((x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)*(x^2 + x + 1)^2*(x^2 + 1)*(x + 1)^2*(x - 1)^7).

%F G.f. for column k >= 4: modify the Sage program below (cf. function f). It is too complicated to write it here. See also some of the links above.

%F (End)

%e Triangle T(n,k) (with rows n >= 1 and columns k >= 1) begins as follows:

%e 1;

%e 1 1;

%e 1 2 1;

%e 1 3 3 1;

%e 1 4 6 4 1;

%e 1 6 12 11 5 1;

%e 1, 7, 21, 27, 17, 6, 1;

%e 1, 9, 34, 63, 54, 25, 7, 1;

%e 1, 11, 54, 134, 163, 99, 35, 8, 1;

%e ...

%o (Sage) # Fripertinger's method to find the g.f. of column k >= 2 (for small k):

%o def A034253col(k, length):

%o G1 = PSL(k, GF(2))

%o G2 = PSL(k-1, GF(2))

%o D1 = G1.cycle_index()

%o D2 = G2.cycle_index()

%o f1 = sum(i[1]*prod(1/(1-x^j) for j in i[0]) for i in D1)

%o f2 = sum(i[1]*prod(1/(1-x^j) for j in i[0]) for i in D2)

%o f = f1 - f2

%o return f.taylor(x, 0, length).list()

%o # For instance the Taylor expansion for column k = 4 gives

%o print(A034253col(4, 30)) # _Petros Hadjicostas_, Sep 30 2019

%Y Cf. A000012 (column k=1), A253186 (column k=2), A034344 (column k=3), A034345 (column k=4), A034346 (column k=5), A034347 (column k=6), A034348 (column k=7), A034349 (column k=8).

%Y Cf. A034254.

%K tabl,nonn

%O 1,5

%A _N. J. A. Sloane_.