# Enumerations of plane trees with multiple edges and Raney lattice paths

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
337
Identifiers
DOI: 10.1016/j.disc.2014.07.024
Keywords
• Enumeration Of Plane Trees
• Lattice Paths
• Raney Lemma

## Abstract

Abstract An N-ary plane multitree is a rooted tree whose subtrees at any vertex are linearly ordered, and every node has at most N outgoing edges to its children, and two nodes can be connected by multiple edges. An N-Raney path of length n is a lattice path running from (0,1) to (n,0) consisting of steps (1,k) for k∈Z such that k≤N, and for which all points except the last one lie above the x-axis. We show a bijection between N-Raney paths of length n and (N+1)-ary plane multitrees of n nodes. We show also a bijection between Raney paths and Raney sequences of integers whose sum is +1 and every partial sum is positive. These two bijections are a main tool to derive formulas for the number of N-ary plane multitrees with specified number of nodes, edges, and leaves. Some statistical properties are considered. It is shown that when N and n tend to infinity, the ratio of the number of leaves to the total number of nodes in all N-ary plane multitrees with n nodes is 1/e.

Seen <100 times

# More articles like this

## Enumerations of plane trees with multiple edges an...

on Discrete Mathematics

Jun 29, 2009

Mar 30, 2012

## Counting lattice paths in restricted planes

on Discrete Mathematics Jan 01, 2000
More articles like this..