A003319
Roland Bacher
Roland.Bacher at ujf-grenoble.fr
Mon Aug 15 10:41:10 CEST 2005
As already remarked by P Hanna, inferior triangular matrices of
Toeplitz-type (whose coefficients X_{i,j} depend only on the
distance i-j to the diagonal) form an algebra which is isomorphic
to the algebra of formal power series (Send such a matrix
X_{i,j}, 0\leq i,j to the series \sum_{n\geq 0} X_{n,0} z^n)
This implies that the matrix logarithm corresponds to (the
matrix) of the ordinary logarithm of the corresponding
power series.
The remark below that the coefficients of the matrix logarithm
are interesting is then the well-known fact of a combinatorial
interpretation of the logarithm: Given a power-series g which counts
the number of objects "having several connected components"
(weighted by natural integers), the logarithm
log(g) counts the the corresponding number of connected objects.
(Roughly stated, look at a book on combinatorial enumeration,
e.g. Stanley or Wilf for the precise statement and details).
Best whishes, Roland Bacher
On Sun, Aug 14, 2005 at 10:44:59PM +0200, Gottfried Helms wrote:
> Friends -
>
> just fiddled around with the matrix logarithm again, which was
> already useful in a sequence contributed by Paul D Hanna.
>
> The Hanna-matrix was a shifting matrix under multiplication;
> M*M gives a new version of M, where the columns/rows are
> shifted by one index. This matrix was generated by some
> partitioning of powers of 2.
> (details see Seq A078121, I'm citing this at the bottom of this post).
>
>
> The matrix-logarithm of that matrix showed an interesting
> pattern and provided a sequence which is connected to the factorials.
>
> Just playing around a bit I created the following matrix, containing
> factorials, since they played a significant role as denominators...
> disp :
> | 1 0 0 0 0 0 0 0 0 0 0 |
> | 1 1 0 0 0 0 0 0 0 0 0 |
> | 2 1 1 0 0 0 0 0 0 0 0 |
> | 6 2 1 1 0 0 0 0 0 0 0 |
> | 24 6 2 1 1 0 0 0 0 0 0 |
> | 120 24 6 2 1 1 0 0 0 0 0 |
> | 720 120 24 6 2 1 1 0 0 0 0 |
> | 5040 720 120 24 6 2 1 1 0 0 0 |
> | 40320 5040 720 120 24 6 2 1 1 0 0 |
> | 362880 40320 5040 720 120 24 6 2 1 1 0 |
> | 3628800 362880 40320 5040 720 120 24 6 2 1 1 |
>
> The matrix-logarithm of that matrix is
>
> disp :
> | 0 0 0 0 0 0 0 0 0 0 0 |
> | 1 0 0 0 0 0 0 0 0 0 0 |
> | 1.5 1 0 0 0 0 0 0 0 0 0 |
> | 4.333333 1.5 1 0 0 0 0 0 0 0 0 |
> | 17.75 4.333333 1.5 1 0 0 0 0 0 0 0 |
> | 92.2 17.75 4.333333 1.5 1 0 0 0 0 0 0 |
> | 574.5 92.2 17.75 4.333333 1.5 1 0 0 0 0 0 |
> | 4156.142 574.5 92.2 17.75 4.333333 1.5 1 0 0 0 0 |
> | 34167.87 4156.142 574.5 92.2 17.75 4.333333 1.5 1 0 0 0 |
> | 314369.4 34167.87 4156.142 574.5 92.2 17.75 4.333333 1.5 1 0 0 |
> | 3199890. 314369.4 34167.87 4156.142 574.5 92.2 17.75 4.333333 1.5 1 0 |
>
> which has only 1 significant column similar as in Paul's problem.
> Taking only the first column gives that sequence:
>
> | 0 1 1.5 4.333333 17.75 92.2 574.5 4156.142 34167.87 314369.4 3199890. |
>
> Multiply each entry of that sequence by its index-1 gives the follwoing sequence:
>
> | 0 1 3 13 71 461 3447 29093 273343 2829325 31998903 |
>
> which is in the OEIS, and is connected to permutations:
> Cite:
> > D Number: A003319 (Formerly M2948)
> > URL: http://www.research.att.com/projects/OEIS?Anum=A003319
> > Sequence: 1,1,3,13,71,461,3447,29093,273343,2829325,31998903,
> > 392743957,5201061455,73943424413,1123596277863,
> > 18176728317413,311951144828863,5661698774848621,
> > 108355864447215063,2181096921557783605
> > Name: Number of connected permutations of [1..n] (those not fixing [1..j]
> > for 0<j<n). Also called indecomposable permutations.
> > Comments: Also the number of permutations with no global descents, as introduced
> > by Aguiar and Sottile [Corollaries 6.3, 6.4 and Remark 6.5]
> > Also the dimensions of the homogeneous components of the space of
> > primitive elements of the Malvenuto-Reutenauer Hopf algebra of
> > permutations. This result, due to Poirier and Reutenauer [Theoreme
> > 2.1] is stated in this form in the work of Aguiar and Sottile [Corollary
> > 6.3] and also in the work of Duchamp, Hivert and Thibon [Section 3.3]
> > Related to number of subgroups of index n-1 in free group of rank 2 (i.e.
> > maximal number of subgroups of index n-1 in any 2-generator group). See
> > Problem 5.13(b) in Stanley's Enumerative Combinatorics, Vol. 2.
> (...)
> > Links: I.M. Gessel and R.P. Stanley Chapter 21 of Handbook of Combinatorics (See pages 7-8 of this online-version for the generating function of these indecomposable permutations)
> > David Callan, Counting Stabilized-Interval-Free Permutations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8.
> > Formula: G.f.: 1-1/Sum (k! x^k ). Also a(n) = n! - Sum_{k=1..n-1} k!*a(n-k), n
> > >= 1.
> > a(n) = (-1)^{n-1} * det {| 1! 2! ... n! | 1 1! ... (n-1)! | 0 1 1! ... (n-2)! |
> > ... | 0 ... 0 1 1! |}
> > INVERTi transform of factorial numbers, A000142 starting from n=1. -
> > Antti Karttunen (Antti.Karttunen(AT)iki.fi), May 30 2003
> > Gives the row sums of the triangle [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] DELTA
> > [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] where DELTA is the operator defined
> > in A084938; this triangle,read by rows is the sequence : 1; 0, 1; 0, 1, 2;
> > 0, 1, 6, 6; 0, 1, 12, 34, 24; 0, 1, 20, 110, 210, 120; 0, 1, 30, 270, 974, 1452,
> > 720; ... - DELEHAM Philippe (kolotoko(AT)lagoon.nc), Dec 30 2003
> > Maple: INVERTi([seq(n!,n=1..20)]);
> > See also: Leading diagonal of A059438.
> > Cf. A051296, A084938, A074664.
> > Sequence in context: A059726 A024337 A001495 this_sequence A000261
> > A059032 A047159
> > Adjacent sequences: A003316 A003317 A003318 this_sequence A003320
> > A003321 A003322
>
>
> It seems, that this type of matrix-logarithms and factorials has something
> to do with partitions and permutations?
>
> Just wondering -
>
> Gottfried Helms
>
>
> > ID Number: A078121
> > URL: http://www.research.att.com/projects/OEIS?Anum=A078121
> > Sequence: 1,1,1,1,2,1,1,4,4,1,1,10,16,8,1,1,36,84,64,16,1,1,202,656,
> > 680,256,32,1,1,1828,8148,10816,5456,1024,64,1,1,27338,
> > 167568,274856,174336,43680,4096,128,1,1,692004,5866452,
> > 11622976,8909648,2794496,349504
> > Name: Infinite lower triangular matrix, M, that satisfies [M^2](i,j) =
> > M(i+1,j+1) for all i,j>=0 where [M^n](i,j) denotes the element at
> > row i, column j, of the n-th power of matrix M, with M(0,k)=1 and M(k,k)=1
> > for all k>=0.
> > Comments: M also satisfies: [M^(2k)](i,j) = [M^k](i+1,j+1) for all
> > i,j,k>=0; thus [M^(2^n)](i,j) = M(i+n,j+n) for all n>=0.
> > Formula: M(1,j)=A002577(j) (partitions of 2^j into powers of 2),
> > M(j+1,j)=2^j, M(j+2,j)=4^j, M(j+3,j)=A016131(j).
> > M(n,k) = the coefficient of x^(2^n - 2^(n-k)) in the power series
> > expansion of 1/Product_{j=0..n-k}(1-x^(2^j)) whenever
> > 0<=k<n for all n>0 (conjecture).
> > Example: The square of the matrix is the same matrix excluding the first row and
> > column:
> > [1,_0,_0,0,0]^2=[_1,_0,_0,_0,0]
> > [1,_1,_0,0,0]___[_2,_1,_0,_0,0]
> > [1,_2,_1,0,0]___[_4,_4,_1,_0,0]
> > [1,_4,_4,1,0]___[10,16,_8,_1,0]
> > [1,10,16,8,1]___[36,84,64,16,1]
> > See also: Cf. A078122, A002577, A016131.
> > Adjacent sequences: A078118 A078119 A078120 this_sequence A078122
> > A078123 A078124
> > Sequence in context: A064298 A099594 A034372 this_sequence A057785
> > A102610 A078047
> > Keywords: nonn,tabl
> > Offset: 0
> > Author(s): Paul D Hanna (pauldhanna(AT)juno.com), Nov 18 2002
>
>
>
More information about the SeqFan
mailing list