A076766 -id:A076766 - cp's OEIS frontend

A174743 Partial sums of A076766.

1, 3, 7, 15, 31, 63, 131, 279, 621, 1469, 3766, 10694, 34728, 133582, 636719, 3955451, 33664265, 407703531, 7147333784, 180948983492, 6537204164708, 332740721681412, 23627093701822296, 2324803141466748032, 315610211340647518667, 58953876234603150481383

Offset: 0

Jonathan Vos Post, Nov 30 2010

nonn

Number of inequivalent binary linear codes of length <= n. Also the total number of nonisomorphic binary matroids on an k-set for all k <= n. The subsequence of primes is: 3, 7, 31, 131.

			a(14) = 1 + 2 + 4 + 8 + 16 + 32 + 68 + 148 + 342 + 848 + 2297 + 6928 + 24034 + 98854 + 503137 = 636719 is prime.

Cf. A076766, A076831, A034328, A055545.

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

Original entry on oeis.org

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

N. J. A. Sloane, Nov 21 2002

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

			     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

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

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

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

# 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

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)

A227960 Big equivalence classes (A227723) related to subgroups of nimber addition (A190939).

Original entry on oeis.org

1, 3, 6, 15, 24, 60, 105, 255, 384, 960, 1632, 1680, 4080, 15555, 27030, 65535, 98304, 245760, 417792, 430080, 1044480, 1582080, 3947520, 3982080, 6908160, 6919680, 16776960, 106991625, 267448335, 1019462460, 1771476585, 4294967295

Offset: 0

Tilman Piesk, Aug 01 2013

A subsequence of A227723, showing all the big equivalence classes that contain Boolean functions related to subgroups of nimber addition (A190939).
Forms a triangle with row lengths A034343 = 1, 1, 2, 4, 8, 16, 36, 80...:
1,
3,
6, 15,
24, 60, 105, 255,
384, 960, 1632, 1680, 4080, 15555, 27030, 65535...
The left column a( 1,2,4,8,16,32,68,148... ) = a( A076766 ) = 3 ,6, 24, 384, 98304... is probably A001146 * 3/2, which is also A006017( A000079 ).
The first A076766(n) entries correspond to the first A006116(n) entries of A190939. (The first 148 here, for n = 7,  correspond to the first 29212 there.) The entries of A190939 can be generated from this sequence.
Among the first A076766(n) entries are A076831(n;0...n) with weight 2^0...2^n. (Among the first 148 are 1, 7, 23, 43, 43, 23, 7, 1 with weights 1, 2, 4, 8, 16, 32, 64, 128.)
a(n) appears to be divisible by 3 for n>0, and the odd part of a(n) is almost always squarefree. - Ralf Stephan, Aug 02 2013

Tilman Piesk, Table of n, a(n) for n = 0..147
Tilman Piesk, a(n) for n = 0..147 and corresponding entries of A190939 in reverse binary. Prime factors and numbers of prime factors (A001222).
Tilman Piesk, Subgroups of nimber addition (Wikiversity)

Subsequence of A227723 (all becs). All entries are also in A227963 (all sona-secs). Neither shares the property of divisibility by 3.
A190939, A034343, A076766, A076831.
The prime factors contain many prime factors of Fermat numbers (A023394).

a( A076766 - 1 ) = A001146 - 1 = A051179.

a( A076766 ) = A001146 * 3/2 (probably).

A250002 Triangle read by rows: T(n,k) = number of inequivalent binary linear [n,k] codes minus C(n,k).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 2, 8, 8, 2, 0, 0, 0, 0, 4, 21, 36, 21, 4, 0, 0, 0, 0, 7, 47, 114, 114, 47, 7, 0, 0, 0, 0, 11, 93, 306, 453, 306, 93, 11, 0, 0, 0, 0, 16, 168, 730, 1526, 1526, 730, 168, 16, 0, 0

Offset: 0

Tilman Piesk, Nov 10 2014

The triangle of inequivalent binary linear [n,k] codes (A076831) looks much like Pascal's triangle (A007318). They start to differ in the middle of row 6. This triangle is the difference between them. Its row sums are A250003 - the difference between the numbers of inequivalent binary linear codes of length n (A076766) and the powers of two (A000079).

			      k   0   1   2   3   4    5    6   7   8   9  10  11      sums
   n
   0      0                                                       0
   1      0   0                                                   0
   2      0   0   0                                               0
   3      0   0   0   0                                           0
   4      0   0   0   0   0                                       0
   5      0   0   0   0   0    0                                  0
   6      0   0   1   2   1    0    0                             4
   7      0   0   2   8   8    2    0   0                        20
   8      0   0   4  21  36   21    4   0   0                    86
   9      0   0   7  47 114  114   47   7   0   0               336
  10      0   0  11  93 306  453  306  93  11   0   0          1273
  11      0   0  16 168 730 1526 1526 730 168  16   0   0      4880
Row 6 of A076831 is (1,6,16,22,16,6,1) and row 6 of A007318 is (1,6,15,20,15,6,1). Row 6 of this triangle is their difference (0,0,1,2,1,0,0).

Cf. A076831, A007318, A250003.

a(n,k) = A076831(n,k) - A007318(n,k).

A227962 Triangle of permutations that assign sona-becs (A227960) to their complements.

Original entry on oeis.org

0, 1, 0, 3, 1, 2, 0, 7, 3, 5, 1, 6, 2, 4, 0, 15, 7, 12, 3, 13, 5, 9, 1, 14, 6, 10, 11, 2, 4, 8, 0, 31, 15, 26, 7, 28, 12, 20, 3, 29, 13, 22, 23, 5, 9, 17, 1, 30, 14, 24, 25, 6, 27, 10, 11, 18, 19, 2, 21, 4, 8, 16, 0

Offset: 0

Tilman Piesk, Aug 04 2013

Subgroups of nimber addition (sona, A190939) have complements (defined using their Walsh spectrum). All sona in the same sona-bec (A227960) have complements in a unique sona-bec, which thus can be called its complement.
The permutation in row n of this triangle assigns complementary sona-becs of size 2^n to each other. (It is thus self-inverse.)
Even rows contain fixed points, because some sona-becs with weight 2^(n/2) are their own complements. E.g., in row 4 the fixed points are 3, 5, 10 and 11.
Each row contains the row before as a subsequence.
0 is always complement with A076766(n)-1, so each row ends with 0, and the left column is A076766-1 (not A000225).

			T(4,1)=7 and T(4,7)=1, so 1 and 7 are complements for n=4.
T(4,3)=3, so 3 is its own complement for n=4.
Triangle begins:
    k = 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
n
0       0
1       1   0
2       3   1   2   0
3       7   3   5   1   6   2   4   0
4      15   7  12   3  13   5   9   1  14   6  10  11   2   4   8   0

Tilman Piesk, Rows 0...7, flattened
Tilman Piesk, Rows 0...7 (the same with emphasis on subsequences)
Tilman Piesk, Complement pairs for n=0...7
Tilman Piesk, Graphic for n=4, complements are symmetric to each other
Tilman Piesk, Subgroups of nimber addition (Wikiversity)

A250003 Number of inequivalent binary linear codes of length n minus 2^n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 4, 20, 86, 336, 1273, 4880, 19938, 90662, 486753, 3285964, 29643278, 373908194, 6739368109, 173801125420, 6356254132640, 326203515419552, 23294352975946580, 2301176047756537128, 313285408199163993419, 58638266023262469408284

Offset: 0

Tilman Piesk, Nov 10 2014

nonn

The numbers of inequivalent binary linear codes of length n (A076766) start like the powers of two (A000079). This sequence is their difference. These are the row sums of the triangle A250002.

			There are 342 inequivalent binary linear codes of length 8, and 2^8 = 256, hence a(8) = 342 - 256 = 86.

Cf. A076766, A000079, A250002.

a(n) = A076766(n) - A000079(n).

A076892 Number of inequivalent ternary linear codes of length n. Also the number of nonisomorphic ternary matroids on an n-set.

Original entry on oeis.org

2, 4, 8, 17, 36, 85, 216, 640, 2292, 9665, 80836, 1070709, 27652010, 1345914266, 115596164732

Offset: 1

Marcel Wild (mwild(AT)sun.ac.za), Nov 26 2002

			The two linear ternary codes of length 3, {(0,0,0), (1,-1,0), (-1,1,0) } and {(0,0,0), (-1,0,-1), (1,0,1) } are equivalent because the latter arises from the former by changing the sign of the first component of every codeword and switching the second with the third component.

M. Wild, Enumeration of binary and ternary matroids and other applications of the Brylawski-Lucas theorem, Technische Hochschule Darmstadt, Preprint 1693, 1994

Jayant Apte and J. M. Walsh, Constrained Linear Representability of Polymatroids and Algorithms for Computing Achievability Proofs in Network Coding, arXiv preprint arXiv:1605.04598 [cs.IT], 2016-2017.

Cf. A076766.

a(9) corrected by Gordon Royle, Oct 27 2007

cp's OEIS Frontend

A174743 Partial sums of A076766.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Sage

Formula

A227960 Big equivalence classes (A227723) related to subgroups of nimber addition (A190939).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A250002 Triangle read by rows: T(n,k) = number of inequivalent binary linear [n,k] codes minus C(n,k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A227962 Triangle of permutations that assign sona-becs (A227960) to their complements.

Views

Author

Keywords

Comments

Examples

Links

A250003 Number of inequivalent binary linear codes of length n minus 2^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A076892 Number of inequivalent ternary linear codes of length n. Also the number of nonisomorphic ternary matroids on an n-set.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A348102 a(n) is the number of vector subspaces in (F_3)^n, counted up to coordinate permutation.

Views

Author

Keywords

Crossrefs