[Fwd; COMB-L: Re: One last problem]

[Olivier Gerard]

Dear Seqfans,

Our list member Edwin Clark used the OEIS today to answer
probably the last thread of the mailing list COMB-L
which is closing soon by decision of his moderator.

Here is his post together with the original question.

Olivier


----- Forwarded message from Edwin Clark <eclark at MATH.USF.EDU> -----

Reply-To: Combinatorial Mathematics <COMB-L at LISTSERV.CMICH.EDU>
From: Edwin Clark <eclark at MATH.USF.EDU>
Subject:      Re: One last problem
To: COMB-L at LISTSERV.CMICH.EDU
X-Antivirus: scanned by sophie at shiva.jussieu.fr

I calculated the sequence A(2,n) for n from 1 to 7 obtaining

      1, 4, 12, 32, 80, 192, 448

As far as it goes this matches sequence A001787 from Sloane's EIS:
After seeing the formula n*2^(n-1) it becomes clear that it is the
correct value for A(2,n). From your conditions one column has two 1's and
the other n-1 columns each have exactly one 1 and one 0. There are n
ways to choose the column with two 1's and 2^(n-1) ways to choose the
other columns.

Using the EIS is much easier than thinking. :-)

Perhaps the reference below to "overflow at traffic lights" is related to
your original transportation problem?

I haven't tried to calculate the sequence for n=3 three yet -- it will
take a little more time.

--Edwin Clark


PS Here's the entry from the EIS:



ID Number: A001787 (Formerly M3444 and N1398)
Sequence:  0,1,4,12,32,80,192,448,1024,2304,5120,11264,24576,53248,
           114688,245760,524288,1114112,2359296,4980736,10485760,
           22020096,46137344,96468992,201326592,419430400,872415232,
           1811939328,3758096384,7784628224
Name:      n*2^(n-1).
Comments:  Number of edges in n-dimensional hypercube.
           Binomial trnsform of [0,1,2,3,4,5,...]. Without the initial 0,
              binomial transform of odd numbers.
           Number of 132-avoiding permutations of [n+2] containing exactly
one
              123 pattern. - Emeric Deutsch (deutsch(AT)duke.poly.edu),
Jul 13
              2001
           Ways to place n-1 nonattacking kings on a 2 x 2(n-1) chessboard
for n
              >= 2 - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com),
May
              22 2001
           Arithmetic derivative of 2^n: a(n) = A003415(A000079(n)). -
Reinhard

[Here was the remaining of entry A001787 - I cut this , OG]

On Sat, 24 May 2003, Dr. Robert O. Stanton wrote:

> Dear Colleagues,
>
> Before Ken shuts this list down, I thought I would pose a problem that
> plagued me years ago until I gave up in frustration. The problem is related
> to degeneracy in transportation problems.
>
> For positive integers  m  and  n, consider an  m x n matrix  M  satisfying
> the following four properties:
>
> 1. The entries of  M are either 0 or 1.
>
> 2. Each row, and each column of M has at least one 1.
>
> 3. The total number of  1's  is  m + n - 1.
>
> Form a graph as follows: The vertices are the entries of  M  that contain a
> 1. Two vertices are joined by an edge provided that they are either in the
> same row or the same column.
>
> 4. The graph of  M  is connected.
>
> A  3 x 3  matrix whose  (m,n) entry is  1   exactly if  m + n  is even
> satisfies the first three conditions, but not the fourth.
>
> Let  A(m,n)  be the number of such  m x n  matrices  M. Clearly  A(1,n) =
> 1  and it is easy to see that  A(2,2) = 4.
>
> My question: Is there a general formula for  A(m,n)?
> Dr. Robert O. Stanton
> Mathematics and Computer Science
> St. John's University
> Jamaica, NY 11439
>


----- End forwarded message -----