Opened 3 years ago

Closed 2 years ago

# Hook statistics in binary Trees

Reported by: Owned by: boussica boussica minor sage-7.2 combinatorics binary trees, hook Adrien Boussicault, Bérénice Delcroix-Oger, Patxi Laborde-Zubieta Kevin Dilks, Frédéric Chapoton N/A d114661 (Commits) d114661139f46fa8e97f79a8c6176c535879e523

### 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.

### comment:1 Changed 3 years ago by boussica

• Owner changed from (none) to boussica

### comment:2 Changed 3 years ago by boussica

• Authors changed from Adrien Boussicault to Adrien Boussicault, Bérénice Delcroix-Oger, Patxi Laborde-Zubieta

### comment:3 Changed 3 years ago by boussica

• Branch set to u/boussica/hook_statistics_in_binary_trees

### comment:4 Changed 3 years ago by chapoton

• Commit set to 6b6aa4748b85f4e05fbf207436726e498b5eeb72

A few remarks:

• it seems better to use 'left' and 'right', rather than 0 and 1 for the side selection
• syntax of INPUT and OUTPUT is wrong; must be
```INPUT:

here
```

with just one colon, and a blank line just below the INPUT line

New commits:

 ​6b6aa47 `Add implementation of Hook statistic`

### comment:5 Changed 3 years ago by git

• 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 chapoton

rather use `"""` for the doc start and end (not `'''`)

maybe call the function `comb_list` (more explicit)

Last edited 3 years ago by chapoton (previous) (diff)

### comment:7 Changed 3 years ago by git

• 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 chapoton

If you want a review, you should set the status to "needs_review"

### comment:9 Changed 3 years ago by oger

• 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 chapoton

• Commit changed from 13522dd011463d9847458ff908a3504a234faf5d to 238b35298dae93ef5e2fb7365c65b9c9b25662a0

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 chapoton

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 3 years ago by chapoton

• Milestone changed from sage-6.10 to sage-7.0

Hello, are you still not interested by a review ? Have you abandoned this ticket ?

### comment:13 Changed 3 years ago by mantepse

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 3 years ago by chapoton

• 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 kdilks

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 non-trivial examples, since they really help illustrate the definitions.

### comment:16 Changed 2 years ago by kdilks

• 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 kdilks

• Commit changed from 238b35298dae93ef5e2fb7365c65b9c9b25662a0 to b28292079ba9bb92978b24498f6fe6b0a8909928
• Reviewers set to Kevin Dilks

New commits:

 ​6c3e0e8 `Merge branch 'u/oger/hook_statistics_in_binary_trees' of http://trac.sagemath.org/sage into hookstat19446` ​b282920 `Added ascii art to documentation`

### comment:18 Changed 2 years ago by kdilks

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 mantepse

Does anybody find my docstring proposals (from comment 13) helpful? If so, I'd add them.

### comment:20 Changed 2 years ago by chapoton

• 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 git

• 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 chapoton

good, but the new text is not correctly aligned

### comment:23 Changed 2 years ago by git

• 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 git

• Commit changed from c257d783d1ad63d4f513fc02ee2a614736afb407 to d114661139f46fa8e97f79a8c6176c535879e523

Branch pushed to git repo; I updated commit sha1. New commits:

 ​58c5494 `Merge branch 'public/19446' of git://trac.sagemath.org/sage into 19446` ​d114661 `trac #19446 two details in doc of comb method of binary trees`

### comment:25 Changed 2 years ago by chapoton

• Milestone changed from sage-7.0 to sage-7.2
• Reviewers changed from Kevin Dilks to Kevin Dilks, Frédéric Chapoton
• Status changed from needs_review to positive_review

ok, looks good to me.

New commits:

 ​58c5494 `Merge branch 'public/19446' of git://trac.sagemath.org/sage into 19446` ​d114661 `trac #19446 two details in doc of comb method of binary trees`

### comment:26 Changed 2 years ago by vbraun

• Branch changed from public/19446 to d114661139f46fa8e97f79a8c6176c535879e523
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.