A076831 Triangle T(n,k) read by rows giving number of inequivalent binary linear [n,k] codes (n >= 0, 0 <= k <= n).

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 16, 22, 16, 6, 1, 1, 7, 23, 43, 43, 23, 7, 1, 1, 8, 32, 77, 106, 77, 32, 8, 1, 1, 9, 43, 131, 240, 240, 131, 43, 9, 1, 1, 10, 56, 213, 516, 705, 516, 213, 56, 10, 1, 1, 11, 71, 333, 1060, 1988, 1988

Offset: 0

Author

N. J. A. Sloane, Nov 21 2002

Keywords

• nonn
• tabl
• nice

Comments

"The familiar appearance of the first few rows [...] provides a good example of the perils of too hasty extrapolation in mathematics." - Slepian.

The difference between this triangle and the one for which it can be so easily mistaken is A250002. - Tilman Piesk, Nov 10 2014.

Examples

			     k    0   1   2   3    4    5    6    7    8   9  10  11        sum
   n
   0      1                                                           1
   1      1   1                                                       2
   2      1   2   1                                                   4
   3      1   3   3   1                                               8
   4      1   4   6   4    1                                         16
   5      1   5  10  10    5    1                                    32
   6      1   6  16  22   16    6    1                               68
   7      1   7  23  43   43   23    7    1                         148
   8      1   8  32  77  106   77   32    8    1                    342
   9      1   9  43 131  240  240  131   43    9   1                848
  10      1  10  56 213  516  705  516  213   56  10   1           2297
  11      1  11  71 333 1060 1988 1988 1060  333  71  11   1       6928
		

References

• M. Wild, Enumeration of binary and ternary matroids and other applications of the Brylawski-Lucas Theorem, Preprint No. 1693, Tech. Hochschule Darmstadt, 1994

Links

• Harald Fripertinger, Isometry Classes of Codes.
• Harald Fripertinger, Wnk2: Number of the isometry classes of all binary (n,k)-codes. [This is a rectangular array whose lower triangle contains T(n,k).]
• H. Fripertinger and A. Kerber, Isometry classes of indecomposable linear codes. 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 W_{nk2}; see p. 197.]
• Petros Hadjicostas, Generating function for column k=4.
• Petros Hadjicostas, Generating function for column k=5.
• Petros Hadjicostas, Generating function for column k=6.
• Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.
• David Slepian, Some further theory of group codes, Bell System Tech. J. 39(5) (1960), 1219-1252.
• David Slepian, Some further theory of group codes, Bell System Tech. J. 39(5) (1960), 1219-1252.
• Marcel Wild, Consequences of the Brylawski-Lucas Theorem for binary matroids, European Journal of Combinatorics 17 (1996), 309-316.
• Marcel Wild, The asymptotic number of inequivalent binary codes and nonisomorphic binary matroids, Finite Fields and their Applications 6 (2000), 192-202.
• Marcel Wild, The asymptotic number of binary codes and binary matroids, SIAM J. Discrete Math. 19 (2005), 691-699. [This paper apparently corrects some errors in previous papers.]
• Index entries for sequences related to binary linear codes

Crossrefs

Cf. A006116, A022166, A076766 (row sums).

A034356 gives same table but with the k=0 column omitted.

Columns include A000012 (k=0), A000027 (k=1), A034198 (k=2), A034357 (k=3), A034358 (k=4), A034359 (k=5), A034360 (k=6), A034361 (k=7), A034362 (k=8).

Programs

Sage

# Fripertinger's method to find the g.f. of column k >= 2 (for small k):
def A076831col(k, length):
    G1 = PSL(k, GF(2))
    G2 = PSL(k-1, GF(2))
    D1 = G1.cycle_index()
    D2 = G2.cycle_index()
    f1 = sum(i[1]*prod(1/(1-x^j) for j in i[0]) for i in D1)
    f2 = sum(i[1]*prod(1/(1-x^j) for j in i[0]) for i in D2)
    f = (f1 - f2)/(1-x)
    return f.taylor(x, 0, length).list()
# For instance the Taylor expansion for column k = 4 gives
print(A076831col(4, 30)) # Petros Hadjicostas, Sep 30 2019

Formula

From Petros Hadjicostas, Sep 30 2019: (Start)

T(n,k) = Sum_{i = k..n} A034253(i,k) for 1 <= k <= n.

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

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

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

(End)