cp's OEIS Frontend

A232636 The second largest value of permanent of (0,1) square matrices of order n with row and column sums equal to 3.

%I A232636 #37 Sep 09 2019 10:25:42
%S A232636 34012224,53747712,131010048,204073344,322486272,786060288,1224440064,
%T A232636 1934917632,4716361728,7346640384,11609505792,28298170368,44079842304,
%U A232636 69657034752,169789022208,264479053824,417942208512
%N A232636 The second largest value of permanent of (0,1) square matrices of order n with row and column sums equal to 3.
%C A232636 The interval (a(n), A232553(n)) contains no permanents of the matrices under consideration. For n=3 and n=4, the permanent takes only one value: 6 and 9 respectively. Our method (see Shevelev link) allows us to find a simple regularity of the sequence only beginning with n=30 (see formula). However, several values for 5<=n<30 are known: a(5)=13, a(6)=20, a(7)=32, a(8)=78, a(9)=120, a(12)=729, a(15)=4374, a(18)=26244, a(21)=157464, a(24)=944784, a(27)=5668704 (Bolshakov) and a(28)=8957952.
%C A232636 We conjecture that formula below also holds for other values.
%C A232636 In cases n==0 (nod 3), n>=6, and n==2 (mod 3), at least, for n=8 and n>=32, the second largest value of permanent attains on subset of symmetric matrices with the main diagonal of 1's, and does not attain, if n==1 (mod 3), at least, for n=7 and n>=28.
%C A232636 All terms for n>30 not divisible by 3 are conjectural since our method is based on the following very plausible but yet not proved conjecture with confirms in many cases and without counterexample since 1992 (when it was posed, see ref. [11] in Shevelev link). Let L_n be the set of considered n X n (0,1)-matrices with all row and column sums equal to 3. Let S_n be the subset of completely indecomposable such matrices, i.e., not containing submatrices from L_m (m<n). Let M(n) be the maximal value of permanent on S_n. Then M(n_1+n_2) <= M(n_1)*M(n_2). V. I. Bolshakov proved the result for n divisible by 3, using quite different arguments which, generally speaking, do not work for other n and for third, fourth, etc. largest values of permanent, where our (yet conditional) method does work successfully, at least for sufficiently large n.
%D A232636 V. I. Bolshakov, On spectrum of permanent on Lambda_n^k, Proc. of Seminar on Discrete Math. and Appl., Moscow State Univ. (1986), 65-73 (in Russian).
%H A232636 V. Shevelev, <a href="http://dx.doi.org/10.1155/2013/289829">Spectrum of permanent's values and its extremal magnitudes in Lambda_n,3 and Lambda_n(alpha,beta,gamma)</a>, Journal of Optimization, Vol. 2013(2013), Article 289829.
%F A232636 a(n) = 9/16 * 6^(n/3), if n>=12, n==0 (mod 3) (Bolshakov); a(n) = 8/9 * 6^((n-1)/3), if n>=28, n== 1 (mod 3); a(n) = 13/6 * 6^((n-2)/3), if n>=32, n==2 (mod 3).
%F A232636 Conjectures from _Colin Barker_, May 27 2016: (Start)
%F A232636 a(n) = 6*a(n-3) for n>32.
%F A232636 G.f.: 419904*x^30*(81+128*x+312*x^2) / (1-6*x^3).
%F A232636 (End)
%Y A232636 Cf. A232553, A176211, A176212, A185177, A185178, A185179.
%K A232636 nonn
%O A232636 30,1
%A A232636 _Vladimir Shevelev_, Nov 27 2013
%E A232636 Edited by _M. F. Hasler_, Nov 30 2013