Opened 3 years ago
Closed 2 years ago
#19446 closed enhancement (fixed)
Hook statistics in binary Trees
Reported by:  boussica  Owned by:  boussica 

Priority:  minor  Milestone:  sage7.2 
Component:  combinatorics  Keywords:  binary trees, hook 
Cc:  Merged in:  
Authors:  Adrien Boussicault, Bérénice DelcroixOger, Patxi LabordeZubieta  Reviewers:  Kevin Dilks, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  d114661 (Commits)  Commit:  d114661139f46fa8e97f79a8c6176c535879e523 
Dependencies:  Stopgaps: 
Description
We add a hook statistics on binary trees.
The hook of a vertex v is the union of {v}, its leftmost and· rightmost branches.
There is a unique way to partition the vertices in hooks. The number of hooks in such a partition is the hook number of the tree.
We can obtain this partition recursively by extracting the root's hook· and iterating the processus on each tree of the remaining forest.
Change History (26)
comment:1 Changed 3 years ago by
 Owner changed from (none) to boussica
comment:2 Changed 3 years ago by
comment:3 Changed 3 years ago by
 Branch set to u/boussica/hook_statistics_in_binary_trees
comment:4 Changed 3 years ago by
 Commit set to 6b6aa4748b85f4e05fbf207436726e498b5eeb72
comment:5 Changed 3 years ago by
 Commit changed from 6b6aa4748b85f4e05fbf207436726e498b5eeb72 to 4ed1b4d305503b52840badb59fc6cc25ffd0dbaa
Branch pushed to git repo; I updated commit sha1. New commits:
4ed1b4d  Update documentation of hook_number() and comb()

comment:6 Changed 3 years ago by
rather use """
for the doc start and end (not '''
)
maybe call the function comb_list
(more explicit)
comment:7 Changed 3 years ago by
 Commit changed from 4ed1b4d305503b52840badb59fc6cc25ffd0dbaa to 13522dd011463d9847458ff908a3504a234faf5d
Branch pushed to git repo; I updated commit sha1. New commits:
13522dd  Modify ''' in the documentation

comment:8 Changed 3 years ago by
If you want a review, you should set the status to "needs_review"
comment:9 Changed 3 years ago by
 Branch changed from u/boussica/hook_statistics_in_binary_trees to u/oger/hook_statistics_in_binary_trees
comment:10 Changed 3 years ago by
 Commit changed from 13522dd011463d9847458ff908a3504a234faf5d to 238b35298dae93ef5e2fb7365c65b9c9b25662a0
Salut, Adrien et Bérénice.
Quand on travaille à plusieurs sur les mêmes tickets, on peut utiliser comme nom de branche un truc du style public/hook_statistics_in_binary_trees
pour ne pas avoir a changer le nom de la branche à chaque fois.
New commits:
238b352  Add the twisting statistic

comment:11 Changed 3 years ago by
So you do not want this to be reviewed ??
Anyway, you can replace
if len(L)>0:
by
if len(L):
and also
tn[0]=tn[0]+1
by
tn[0] += 1
comment:12 Changed 2 years ago by
 Milestone changed from sage6.10 to sage7.0
Hello, are you still not interested by a review ? Have you abandoned this ticket ?
comment:13 Changed 2 years ago by
I did not get the definition of hook upon first reading. Thus, here are some suggestions for the docstrings. A reference where one can find a definition would be good, too.
I'd like to submit this statistic to http://FindStat.org  would this be OK?
Return the comb of a tree. There are two combs in a binary tree: a left comb and a right comb. Consider the vertices of the leftmost (resp. rightmost) branch of the root, excluding the root itself. The left (resp. right) comb is the list of right (resp. left) subtree of each of these vertices. INPUT:  ``side``  (default: 'left') set to 'left' to obtain the left comb, and to 'right' to obtain the right comb. OUTPUT: A list of binary trees.
Return the number of hooks. The hook of a vertex v is the subtree that consists of {v}, the leftmost branch and the rightmost branch of v. The set of hooks partitions the binary tree. The number of hooks in such a partition is the hook number of the tree. We can obtain this partition recursively by extracting the root's hook and repeating the process on each tree of the remaining forest.
comment:14 Changed 2 years ago by
 Status changed from new to needs_review
ok, let me put that in needs_review, after a mail exchange with Adrien
comment:15 Changed 2 years ago by
Everything looks good to me (it seems a few people have already looked it over and made comments). The one thing I'd like to see (and might add myself) is ASCII art representations of the nontrivial examples, since they really help illustrate the definitions.
comment:16 Changed 2 years ago by
 Branch changed from u/oger/hook_statistics_in_binary_trees to u/kdilks/hook_statistics_in_binary_trees
comment:17 Changed 2 years ago by
 Commit changed from 238b35298dae93ef5e2fb7365c65b9c9b25662a0 to b28292079ba9bb92978b24498f6fe6b0a8909928
 Reviewers set to Kevin Dilks
comment:18 Changed 2 years ago by
Somebody can set a positive review on my behalf once they've verified that everything is ok with my additions to the documentation.
comment:19 Changed 2 years ago by
Does anybody find my docstring proposals (from comment 13) helpful? If so, I'd add them.
comment:20 Changed 2 years ago by
 Branch changed from u/kdilks/hook_statistics_in_binary_trees to public/19446
 Commit changed from b28292079ba9bb92978b24498f6fe6b0a8909928 to cb93656f7f8b50a380a55b59b743dbfbaa6df99e
here is a new git branch with some little doc and code cleanups.
I am still not happy with the documentation, in particular
 what is a "branch" ? it should be defined somewhere..
New commits:
ae98a59  Merge branch 'u/kdilks/hook_statistics_in_binary_trees' of ssh://trac.sagemath.org:22/sage into tree_hook

cb93656  trac #19446 a few doc and code cleanup changes

comment:21 Changed 2 years ago by
 Commit changed from cb93656f7f8b50a380a55b59b743dbfbaa6df99e to 8f0c777e13f768ae343816058e5c9a9a7d69e743
Branch pushed to git repo; I updated commit sha1. New commits:
8f0c777  I add some details one the documentation (especially the definition of a branch)

comment:22 Changed 2 years ago by
good, but the new text is not correctly aligned
comment:23 Changed 2 years ago by
 Commit changed from 8f0c777e13f768ae343816058e5c9a9a7d69e743 to c257d783d1ad63d4f513fc02ee2a614736afb407
Branch pushed to git repo; I updated commit sha1. New commits:
c257d78  Correction of spaces

comment:24 Changed 2 years ago by
 Commit changed from c257d783d1ad63d4f513fc02ee2a614736afb407 to d114661139f46fa8e97f79a8c6176c535879e523
comment:25 Changed 2 years ago by
 Milestone changed from sage7.0 to sage7.2
 Reviewers changed from Kevin Dilks to Kevin Dilks, Frédéric Chapoton
 Status changed from needs_review to positive_review
comment:26 Changed 2 years ago by
 Branch changed from public/19446 to d114661139f46fa8e97f79a8c6176c535879e523
 Resolution set to fixed
 Status changed from positive_review to closed
A few remarks:
with just one colon, and a blank line just below the INPUT line
New commits:
Add implementation of Hook statistic