Two principles of SageMath that we have encoutered before:
The same principle is true for open databases!
oeis('narayana')
0: A001263: Triangle of Narayana numbers T(n,k) = C(n-1,k-1)*C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle. 1: A000930: Narayana's cows sequence: a(0) = a(1) = a(2) = 1; thereafter a(n) = a(n-1) + a(n-3). 2: A090181: Triangle of Narayana (A001263) with 0 <= k <= n, read by rows.
What is your favourite sequence?
Some more famous sequences:
And sequences with two parameters also appear in the OEIS, as an array or a triangle.
# What is this?
oeis(list(str(float(pi))))
0: A000796: Decimal expansion of Pi (or digits of Pi). 1: A212131: Decimal expansion of k such that e^(k*sqrt(163)) = round(e^(Pi*sqrt(163))). 2: A112602: Erroneous version of decimal expansion of Pi (see A000796 for the correct version).
oeis(list(str(float(pi))))
Takes $\pi$, float
expands its decimal (to 16 digits of precision), str
changes the number into a string (so a sequence) of characters, lists splits them. Asking the OEIS gives some choices for sequences.
Any question on the OEIS?
I made up some statistic for some Dyck Paths, and store them as tuples in list_for_search
. Can you find what is that statistics?
for pair in list_for_search:
print(ascii_art(pair[0]), pair[1])
/\/\ 0 /\ / \ 2 /\/\/\ 0 /\ /\/ \ 1 /\ / \/\ 1 /\/\ / \ 1 /\ / \ / \ 3 /\/\/\/\ 0 /\ /\/\/ \ 1 /\ /\/ \/\ 1 /\/\ /\/ \ 2 /\ / \ /\/ \ 2 /\ / \/\/\ 0 /\ /\ / \/ \ 0 /\/\ / \/\ 2 /\/\/\ / \ 2 /\ /\/ \ / \ 2 /\ / \ / \/\ 1 /\ / \/\ / \ 1 /\/\ / \ / \ 2 /\ / \ / \ / \ 4
Or
findstat(list_for_search)
0: St000445oMp00118 (quality [100, 100]) 1: St000445oMp00121oMp00118 (quality [100, 100]) 2: St001126oMp00030oMp00118 (quality [100, 100]) 3: St001232oMp00222oMp00199 (quality [14, 60]) 4: St001879oMp00047oMp00026 (quality [14, 60]) 5: St001880oMp00047oMp00026 with offset 1 (quality [14, 60]) 6: St001880oMp00242oMp00143 with offset 2 (quality [14, 40])
This gives several options, of varying quality... The top three are high quality, meaning that they match 100%. We can ask FindStat what they are.
Exploring
0: St000445oMp00118 (quality [100, 100])
We start with the statistic, then the map. We are interested in Statistic 445.
findstat(445).description()
'The number of rises of length 1 of a Dyck path.'
One can also get the code used to generate the statistic.
findstat(445).code()
'def statistic(D):\r\n return list(D.rise_composition()).count(1)\r\n'
If we are interested in the distribution, we can ask for the generating function or ask to browse the OEIS for the corresponding sequence.
findstat(445).generating_functions()
{2: q^2 + 1, 3: q^3 + 3*q + 1, 4: q^4 + 6*q^2 + 4*q + 3, 5: q^5 + 10*q^3 + 10*q^2 + 15*q + 6, 6: q^6 + 15*q^4 + 20*q^3 + 45*q^2 + 36*q + 15, 7: q^7 + 21*q^5 + 35*q^4 + 105*q^3 + 126*q^2 + 105*q + 36}
findstat(445).oeis_search()
Searching the OEIS for "1,0,1 1,3,0,1 3,4,6,0,1 6,15,10,10,0,1 15,36,45,20,15,0,1 36,105,126,105,35,21,0"
0: A091867: Triangle read by rows: T(n,k) = number of Dyck paths of semilength n having k peaks at odd height.
We can also ask for reference, or get all of this at one by typing browse()
.
findstat(445).references()
0: [1] Kangro, K., Pourmoradnasseri, M., Theis, D. O., Short note on the number of 1-ascents in dispersed dyck paths [[arXiv:1603.01422]]
findstat(445).browse() # opens a tab in a browser
Recently, Jennifer Elder, Erin McNicholas, Jessica Striker, Amanda Welch and myself defined interval-closed subsets of a partially ordered set (poset, for short). (https://arxiv.org/abs/2307.08520) These subsets are such that if $x \leq y \leq z$ in a poset and both $x$ and $z$ belong to the interval-closed subset, then $y$ does as well:
$$x\leq y \leq z \text{ and } x,z \in I \implies y \in I.$$We were trying to count some types of interval-closed sets.
We draw posets with cover relations, with the smaller items at the bottom, and the larger at the top.
Example: divisors poset. We say that $x \preceq y$ if $x$ divides $y$, as an integer.
P = Posets.DivisorLattice(12); P
It is known that divisors posets can be drawn as rectangle posets. We wanted to count, for divisors posets of numbers with two different prime factors, a specific type of interval-closed sets, namely those that have elements in all the chains.
# All four chains have a different color here
color_all_a_chains(4,3, label=False)
We were wondering how many interval-closed sets had items in all $a$ chains for the divisors poset of $2^{a-1}3^{b-1}$.
The left-hand side subset (in red) has items in all 4 chains, while the one on the right does not (no element in top chain).
P = Posets.DivisorLattice(72);
graphics_array([subset_plot(P, (3,6,8,12)), subset_plot(P, (3,4,6,9,12, 18, 36))])
(Naive) method:
Questions:
def has_elements_in_all_a_chains(I, a):
chain = [False for _ in range(a)]
try:
for x in I:
chain[x[0]] = True
except:
print(x, chain, a)
if chain == [True for _ in range(a)]:
return True
return False
def count_ICS_that_have_elements_in_all_a_chains(a, b):
count = 0
P = Posets.ProductOfChains([a, b])
for A in P.antichains_iterator():
J = P.subposet(P.order_ideal(A))
Q = P.subposet(Set(J).difference(A))
for B in Q.antichains_iterator():
I = Set(J).difference(Set(P.order_ideal(B)))
if has_elements_in_all_a_chains(I, a):
count += 1
return count
counts = []
for s in range(2,9):
counts.extend([count_ICS_that_have_elements_in_all_a_chains(s-b, b) for b in range(1, s+1)])
print(counts, '\n', oeis(counts)) # Requires internet access. If you don't have it, replace this line with `print(counts)`, and enter the output in the OEIS.
[1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 10, 20, 10, 1, 1, 15, 50, 50, 15, 1, 1, 21, 105, 175, 105, 21, 1, 1, 28, 196, 490, 490, 196, 28, 1] 0: A001263: Triangle of Narayana numbers T(n,k) = C(n-1,k-1)*C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle.
The first comment in the entry for sequence A001263 of the OEIS is that it is the "number of antichains (or order ideals) in the poset 2*(k-1)*(n-k)".
This put us on track to establish a bijection between order ideals of 2a(b-1) (the divisor poset of $2^{a-1}3^{b-2}5$) and interval-closed sets of a*b (the divisor poset of $2^{a-1}3^{b-1}$) with items in all $a$ chains.
In our paper (Section 4.1), we indeed show that this is a bijection, and conclude that they are counted by the Narayana numbers, as suggested by the OEIS.
Open problem
See the [paper]((https://arxiv.org/abs/2307.08520) for details if you are interested in working on this problem, or the Sage notebook with computations for this project.
The bijections will be found by a computer, so they might not be beautiful, or interesting... This is why we give it constraints.
Example of constraints:
We care about bijections because:
n = 3
A = DyckWords(n)
B = OrderedTrees(n+1)
def alpha1(d): return len(d.peaks())
def beta1(t): return findstat(167)(t) # findstat statistics #167 is the number of leaves in an ordered tree
bij = Bijectionist(A, B) # We call the Bijectionist!
bij.set_statistics((alpha1, beta1))
sol = next((bij.solutions_iterator()))
for key in sol.keys():
show(graphics_array([key.plot(), sol[key].plot()]))
We can even see what all the constraints are on the bijection.
list(bij.minimal_subdistributions_iterator())
[([[1, 0, 1, 0, 1, 0, 1, 0]], [[[], [], [], []]]), ([[1, 1, 1, 1, 0, 0, 0, 0]], [[[[[[]]]]]]), ([[1, 0, 1, 1, 1, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0, 0], [1, 1, 0, 1, 1, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 0], [1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 0, 1, 0, 0, 0]], [[[], [[[]]]], [[[]], [[]]], [[[], [[]]]], [[[[]]], []], [[[[]], []]], [[[[], []]]]]), ([[1, 0, 1, 0, 1, 1, 0, 0], [1, 0, 1, 1, 0, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0, 0], [1, 1, 0, 0, 1, 0, 1, 0], [1, 1, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 0]], [[[], [], [[]]], [[], [[]], []], [[], [[], []]], [[[]], [], []], [[[], []], []], [[[], [], []]]])]
Exercise: how many solutions are there, to do a bijection that meets our constraints (for $n=4$)?
There are $6!\times 6!$ possible bijections, because in each block, we can match any path with any tree.
The bijectionist requires that the statistics satisfies $$\sum_{\pi} q^{s(\pi)} = \sum_{\pi} q^{\tau(\pi)},$$ so that they are equidistributed.
The bijectionist can give a bijection that works for example for all values less than 10. However, it does so by matching elements to satisfy constraints, but it might not give a general description to make it a nice conjecture.