login
Number of binary codes (not necessarily linear) of length n with 3 words.
7

%I #75 Feb 28 2024 01:06:33

%S 0,1,3,6,10,16,23,32,43,56,71,89,109,132,158,187,219,255,294,337,384,

%T 435,490,550,614,683,757,836,920,1010,1105,1206,1313,1426,1545,1671,

%U 1803,1942,2088,2241,2401,2569,2744,2927,3118,3317,3524,3740

%N Number of binary codes (not necessarily linear) of length n with 3 words.

%C Number of distinct triangles on vertices of n-dimensional cube.

%C Also, a(n) is the number of orbits of C_2^2 subgroups of C_2^n under automorphisms of C_2^n.

%C Also, a(n) is the number of faithful representations of C_2^2 of dimension n up to equivalence by automorphisms of (C_2^2).

%C Also, a([n/2]) is equal to the number of partitions mu such that there exists a C_2^2 subgroup G of S_n such that the i^th largest (nontrivial) product of 2-cycles in G consists of mu_i 2-cycles (see below example). - _John M. Campbell_, Jan 22 2016

%H John Campbell, <a href="https://doi.org/10.23638/DMTCS-19-1-8">A class of symmetric difference-closed sets related to commuting involutions</a>, Discrete Mathematics & Theoretical Computer Science, Vol 19 no. 1, 2017.

%H J. Brandts and C. Cihangir, <a href="http://www.math.cas.cz/~am2013/proceedings/contributions/brandts.pdf">Counting triangles that share their vertices with the unit n-cube</a>, in Conference Applications of Mathematics 2013 in honor of the 70th birthday of Karel Segeth. Jan Brandts, Sergey Korotov, et al., eds., Institute of Mathematics AS CR, Prague 2013.

%H Jan Brandts and A. Cihangir, <a href="http://arxiv.org/abs/1512.03044">Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group</a>, arXiv preprint arXiv:1512.03044 [math.CO], 2015.

%H H. Fripertinger, <a href="http://www.mathe2.uni-bayreuth.de/frib/codes/tables.html">Isometry Classes of Codes</a>

%H H. Fripertinger, <a href="http://dx.doi.org/10.1023/A:1008248618779">Enumeration, construction and random generation of block codes</a>, Designs, Codes, Crypt., 14 (1998), 213-219.

%H Petr Lisonek, <a href="http://dx.doi.org/10.1016/j.jcta.2006.06.013">Combinatorial families enumerated by quasi-polynomials</a>, Journal of Combinatorial Theory, Series A, Volume 114, Issue 4, May 2007, Pages 619-630.

%H Thomas Wieder, <a href="http://www.math.nthu.edu.tw/~amen/2008/070301.pdf">The number of certain k-combinations of an n-set</a>, Applied Mathematics Electronic Notes, vol. 8 (2008).

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,-1,0,2,-1).

%F a(n) = floor(n*(2*n^2 + 21*n - 6)/72).

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

%F a(1) = 0, a(2) = 1, a(3) = 3, a(4) = 6, a(5) = 10, a(6) = 16, a(7) = 23, and a(n) = 2*a(n-1) - a(n-3) - a(n-4) + 2*a(n-6) - a(n-7) for n >= 8. [_Harvey P. Dale_, Dec 25 2011]

%F From _Irena Swanson_, Feb 11 2024: (Start)

%F The roots of the characteristic polynomial corresponding to the above recurrence are 1, 1, 1, 1, -1, -1/2 - sqrt(-3)/2 and -1/2 + sqrt(-3)/2. The corresponding closed form is:

%F a(n) = -25/144 - n/12 + 7n^2/24 + n^3/36 + (-1)^n/16 + (1/18 + sqrt(-3)/54)(-1/2 - sqrt(-3)/2)^n + (1/18 - sqrt(-3)/54)(-1/2 + sqrt(-3)/2)^n for n >= 1. (End)

%e Let t denote the trivial representation and u_1, u_2, u_3 the three nontrivial irreducible representations of C_2^2 (so the u_i are all equivalent up to automorphisms of C_2^2). Then the a(4) = 6 faithful representations of dimension 4 are:

%e 2t+u_1+u_2; t+2u_1+u_2; t+u_1+u_2+u_3;

%e 3u_1+u_2; 2u_1+2u_2; 2u_1+u_2+u_3.

%e From _John M. Campbell_, Jan 22 2016: (Start)

%e Letting n=8, there are a([n/2])=a(4)=6 partitions mu such that there exists a Klein four-subgroup G of S_n such that the i^th largest (nontrivial) product of 2-cycles in G consists of mu_i 2-cycles, as indicated below:

%e {2, 1, 1} <-> {(12)(34), (12), (34), id}

%e {3, 2, 1} <-> {(12)(34)(56), (34)(56), (12), id}

%e {2, 2, 2} <-> {(12)(34), (34)(56), (56)(12), id}

%e {4, 3, 1} <-> {(12)(34)(56)(78), (34)(56)(78), (12), id}

%e {4, 2, 2} <-> {(12)(34)(56)(78), (56)(78), (12)(34), id}

%e {3, 3, 2} <-> {(12)(34)(56), (34)(56)(78), (12)(78), id}

%e (End)

%p A034198 := n -> iquo(n*(2*n^2+21*n-6), 72):

%p seq(A034198(n), n=1..100); # _Wesley Ivan Hurt_, Oct 29 2013

%t Table[Floor[n (2n^2+21*n-6)/72],{n,50}] (* _Harvey P. Dale_, Dec 25 2011 *)

%t LinearRecurrence[ {2,0,-1,-1,0,2,-1},{0,1,3,6,10,16,23},50] (* _Harvey P. Dale_, Dec 25 2011 *)

%o (Magma) [Floor(n*(2*n^2+21*n-6)/72): n in [1..50]]; // _Vincenzo Librandi_, Sep 18 2016

%Y Cf. A034188.

%Y Column k=2 of both A034356 and A076831 (which are the same except for column k=0).

%K nonn

%O 1,3

%A _N. J. A. Sloane_.

%E Additional comments from _Max Alekseyev_, Jul 09 2006

%E Additional comments from _Andrew Rupinski_, Jan 20 2010