[seqfan] Re: Guess the Triangle

[Rob Pratt]

Well, idempotent implies that the eigenvalues are 0 and 1, with 0 and 1 on main diagonal, and trace = rank.  So the main diagonal consists of n - 1 ones and 1 zero.  There are n choices for the position of this zero.  If the matrix is upper triangular, the only nonzero elements appear in the column corresponding to the 0 diagonal element, and these n - 1 elements can be arbitrary.  This yields n(k+1)^(n-1) upper triangular matrices.  Similar argument yields the same number of lower triangular matrices.  But the n diagonal matrices have been counted twice, so subtract n.  It remains to show that such matrices must be triangular so that these are the only possibilities.

On Mar 29, 2013, at 9:27 AM, "Ron Hardin" <rhhardin at att.net> wrote:

> Oh and of course that's equal to something simpler: apparently
> 
> T(n,k)=2*n*(1+k)^(n-1)-n
> 
> Should the formula be obvious somehow?
> 
> rhhardin at mindspring.com
> rhhardin at att.net (either)
> 
> 
> 
> ----- Original Message ----
>> From: Ron Hardin <rhhardin at att.net>
>> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>> Sent: Fri, March 29, 2013 9:09:41 AM
>> Subject: [seqfan] Re: Guess the Triangle
>> 
>> Great (thanks also to Maximilian Hasler)
>> 
>> Then empirical: T(n,k) =  2*n*sum{ binomial(n-1,i)*k^(n-1-i), i=0..(n-1) } - n
>> 
>> matches all my data  so far (which doesn't extend very far into k for big n, 
>> e.g. 
>> 
>> n=7,k=5;  n=8,k=1).
>> 
>> I wonder if more available factorizations of a large k would  turn up affecting 
>> 
>> the empirical formula.
>> 
>> 
>> 
>> rhhardin at mindspring.com
>> rhhardin at att.net (either)
>> 
>> 
>> 
>> ----- Original Message ----
>>> From: William Keith  <william.keith at gmail.com>
>>> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
>>> Sent:  Fri, March 29, 2013 5:07:04 AM
>>> Subject: [seqfan] Re: Guess the  Triangle
>>> 
>>>> T(n,k)=Number of idempotent nXn 0..k matrices of  rank n-1
>>>> 
>>>> Rows n=1..6 match
>>>> a(k) =  1
>>>> a(k) = 4*k + 2
>>>> a(k) = 6*k^2 +  12*k + 3
>>>> a(k) = 8*k^3 + 24*k^2 + 24*k + 4
>>>> a(k) = 10*k^4 + 40*k^3   + 60*k^2 + 40*k + 5
>>>> a(k) = 12*k^5 + 60*k^4 + 120*k^3 + 120*k^2 +  60*k +  6
>>> 
>>> Pascal's triangle times 2n, except for the last  coefficient, which  is
>>> just times n.
>>> 
>>> William   Keith
>>> 
>>> _______________________________________________
>>> 
>>> Seqfan  Mailing list - http://list.seqfan.eu/
>> 
>> _______________________________________________
>> 
>> Seqfan Mailing  list - http://list.seqfan.eu/
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
>