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$
    – მამუკა ჯიბლაძე
    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$
    – მამუკა ჯიბლაძე
    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$
    – მამუკა ჯიბლაძე
    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
    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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.