1
$\begingroup$

Sequence A002846 in https://oeis.org/A002846 (OEIS) gives, for each positive integer $n$, the number $a(n)$ of ways of transforming a set of $n$ indistinguishable objects into $n$ singletons via a sequence of $n-1$ refinements, i.e. the number of ways of transforming a set of $n$ unlabelled objects into $n$ singletons via a sequence of $n-1$ binary partitions.

For a given $n$, each sequence of refinements can be represented by an $n\times{}n$ triangular matrix. The $(i,j)^{th}$ element of the matrix represents the number of sets after $i-1$ partitions that contain $j$ elements. The sum of the $i^{th}$ row is simply the number of sets after $i-1$ partitions, so is clearly $=i$. I am interested in linear combinations of these $a(n)$ matrices. For convenience, suppose that the coefficients total to 1. Then obviously if a matrix $M$ is formed by such a linear combination, the sum of the $i^{th}$ row is still $i$. However, a number of trials have convinced me that if $M$ is non-singular, the sum of the $i^{th}$ row of $M^{-1}$ is $\frac{i}{n}.$

To allow you to easily experiment, a list of matrices for n=4 to 9 can be obtained at github.com/helmutsimon/coalescent_tree_data . The file matrix_list_9 etc can be downloaded and then opened with pickle and gzip. The file then contains a python list of matrices represented as numpy arrays. At present, I have no idea how to go about proving this conjecture.

The following are the 4 matrices for n=5:

[[ 0. 0. 0. 0. 1.]
[ 1. 0. 0. 1. 0.]
[ 2. 0. 1. 0. 0.]
[ 3. 1. 0. 0. 0.]
[ 5. 0. 0. 0. 0.]

[[ 0. 0. 0. 0. 1.]
[ 1. 0. 0. 1. 0.]
[ 1. 2. 0. 0. 0.]
[ 3. 1. 0. 0. 0.]
[ 5. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 1.]
[ 0. 1. 1. 0. 0.]
[ 2. 0. 1. 0. 0.]
[ 3. 1. 0. 0. 0.]
[ 5. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 1.]
[ 0. 1. 1. 0. 0.]
[ 1. 2. 0. 0. 0.]
[ 3. 1. 0. 0. 0.]
[ 5. 0. 0. 0. 0.]]

The following are the 11 matrices for n=6:

[[ 0. 0. 0. 0. 0. 1.]
[ 1. 0. 0. 0. 1. 0.]
[ 2. 0. 0. 1. 0. 0.]
[ 3. 0. 1. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 1. 0. 0. 0. 1. 0.]
[ 2. 0. 0. 1. 0. 0.]
[ 2. 2. 0. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 1. 0. 0. 0. 1. 0.]
[ 1. 1. 1. 0. 0. 0.]
[ 3. 0. 1. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 1. 0. 0. 0. 1. 0.]
[ 1. 1. 1. 0. 0. 0.]
[ 2. 2. 0. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 0. 1. 0. 1. 0. 0.]
[ 2. 0. 0. 1. 0. 0.]
[ 3. 0. 1. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 0. 1. 0. 1. 0. 0.]
[ 2. 0. 0. 1. 0. 0.]
[ 2. 2. 0. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 0. 1. 0. 1. 0. 0.]
[ 1. 1. 1. 0. 0. 0.]
[ 3. 0. 1. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 0. 1. 0. 1. 0. 0.]
[ 1. 1. 1. 0. 0. 0.]
[ 2. 2. 0. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 0. 1. 0. 1. 0. 0.]
[ 0. 3. 0. 0. 0. 0.]
[ 2. 2. 0. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 0. 0. 2. 0. 0. 0.]
[ 1. 1. 1. 0. 0. 0.]
[ 2. 2. 0. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

[[ 0. 0. 0. 0. 0. 1.]
[ 0. 0. 2. 0. 0. 0.]
[ 1. 1. 1. 0. 0. 0.]
[ 3. 0. 1. 0. 0. 0.]
[ 4. 1. 0. 0. 0. 0.]
[ 6. 0. 0. 0. 0. 0.]]

Improve this question
$\endgroup$
13
  • $\begingroup$ What if I am not a python expert? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jul 19, 2017 at 10:19
  • 1
    $\begingroup$ @HughThomas I figured it out actually. Matrices are $n\times n$ lower triangular if by "$i$th row" one understands the $(n+1-i)$th row, i. e. refinements go from down to up. Example: $5\to41\to311\to2111\to11111$; \begin{align*}&\text{the $1$st row corresponding to $11111$ is $50000$,}\\&\text{the $2$nd row corresponding to $2111$ is $31000$;}\\&\text{the $3$rd row corresponding to $311$ is $20100$;}\\&\text{the $4$th row corresponding to $41$ is $10010$;}\\&\text{the $5$th (last) row corresponding to $5$ is $00001$.} \end{align*} $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jul 19, 2017 at 12:00
  • 1
    $\begingroup$ Thus e. g. the $n$th (last) row is always $000\cdots01$, the first row is always $n00\cdots00$, and the second row is always $(n-2)10\cdots00$. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Jul 19, 2017 at 12:04
  • 1
    $\begingroup$ Of the 15 matrices given, 13 have an all-zero column (and thus are singular). $\endgroup$
    – Gerry Myerson
    Commented Jul 19, 2017 at 22:32
  • 2
    $\begingroup$ @Gerry Myerson. True. But linear combinations of the matrices are generally non-singular (in fact with probability 1 if the coefficients are selected randomly). $\endgroup$
    – Helmut
    Commented Jul 19, 2017 at 23:35

1 Answer 1

Reset to default
4
$\begingroup$

Actually, this turned out to be embarrassingly simple. Let $M$ be such an $n\times{}n$ matrix and set $\mathbf{i}_n$ to be the column matrix with entries 1 to $n$ and $\mathbf{1}_n$ to be the column matrix with entries all equal to 1. By construction, each row of the matrix represents a partition of $n$. The first element of the row is the number of partitions of block size 1, the second element is the number of partitions of block size 2 and so on. So $$M.\mathbf{i}_n=n\mathbf{1}_n$$ So if $M^{-1}$ exists: $$M^{-1}.M.\mathbf{i}_n=M^{-1}.n\mathbf{1}_n$$ $$M^{-1}\mathbf{1}_n=\frac{\mathbf{i}_n}{n}$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .