## Pascal' Triangle and Catalan Numbers

*Thomas Koshy*

### in Catalan Numbers with Applications

- Published in print:
- 2008
- Published Online:
- January 2009
- ISBN:
- 9780195334548
- eISBN:
- 9780199868766
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195334548.003.0012
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter shows the various ways Catalan numbers can be extracted from Pascal's triangle. It includes discussion of nonisomorphic groups, Catalan polynomials, Touchard's recursive formula, and ... More

## EXPANDING THE TUTTE POLYNOMIAL OF A MATROID OVER THE INDEPENDENT SETS

*Koko Kalambay Kayibi*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0011
- Subject:
- Mathematics, Probability / Statistics

This chapter provides direct combinatorial proof of an expansion of the Tutte polynomial by independent sets of the matroid. Another expansion of the Tutte polynomial is presented in terms of ... More

## ORBIT COUNTING AND THE TUTTE POLYNOMIAL

*Peter J. Cameron*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0001
- Subject:
- Mathematics, Probability / Statistics

This chapter summarizes the various attempts to extend the Tutte polynomial of a matroid to a polynomial which counts orbits of a group on various sets of objects that the usual Tutte polynomial ... More

## COMPLEXITY OF GRAPH POLYNOMIALS

*Steven D. Noble*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0013
- Subject:
- Mathematics, Probability / Statistics

This chapter examines the complexity of evaluating graph polynomials, related to the Tutte polynomial, for various classes of matroids. It begins with a short introduction to matroids, complexity, ... More

## TUTTE-WHITNEY POLYNOMIALS: SOME HISTORY AND GENERALIZATIONS

*Graham E. Farr*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0003
- Subject:
- Mathematics, Probability / Statistics

The Tutte-Whitney polynomials play a key role in the study of counting problems on graphs, and have close connections with statistical mechanics and knot theory. This chapter briefly reviews their ... More

## APPROXIMATING THE TUTTE POLYNOMIAL

*Mark Jerrum*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0009
- Subject:
- Mathematics, Probability / Statistics

This chapter examines some algorithmic problems associated with matroids. It focuses on determining a ‘fully polynomial randomized approximation scheme’ or ‘FPRAS’. First, the problem of counting ... More

## Finding the Roots of Algebraic Equations

*Victor J. Katz and Karen Hunger Parshall*

### in Taming the Unknown: A History of Algebra from Antiquity to the Early Twentieth Century

- Published in print:
- 2014
- Published Online:
- October 2017
- ISBN:
- 9780691149059
- eISBN:
- 9781400850525
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691149059.003.0011
- Subject:
- Mathematics, History of Mathematics

This chapter highlights some of the struggles to solve fifth-degree polynomials as well as the development of the idea of a group and its application to answering the question of solvability of ... More

## Sonine Polynomials Expansion of The Velocity Distribution Function

*Nikolai V. Brilliantov and Thorsten Pöschel*

### in Kinetic Theory of Granular Gases

- Published in print:
- 2004
- Published Online:
- January 2010
- ISBN:
- 9780198530381
- eISBN:
- 9780191713057
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198530381.003.0007
- Subject:
- Physics, Condensed Matter Physics / Materials

The velocity distribution of function of a granular gas is different from the Maxwell distribution. It may be represented in the form of a Sonine polynomials expansion. This chapter shows that the ... More

## Thermoelastic Polynomials

*Józef Ignaczak and Martin Ostoja‐Starzewski*

### in Thermoelasticity with Finite Wave Speeds

- Published in print:
- 2009
- Published Online:
- February 2010
- ISBN:
- 9780199541645
- eISBN:
- 9780191716164
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199541645.003.0009
- Subject:
- Mathematics, Applied Mathematics, Mathematical Physics

This chapter begins from the observation that the fundamental solutions of the G‐L theory may be determined with the help of polynomial sequences on the time axis, the so‐called polynomials of ... More

## Knowability

*Ben Brubaker, Daniel Bump, and Solomon Friedberg*

### in Weyl Group Multiple Dirichlet Series: Type A Combinatorial Theory (AM-175)

- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691150659
- eISBN:
- 9781400838998
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691150659.003.0012
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter introduces the Knowability Lemma, which explains when products of Gauss sums associated to elements of a preaccordion are explicitly evaluable as polynomials in q, the order of the ... More

## Sylvester denumerant

*J. L. Ramírez Alfonsín*

### in The Diophantine Frobenius Problem

- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198568209
- eISBN:
- 9780191718229
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198568209.003.0004
- Subject:
- Mathematics, Algebra, Combinatorics / Graph Theory / Discrete Mathematics

In 1857, while investigating the partition number function, J. J. Sylvester defined the function d(m; a1, . . . , an), called the denumerant, as the number of nonnegative integer representations of m ... More

## TESTING FOR THE EXISTENCE OF HOMOMORPHISMS

*Pavol Hell and Jaroslav Nešetřil*

### in Graphs and Homomorphisms

- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0005
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target ... More

## Harmonic morphisms defined by polynomials

*Paul Baird and John C. Wood*

### in Harmonic Morphisms Between Riemannian Manifolds

- Published in print:
- 2003
- Published Online:
- September 2007
- ISBN:
- 9780198503620
- eISBN:
- 9780191708435
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198503620.003.0005
- Subject:
- Mathematics, Pure Mathematics

This chapter establishes the Liouville-type theorem which asserts that any entire (i.e., globally defined) harmonic morphism from a Euclidean space of arbitrary dimension to a Euclidean space of ... More

##
*SL*(*n*) Examples with Slightly Composite *n*

*Nicholas M. Katz*

### in Convolution and Equidistribution: Sato-Tate Theorems for Finite-Field Mellin Transforms (AM-180)

- Published in print:
- 2012
- Published Online:
- October 2017
- ISBN:
- 9780691153308
- eISBN:
- 9781400842704
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691153308.003.0023
- Subject:
- Mathematics, Number Theory

This chapter continues to study the object N of Theorem 21.1. Thus, k is a finite field of characteristic p, ψ a nontrivial additive character of k, f(x) = f(x)=∑i=−baAixi∈k[x,1/x]Aᵢxⁱ ɛ k[x, 1/x] ... More

##
Other *SL*(*n*) Examples

*Nicholas M. Katz*

### in Convolution and Equidistribution: Sato-Tate Theorems for Finite-Field Mellin Transforms (AM-180)

- Published in print:
- 2012
- Published Online:
- October 2017
- ISBN:
- 9780691153308
- eISBN:
- 9781400842704
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691153308.003.0024
- Subject:
- Mathematics, Number Theory

This chapter fixes an integer n ≤ 3 which is not a power of the characteristic p, and a monic polynomial f(x) ɛ k[x] of degree n, f(x)=∑i=0nAixi, An=1.

## FOURIER ANALYSIS ON FINITE ABELIAN GROUPS: SOME GRAPHICAL APPLICATIONS

*Andrew Goodall*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0007
- Subject:
- Mathematics, Probability / Statistics

This article reviews basic techniques of Fourier analysis on a finite abelian group Q, with subsequent applications in graph theory. These include evaluations of the Tutte polynomial of a graph G in ... More

## FLOWS AND FERROMAGNETS

*Geoffrey Grimmett*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0008
- Subject:
- Mathematics, Probability / Statistics

The Tutte polynomial and its relatives play important roles in matroid theory, computational complexity, and models of statistical physics. They provide the natural way to count and relate a variety ... More

## INTERACTIVE PROGRAMS AND WEAKLY FINAL COALGEBRAS IN DEPENDENT TYPE THEORY

*Peter Hancock and Anton Setzer*

### in From Sets and Types to Topology and Analysis: Towards practicable foundations for constructive mathematics

- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198566519
- eISBN:
- 9780191713927
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566519.003.0007
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy

This chapter considers the representation of interactive programs in dependent type theory and bases it on the monadic I/O used in Haskell. Two versions are described: in the first the interface with ... More

## CONNECTIONS TO APPROXIMATION ALGORITHMS

*Rolf Niedermeier*

### in Invitation to Fixed-Parameter Algorithms

- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0014
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter summarizes the currently known connections between fixed-parameter and polynomial-time approximation algorithmics. Important topics in this context are lower bound and impossibility ... More

## THE CONTRIBUTIONS OF DOMINIC WELSH TO MATROID THEORY

*James Oxley*

### in Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh

- Published in print:
- 2007
- Published Online:
- September 2007
- ISBN:
- 9780198571278
- eISBN:
- 9780191718885
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198571278.003.0015
- Subject:
- Mathematics, Probability / Statistics

Dominic Welsh began writing papers in matroid theory nearly forty years ago. Since then, he has made numerous important contributions to the subject. This chapter reviews Dominic Welsh's work in and ... More