Discrete Mathematics and Combinatorics Commons^™

Fibonacci Determinants — A Combinatorial Approach, Arthur T. Benjamin, Naiomi T. Cameron, Jennifer J. Quinn

All HMC Faculty Publications and Research

In this paper, we provide combinatorial interpretations for some determinantal identities involving Fibonacci numbers. We use the method due to Lindström-Gessel-Viennot in which we count nonintersecting n-routes in carefully chosen digraphs in order to gain insight into the nature of some well-known determinantal identities while allowing room to generalize and discover new ones.

Q.954 And A.954, Quickie Problem And Solution, Arthur T. Benjamin, Michel Bataille

All HMC Faculty Publications and Research

Problem and proof proposed by authors.

Another proof, using lattice paths, can be found in Robert A. Sulanke's article, Objects Counted by the Central Delannoy Numbers, The Journal of Integer Sequences, Vol 6, 2003. A proof by polynomials is in Michel Bataille's paper Some Identities about an Old Combinatorial Sum, The Mathematical Gazette, March 2003, pp. 144-8. A slight change in the above proof leads to m ≥ n, a generalization proved by Li Zhou using lattice paths in The Mathematical Gazette.

A Constructive Proof Of Ky Fan's Generalization Of Tucker's Lemma, Timothy Prescott '02, Francis E. Su

All HMC Faculty Publications and Research

We present a proof of Ky Fan's combinatorial lemma on labellings of triangulated spheres that differs from earlier proofs in that it is constructive. We slightly generalize the hypotheses of Fan's lemma to allow for triangulations of Sⁿ that contain a flag of hemispheres. As a consequence, we can obtain a constructive proof of Tucker's lemma that holds for a more general class of triangulations than the usual version.

Counting On Determinants, Arthur T. Benjamin, Naiomi T. Cameron

All HMC Faculty Publications and Research

No abstract provided in this article.

Lower Bounds For Simplicial Covers And Triangulations Of Cubes, Adam Bliss '03, Francis E. Su

All HMC Faculty Publications and Research

We show that the size of a minimal simplicial cover of a polytope P is a lower bound for the size of a minimal triangulation of P, including ones with extra vertices. We then use this fact to study minimal triangulations of cubes, and we improve lower bounds for covers and triangulations in dimensions 4 through at least 12 (and possibly more dimensions as well). Important ingredients are an analysis of the number of exterior faces that a simplex in the cube can have of a specified dimension and volume, and a characterization of corner simplices in terms of their …

Combinatorial Proofs Of Fermat's, Lucas's, And Wilson's Theorems, Peter G. Anderson, Arthur T. Benjamin, Jeremy A. Rouse

All HMC Faculty Publications and Research

No abstract provided in this article.

A Combinatorial Approach To Hyperharmonic Numbers, Arthur T. Benjamin, David Gaebler '04, Robert Gaebler '04

All HMC Faculty Publications and Research

Hyperharmonic numbers arise by taking repeated partial sums of harmonic numbers. These numbers can be expressed in terms of r-Stirling numbers, leading to combinatorial interpretations of many interesting identities.

A Probabilistic View Of Certain Weighted Fibonacci Sums, Arthur T. Benjamin, Judson D. Neer, Daniel T. Otero, James A. Sellers

All HMC Faculty Publications and Research

In this article, we pursue the reverse strategy of using probability to derive a_n and develop an exponential generating function for a_n in Section 3. In Section 4, we present a method for finding an exact, non-recursive, formula for a_n.

The Fibonacci Numbers -- Exposed More Discretely, Arthur T. Benjamin, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Two Quick Combinatorial Proofs, Arthur T. Benjamin, Michael E. Orrison

All HMC Faculty Publications and Research

Presentation of two simple combinatorial proofs.

A Stirling Encounter With Harmonic Numbers, Arthur T. Benjamin, Gregory O. Preston '01, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Enumeration Of Matchings In The Incidence Graphs Of Complete And Complete Bipartite Graphs, Nicholas Pippenger

All HMC Faculty Publications and Research

If G = (V, E) is a graph, the incidence graphI(G) is the graph with vertices I ∪ E and an edge joining v ∈ V and e ∈ E when and only when v is incident with e in G. For G equal to K_n (the complete graph on n vertices) or K_n,n (the complete bipartite graph on n + n vertices), we enumerate the matchings (sets of edges, no two having a vertex in common) in I(G), both exactly (in terms of generating …

Enumeration Of Equicolourable Trees, Nicholas Pippenger

All HMC Faculty Publications and Research

A tree, being a connected acyclic graph, can be bicolored in two ways, which differ from each other by exchange of the colors. We shall say that a tree is equicolorable if these bicolorings assign the two colors to equal numbers of vertices. Labelled equicolored trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolorable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolorable is asymptotically just twice the probability that its vertices would be equicolored if they were assigned colors by …

Phased Tilings And Generalized Fibonacci Identities, Arthur T. Benjamin, Jennifer J. Quinn, Francis E. Su

All HMC Faculty Publications and Research

Fibonacci numbers arise in the solution of many combinatorial problems. They count the number of binary sequences with no consecutive zeros, the number of sequences of 1's and 2's which sum to a given number, and the number of independent sets of a path graph. Similar interpretations exist for Lucas numbers. Using these interpretations, it is possible to provide combinatorial proofs that shed light on many interesting Fibonacci and Lucas identities (see [1], [3]). In this paper we extend the combinatorial approach to understand relationships among generalized Fibonacci numbers.

Given G₀ and G₁ a generalized Fibonacci sequence G …

Random Approaches To Fibonacci Identities, Arthur T. Benjamin, Gregory M. Levin, Karl Mahlburg '01, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Counting On Continued Fractions, Arthur T. Benjamin, Francis E. Su, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Recounting Fibonacci And Lucas Identities, Arthur T. Benjamin, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Unevening The Odds Of "Even Up", Arthur T. Benjamin, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

Combinatorics And Campus Security, Arthur T. Benjamin

All HMC Faculty Publications and Research

One day I received electronic mail from our director of campus security [Gilbraith 1993]:

"I have a puzzle for you that has practical applications for me. I need to know how many different combinations there are for our combination locks. A lock has 5 buttons. In setting the combination you can use only 1button or as many as 5. Buttons may be pressed simultaneously and / or successively, but the same button cannot be used more than once in the same combination.

I had a student (obviously not a math major) email me that there are only 120 possibilities, but …

Analysis Of A Recurrence Arising From A Construction For Nonblocking Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

Define f on the integers n > 1 by the recurrence f(n) = min( n, min_m|n( 2f(m) + 3f(n/m) ). The function f has f(n) = n as its upper envelope, attained for all prime n.

The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form f(n) ~ C(log n)^{1 + 1/γ} for certain constants γ and C, in the sense that for any ε > 0, the inequality f(n) ≤ (C + ε)(log n)^{1 + 1/γ} holds for infinitely many n, while f(n) ≤ (C + ε)(log …

Analysis Of A Recurrence Arising From A Construction For Non-Blocking Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

Define f on the integers $n > 1$ by the recurrence $f( n ) = \min \{ n,\min _{m|n} 2f( m ) + 3f( n/m ) \}$. The function f has $f( n ) = n$ as its upper envelope, attained for all prime n. The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form $f( n ) \sim C( \log n )^{1 + 1/\gamma } $ for certain constants $\gamma $ and C, in the sense that for any $\varepsilon > 0$, the inequality $f( n ) \leq ( …

Fault-Tolerant Circuit-Switching Networks, Nicholas Pippenger, Geng Lin

All HMC Faculty Publications and Research

The authors consider fault-tolerant circuit-switching networks under a random switch failure model. Three circuit-switching networks of theoretical importance—nonblocking networks, rearrangeable networks, and superconcentrators—are studied. The authors prove lower bounds for the size (the number of switches) and depth (the largest number of switches on a communication path) of such fault-tolerant networks and explicitly construct such networks with optimal size Θ( n (log n)² ) and depth Θ( log n ).

Optimal Leapfrogging, Joel Auslander, Arthur T. Benjamin, Daniel S. Wilkerson

All HMC Faculty Publications and Research

No abstract provided in this article.

Another Way Of Counting Nᴺ, Arthur T. Benjamin, Fritz Juhnke

All HMC Faculty Publications and Research

An original combinatorial proof of a combinatorial identity is presented.

The Expected Capacity Of Concentrators, Nicholas Pippenger

All HMC Faculty Publications and Research

The expected capacity of a class of sparse concentrators called modular concentrators is determined. In these concentrators, each input is connected to exactly two outputs, each output is connected to exactly three inputs, and the girth (the length of the shortest cycle in the connexion graph) is large. Two definitions of expected capacity are considered. For the first (which is due to Masson and Morris), it is assumed that a batch of customers arrive at a random set of inputs and that a maximum matching of these customers to servers at the outputs is found. The number of unsatisfied requests …

Random Sequential Absorption On Graphs, Nicholas Pippenger

All HMC Faculty Publications and Research

This paper analyzes a process whereby the vertices of a graph are considered in a random sequence,and each considered vertex is “occupied” unless it or an adjacent vertex has previously been occupied. The process continues until no more vertices can be occupied, at which point the “jamming limit” has been reached. The case in which the graph is regular (so that every vertex has degree $d\geqq 2$ and has “few short cycles” is treated. In particular, the results apply to infinite regular trees, to finite graphs obtained from them by forming quotient graphs, and to random regular graphs.

It is …

Wide-Sense Nonblocking Networks, Paul Feldman, Joel Friedman, Nicholas Pippenger

All HMC Faculty Publications and Research

A new method for constructing wide-sense nonblocking networks is presented. Application of this method yields (among other things) wide-sense nonblocking generalized connectors with n inputs and outputs and size O( n log n ), and with depth k and size O( n^{1 + 1/k} ( log n )^{1 - 1/k} ).

Some Graph-Colouring Theorems With Applications To Generalized Connection Networks, David G. Kirkpatrick, Maria M. Klawe, Nicholas Pippenger

All HMC Faculty Publications and Research

With the aid of a new graph-colouring theorem, we give a simple explicit construction for generalized n-connectors with 2k - 1 stages and O( n^{1 + 1 / k} (log n )^{( k - 1)/ 2} ) edges. This is asymptotically the best explicit construction known for generalized connectors.

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis

All HMC Faculty Publications and Research

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Π_k-formulae of size n for which every Σ_k-formula has size exp Ω(n^1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σ_k-formula of size exp O(n^1/(k-1)). Thus our hierarchy theorem is the best possible.

Rearrangeable Networks With Limited Depth, Nicholas Pippenger, Andrew C.-C. Yao

All HMC Faculty Publications and Research

Rearrangeable networks are switching systems capable of establishing simultaneous independent communication paths in accordance with any one-to-one correspondence between their n inputs and n outputs. Classical results show that Ω( n log n ) switches are necessary and that O( n log n ) switches are sufficient for such networks. We are interested in the minimum possible number of switches in rearrangeable networks in which the depth (the length of the longest path from an input to an output) is at most k, where k is fixed as n increases. We show that Ω( n^{1 + 1/k} ) switches …