Intro.sagews

P = Permutations()
P

Standard permutations

P.category()

Category of infinite enumerated sets

P3 = Permutations(3)
P3

Standard permutations of 3

perm = P3.an_element()
perm

[3, 1, 2]

perm2 = Permutation([2,1,3])
perm2

[2, 1, 3]

perm.parent()

Standard permutations of 3

︠a7e00e40-ac46-4b3a-8da1-98e9eaf40793︠
list(P3)

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

P3.cardinality()

6

P100 = Permutations(100)
P100

Standard permutations of 100

P100.cardinality()

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

P100.random_element()

[84, 33, 16, 44, 78, 21, 66, 22, 35, 99, 55, 85, 50, 87, 61, 65, 15, 63, 90, 5, 76, 18, 12, 64, 81, 30, 20, 48, 68, 3, 89, 83, 92, 56, 14, 19, 4, 47, 7, 46, 42, 26, 54, 82, 88, 86, 95, 43, 39, 29, 10, 36, 69, 62, 91, 45, 70, 96, 25, 79, 23, 73, 27, 60, 75, 97, 17, 100, 9, 72, 8, 52, 71, 37, 31, 13, 41, 40, 1, 58, 67, 93, 94, 49, 77, 59, 24, 51, 34, 2, 11, 74, 6, 57, 53, 28, 32, 38, 80, 98]

BT = BinaryTrees()
BT

Binary trees

BT.cardinality()

+Infinity

BT2 = BinaryTrees(2)
BT2

Binary trees of size 2

BT2.cardinality()

2

latex.eval(latex(BT2[0]))

''

latex.eval(latex(BT2[1]))

''

bt = BinaryTree([[None,[]],[[],[[[],[]],[None,[]]]]])
latex.eval(latex(bt))

''

bt.node_number()
bt.depth()
bt.is_complete()

11 5 False

BT3 = BinaryTrees(3)
BT3.cardinality()

5

for bt in BinaryTrees(3):
    latex.eval(latex(bt))

''

''

''

''

''

BinaryTrees(4).cardinality()
BinaryTrees(5).cardinality()

14 42

BinaryTrees(11).cardinality()

58786

[BinaryTrees(i).cardinality() for i in xrange(10)]

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

[1/(n+1) * binomial(2*n, n) for n in xrange(10)]

[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

BT3.cardinality??

   File: /projects/sage/sage-6.7/local/lib/python2.7/site-packages/sage/combinat/binary_tree.py
   Source:
       def cardinality(self):
        """
        The cardinality of ``self``

        This is a Catalan number.

        TESTS::

            sage: BinaryTrees(0).cardinality()
            1
            sage: BinaryTrees(5).cardinality()
            42
        """
        from combinat import catalan_number
        return catalan_number(self._size)

all([len([bt for bt in BinaryTrees(n) if bt.depth() == n]) == 2^(n-1) for n in xrange(2,8)])

True

def random_binary1(size):
    return BinaryTrees(size).random_element()
    
bt1 = random_binary1(11)
bt2 = random_binary1(11)
latex.eval(latex(bt1))
latex.eval(latex(bt2))

''

''

def random_binary2(size):
    p = Permutations(size).random_element()
    return p.binary_search_tree_shape()

bt1 = random_binary2(11)
bt2 = random_binary2(11)
latex.eval(latex(bt1))
latex.eval(latex(bt2))

''

''

mean([float(random_binary1(11).depth()) for i in xrange(1000)])

7.568

mean([float(random_binary2(11).depth()) for i in xrange(1000)])

5.938

mean([float(random_binary1(100).depth()) for i in xrange(10000)])

29.9965

mean([float(random_binary2(100).depth()) for i in xrange(10000)])

13.2599