Timeline for Counting matrices of special types
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 24, 2019 at 15:37 | comment | added | Max Alekseyev | @IraGessel: Yes, I've got confused by the complexity of the Gessel-Li paper. The formula is indeed a simple modification of what I posted here. | |
| Feb 24, 2019 at 15:07 | comment | added | Ira Gessel | @MaxAlekseyev: No, zeroing the diagonal doesn't make much difference. It just changes the $2^{i(i+1)/2}$ in $\sum_{i=0}^n s(n,i) 2^{i(i+1)/2}$ to $2^{i(i-1)/2}$. | |
| Feb 24, 2019 at 14:05 | comment | added | Max Alekseyev | @IraGessel: Thanks for the pointer. It's interesting to see that "zeroing" the diagonal makes the problem much harder (apparently). | |
| Feb 23, 2019 at 19:48 | comment | added | Ira Gessel | A closely related problem is that of counting graphs in which no two vertices have the same neighborhood. This corresponds to symmetric 0-1 matrices with 0s on the diagonal. These graphs are called point-determining or mating graphs. You can find links to their enumeration (both labeled and unlabeled) at oeis.org/A006024. | |
| Jul 5, 2015 at 11:44 | comment | added | Max Alekseyev | @Turbo: No, I do not take permutations of rows/columns into accout. | |
| Jul 5, 2015 at 3:19 | comment | added | Turbo | Count is modulo row/column permutations right? | |
| Jul 5, 2015 at 3:19 | vote | accept | Turbo | ||
| Jul 5, 2015 at 3:19 | vote | accept | Turbo | ||
| Jul 5, 2015 at 3:19 | |||||
| Jul 5, 2015 at 0:46 | comment | added | Max Alekseyev | @Turbo: I've addressed the symmetric case in the update. | |
| Jul 5, 2015 at 0:44 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
added symmetric case
|
| Jun 30, 2015 at 7:52 | comment | added | Richard Stanley | @MaxAlekseyev I meant that you apply $(1,2)$ to both the rows and the columns. I see that you meant something else. | |
| Jun 30, 2015 at 5:20 | comment | added | Max Alekseyev | @RichardStanley: I do not quite follow your argument. Matrix $\begin{pmatrix} a&b\\c&d\end{pmatrix}$ is invariant w.r.t. $\pi=(1,2)$ iff $a=c$ and $b=d$; and it is invariant w.r.t. $\sigma=(1,2)$ iff $a=b$ and $c=d$. So it is invariant w.r.t. both $\pi$ and $\sigma$ iff $a=b=c=d$. There are $k^1=2$ such matrices. | |
| Jun 30, 2015 at 1:22 | comment | added | Richard Stanley | @MaxAlekseyev I don't think that your assertion about $k^{i\cdot j}$ is true. Let $k=2$, $\pi=\sigma=(1,2)$. Then the number of matrices invariant with respect to $\pi$ and $\sigma$ is four, not two. | |
| Jun 29, 2015 at 14:39 | comment | added | Max Alekseyev | If one fix a permutation of rows $\pi$ and a permutation of columns $\sigma$, then the number of matrices invariant w.r.t. $\pi$ and $\sigma$ equals $k^{i\cdot j}$, where $i$ and $j$ are the number of cycles in $\pi$ and $\sigma$, respectively. | |
| Jun 29, 2015 at 14:20 | comment | added | Turbo | ok is there 'main idea(s)' for the formula? | |
| Jun 29, 2015 at 14:15 | comment | added | Max Alekseyev | Inclusion-exclusion but it's rather lenthty to post the proof here. I'll look at the symmetric case later. | |
| Jun 29, 2015 at 14:13 | comment | added | Turbo | How do you get the count? | |
| Jun 29, 2015 at 14:10 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
added 24 characters in body
|
| Jun 29, 2015 at 13:55 | history | answered | Max Alekseyev | CC BY-SA 3.0 |