A131709

[koh]

----- Original Message ----- 
From: "Max Alekseyev" <maxale at gmail.com>
To: "koh" <zbi74583 at boat.zero.ad.jp>
Cc: <seqfan at ext.jussieu.fr>; "Neil J. A. Sloane" <njas at research.att.com>
Sent: Tuesday, October 30, 2007 8:31 AM
Subject: Re: A131709


> On 10/28/07, koh <zbi74583 at boat.zero.ad.jp> wrote:
> 
>>   I got the following formula.
>>
>>   a(n) = Product_{v_i} m_i
>>        + Sum_{c_j} (se_j - 1)*Product_{v_k E (G_n-c_j)} m_k
>>         where :
>>               v_i E V_n, G_n={V_n,E_n}, "E" means element
>>               m_i means number of matching of incident edges of v_i
>>               c_j means cycles in G_n
>>               se_j means number of start-end points in c_j
>>               v_k E G_n and not(v_k E c_j)
>>               m_k means number of matching of incident edges of v_k
> 
> I almost agree with your formula, except that the inner Product must
> be equal 0 in some cases (when there is no way to cut the cycle, i.e.,
> G_n-c_j is empty). There will be a discrepancy as the empty product is
> defined as 1.
> 
    You are right.

>> > I've got the following general formula:
>> >
>> > For n>=2, S(n) = 3^(2*(n-1)) + 3^(n-1) + 2 + (3^n + 27 - 18*n)/4
>> >
>> > S : 1, 4, 14, 92, 767, 6689, 59456, 532694, 4786769, 43058171,
>> > 387454898, 3486887696, 31381369571, 282430466453, 2541868618340
> 
>>     The terms for n=3,4 are different.
>>
>>     Which are correct?
> 
> I think neither one. See below.
> 
>>     My early result by hand for n=3 is the following.
>>     I might have lost some, because it is also different from 106.
>>
>>
>>     I list all partitions with their figures.
>>
>>          ._._._.
>>          |_|_|_|
>>
>>
>>          ._._._.
>>          |_._|_| +   |            12
>>          ._._._.
>>          |_._._| +   | |          4
> 
> These cases are unclear. For example, the top one of the two above may
> contain the bottom one as a particular case.
> 
    Sorry, I should have written more explanation about figures.
    I sorted the partitions using length of paths.
    The top is the case for {9}+{1}, and the bottom is for {8}+{1}+{1}

    After all, it was a past work.
    I meant that 98<=a(3) 

> I suggest to count, starting with the cycle configuration (i.e., what
> we have after the first step in my description of the partition
> process):
> 
> 1) One 8-cycle:
> ._._._.
> |_._._|
> 
> There is an unique way to get this cycle and 4 ways to "cut" it (at
> the corner vertices) into a circular path.
> So, there 1*4=4 partitions here.
> 
> 2) One 6-cycle:
> ._._.
> |_._|
> There are 2 ways to obtain such a cycle (either at left or at right of
> the original graph) and 2 ways to cut it into a path.
> So, there 2*2=4 partitions here.
> 
> 3) One 4-cycle:
> ._.
> |_|
> There are 2*(3*3-1)=16 ways to obtain such a cycle (either at the left
> or at the right end, but not at the middle - such a cycle cannot be
> cut into a path), and there are 2 ways to cut it into a path.
> So, there 16*2=32 partitions here.
> 
    
> 4) Two 4-cycles:
> ._. _.
> |_| |_|
> There is an unique way to get such cycles and 2*2=4 ways to cut them into paths.
> So, there 4 partitions here.
> 
> 5) No cycles.
> There are 3^4 - 2*3^2 - 2*1 - 1 + 1 = 61 (also, can be counted as     -
> 2*(3^2-1)^2 - 3 = 61) partitions here .
> 
    I think that the equation is 3^4  - 1 - 2 - 16 - 1 = 61 

    And your result for no cycle still conteins the "impossible case" which you wrote four lines after.

> The total number of partitions (i.e., a(4) in A131709) is
> 4 + 4 + 32 + 4 + 61 = 105
> 
    I think that the last term is 60 , so it bedcomes 104.

> This result is close to your result of 106 where you counted the
> impossible case:
> ._    ._.  _.
> |_    |_|   _|
> 
> In this case we cannot cut the inner cycle into a path. Therefore, it
> does not deliver any partitions.
> 
    My result corresponded with your classification is as follows.
    a(3) = 3^4 + 2*(3^2-1) - 1 + 2+ 3 + 3        
           = {5)+21} + {3)-16} - {I} + {2)-2} + {4)-1} +  {1)-1}
    Where,"I" means the " impossible case".
    I didn't counted it.

    I have awoke that I counted twice the case of  two 4-cycle.
    So, the second term must be 2*(3^2-1)  = 16 
    Hence a(3) = 104

    Both results are the same.

> Neil, please do not make any corrections to A131709 until we agree
> with Yasutoshi on this sequence. In particular, the latest correction
> of a(4) turned it into non-sense. Please roll that correction
> (together with the illustration) back to at least follow the formula
> specified in the name of A131709.
> 
> Regards,
> Max
>
    I wrote : 
        ._._._._.   n=4
　　　　|_|_|_|_|

    a(4)
    = 3^6 + 2*3^4 - 2*3^2 + 2*3^2 - 1 + 2*1 + 3*3^2 + 2*1 + 2*3 + 3         
    = 729 + 162 + 1 + 27 + 11
    = 930

    It is not correct.
    I counted the cycles twice in 2nd and 3rd and 4th term and mistook the sign of 6th term. 

    The total number is the following.
    = 3^6 + 2*(3^4-2) - 2*(3^2-1) + 2*(3^2-1)  - 1 -2*1 + 3*3^2 + 2*1 + 2*3 + 3
    = 922

    Corresponding cycles : 
        nc      14c              14c              16c            16c  24c    24c         18c     16c+14c   1.10c 
        where "nc" means No cycle , "14c" means One 4 cyclth.



    Yasutoshi
          I 



Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
:Here is a seemingly dumb question.
:
:Is sequence A134320 finite?
:
:Here is the info on this sequence, for those too lazy
:to check the EIS:
:
:%I A134320
:%S A134320 2,4,6,12,20,30,42,90
:%N A134320 Positive integers with more non-isolated
:divisors than isolated divisors. A divisor, k, of n is
:non-isolated if (k-1) and/or (k+1) also divides n. A
:divisor, k, of n is isolated if neither (k-1) nor
:(k+1) divides n.
:%C A134320 Is this sequence finite?
:
:With the exception of a(2) = 4, all terms of this
:sequence are of the form m*(m+1). (Oblong numbers:
:A002378)
:%e A134320 The divisors of 42 are 1,2,3,6,7,14,21,42.
:Of these, 1,2,3,6,7 are non-isolated divisors, and
:14,21,42 are isolated divisors. There are more
:non-isolated divisors (5 in number) than isolated
:divisors (3 in number), so 42 is in the sequence.
:%Y A134320 A134321,A134322
:%O A134320 1
:%K A134320 ,more,nonn,

The sequence is finite and complete.

Proof:

If a and b are coprime divisors of n, then ab is also a divisor of n.

Hence if a > sqrt(n) is a divisor of n, then a+1 is not a divisor of n.

If n = m^2 is a perfect square with 2k+1 divisors, then k of those
divisors are greater than m, and each of these is isolated. So to be in the
particular that m is non-isolated, so m-1 must be a divisor, and so
(m-1).m^2 is a divisor, so m-1 = 1. So the only perfect square in the

If n is neither square nor oblong, then it has 2k divisors, k of which
are greater than sqrt(n) and hence isolated. So no such n can be in the

If n = m(m+1) is an oblong number, then it has 2k divisors, k-1 of which
are greater than m+1, each of which is isolated. So all the remaining
divisors must be non-isolated.

One of m and m+1 is even: call it 'a', and call the other b. Now a/2 is
a divisor, and most be non-isolated, so it must be adjacent to a divisor
of n; that divisor is coprime to a/2, so it must divide 2b.

By definition b is odd, so 2b is not divisible by 4. The next two steps

If it is 2b/3, this is minimised when a = m+1, b = m. Now when m > 9
we have 2b/3 - a/2 >= 2m/3 - (m+1)/2 > 1. So 2b/3 is too large to be
adjacent to a/2 when m > 9.

If it is 2b/5, this is maximised when a = m, b = m+1. Now when m > 14
we have a/2 - 2b/5 >= m/2 - 2(m+1)/5 > 1. So 2b/5 is too small to be
adjacent to a/2 when m > 14.

So the only possible elements of the sequence are the square 4, and the
oblong numbers m(m+1) for m <= 14. These can be checked individually to

Hugo