A003319
Gottfried Helms
Annette.Warlich at t-online.de
Sun Aug 14 22:44:59 CEST 2005
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