Combinatorics

May need to study combinatorics for many reasons.

Needed for Geometric Algebra.

  1. Precedes Extension Theory as discrete version.
  2. Generalizes Universal Geometric Calculus with Crapo/Brini letterplace superalgebras and Whitney Matroids.
  3. Pregeometry, combinatorial geometry, abstract convexity, greedoids, myopic optimization.
  4. Polytopes, linear programming.
  5. “Combinatorial essence” of proofs.
  6. Counting methods bijections look like lawveres cyclindirical unity of opposites modal adoints.
  7. Numbers from arithmoi related to pythogorean stuff.
  8. Diagram chasing.
  9. Simplicial complexes.
  10. n-categories.

Perhaps also for simulating evolution of new technologies:

https://en.m.wikipedia.org/wiki/Combinatorial_chemistry

https://en.m.wikipedia.org/wiki/Combinatorial_biology

Basic Principles:

https://en.m.wikipedia.org/wiki/Combinatorial_principles

https://en.m.wikipedia.org/wiki/Combinatorial_proof

https://en.m.wikipedia.org/wiki/Combination

https://en.m.wikipedia.org/wiki/Permutation

https://en.m.wikipedia.org/wiki/Combinatorics

https://en.m.wikipedia.org/wiki/Figurate_number#Gnomon

https://en.m.wikipedia.org/wiki/Pascal%27s_triangle#Patterns_and_properties

https://en.m.wikipedia.org/wiki/Polygonal_number

https://en.m.wikipedia.org/wiki/Discrete_geometry

https://jehovajah.wordpress.com/2013/04/14/grassmann-the-new-pythagorus/

I am not sure how much is prior to arithmetic and how much depends on arithmetic.

Structural induction seems to be part of general “theory of forms” and quickly heads into binomials etc.

@inbook{Skolem-1955,
doi = {10.1016/s0049-237x(09)70300-3},
title = {[Studies in Logic and the Foundations of Mathematics] Mathematical Interpretation of Formal Systems Volume 16 || Peano’s Axioms and Models of Arithmetic},
author = {Skolem, Th.},
isbn = {9780444533814},
year = {1955},
page = {1–14},
url = {http://gen.lib.rus.ec/scimag/index.php?s=10.1016/s0049-237x(09)70300-3},
}

More usual approach seems much more metaphysical:

https://en.m.wikipedia.org/wiki/Peano_axioms#Arithmetic

Suspect Hao Wang, Mirceau Radu and others failed to grasp that Robert (and Hermann) Grassmann were being very finitist and perhaps prefiguring constructive univalent homotopy type theory. (They sure do stress univalence!)

The HoTT Book

https://en.m.wikipedia.org/wiki/Homotopy_type_theory

https://en.m.wikipedia.org/wiki/Intuitionistic_type_theory#Extensional_versus_intensional

https://en.m.wikipedia.org/wiki/Univalent_foundations

Wow!

In foundations of mathematics, univalent foundations is an approach to the foundations of constructive mathematics[1] based on the idea that mathematics studies structures on “univalent types” that correspond, under the projection to set-theoretic mathematics, to homotopy types. Univalent foundations are inspired both by the old Platonic ideas of Hermann Grassmann and Georg Cantor and by the “categorical” mathematics in the style of Alexander Grothendieck. It departs from the use of predicate logic as the underlying formal deduction system, replacing it, at the moment, by a version of the Martin-Löf type theory. The development of the univalent foundations is closely related with the development of homotopy type theory.

Univalent foundations are compatible with structuralism, if an appropriate (i.e. categorical) notion of mathematical structure is adopted.[2]

Number theory part of Robert Grassmann 1872 has lots of modular arithmetic:

http://mathworld.wolfram.com/Congruence.html

Have skipped bit on divisibility tests that would be based on the following:

https://en.m.wikipedia.org/wiki/Casting_out_nines

http://mathworld.wolfram.com/DivisibilityTests.html

http://mathworld.wolfram.com/DigitSum.html

Reciprocal roots:

http://mathworld.wolfram.com/EgyptianFraction.html

https://en.m.wikipedia.org/wiki/Superparticular_ratio

Greedy Algorithms used for Egyptian fractions, long division, matroids…

http://mathworld.wolfram.com/GreedyAlgorithm.html

Vieta seems to be the key link between medieval and pre-modern just before Grassmanns.

Did polynomials and binomial theorem – links combinatorics to analysis.

https://en.m.wikipedia.org/wiki/François_Viète

Vieta’s Isagogue included in Jacob Klein.

Start from beginning:

@book{book:275047,
title = {A course in combinatorics},
author = {J. H. van Lint, R. M. Wilson},
publisher = {Cambridge University Press},
isbn = {0521803403,9780521803403,9780521006019,9780511672897,0521006015},
year = {2001},
series = {},
edition = {2nd ed},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=565600B8527D62069E673A26C240A3FD}
}

Wikipedia has good summaries:

https://en.m.wikipedia.org/wiki/Combinatorial_principles

https://en.m.wikipedia.org/wiki/Combination

https://en.m.wikipedia.org/wiki/Permutation

https://en.m.wikipedia.org/wiki/Combinatorics

Use modern terminology in summarizing Robert Grassmann on Binding theory.

Clear that this is essential preliminary to Extension theory so worth writing out before studying A1.

Could also be important for understanding more modern aspects of Universal Geometric Calculus. eg

  1. Generalization from Crapo, Brini et al uses “letterplace superalgebras” over Whitney Matroids.
  2. Spectral theory related to modular arithmetic.

Garret Sobczyk (auth.)-New Foundations in Mathematics_ The Geometric Concept of Number-Birkhäuser Basel (2013).pdf

Starts with spectral theory/Chinese Remainder Theorem in modular arithmetic.

The prime factorization of a natural is a (combinatorial) bag of prime powers. Match (bijection) between bags and naturals (also with negatives for rationals in simplest representation with no common factors between numerator and denominator).

Is this some sort of graded algebra?

Projection k is k-vector prime power factor of kth prime.

Projection 0 for scalar is sign?

Adding the k-vector projections is multiplying them.

Scalar inner product is HCF? So orthogonal naturals have HCF of 1?

Square by inner product is a.a = a since HCF idempotent?

Exterior product (wedge!) is LCM?

Geometric product ab = LCM/HCF? (Dualizing somewhere with rationals?) Anti-commutative.

Recover inner and exterior by usual polarities half sum and half difference of geometric and reverersed geometric?

etc etc

Is there a connection with combinadics?

https://en.m.wikipedia.org/wiki/Combinatorial_number_system.

See also primordial and other mixed radix number systems:
https://en.m.wikipedia.org/wiki/Mixed_radix#Primorial_number_system

and factorial number system:

https://en.m.wikipedia.org/wiki/Factorial_number_system

There was some connection between Gian Carlo Rota and Grassmann. Lookup.

Think through later.

Category theorists sometimes mention “combinatorial essence” of proofs. Diagram chasing seems pretty combinatorial. Whole finitist trend of constructive higher order type theory may be combinatorial in the same sort of way as Grassmann equational calculus.

See also Plato’s Parmenides for first proof by complete induction!

H. Crapo (auth.), H. Crapo, D. Senato (eds.)-Algebraic Combinatorics and Computer Science_ A Tribute to Gian-Carlo Rota-Springer-Verlag Mailand (2001).pdf

Includes (Brini et al)

Remarks on invariant geometric calculus. Cayley-Grassmann algebras and geometric Clifford algebras….Pages 129-150
Grassmann geometric calculus, invariant theory and superalgebras….Pages 151-196

@book{book:945516,
title = {Algebraic Combinatorics and Computer Science: A Tribute to Gian-Carlo Rota},
author = {H. Crapo (auth.), H. Crapo, D. Senato (eds.)},
publisher = {Springer-Verlag Mailand},
isbn = {978-88-470-2159-4,978-88-470-2107-5},
year = {2001},
series = {},
edition = {1},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=51161aff15b090a4aa459c0e172df0da}
}

Henry H. Crapo, Gian-Carlo Rota-On The Foundations of Combinatorial Theory_ Combinatorial Geometries-The MIT Press (1970).pdf

@book{book:1207895,
title = {On The Foundations of Combinatorial Theory: Combinatorial Geometries},
author = {Henry H. Crapo, Gian-Carlo Rota},
publisher = {The MIT Press},
isbn = {0262530163,9780262530163},
year = {1970},
series = {},
edition = {Prelim. ed},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=b3ce6c2266bce9655cb809220e9344e5}
}

http://www.maths.ed.ac.uk/~aar/papers/rota2.pdf

The Number of Partitions of a Set. Author(s): Gian-Carlo Rota. Source: The American Mathematical Monthly, Vol. 71, No. 5 (May, 1964), pp. 498-504.

Let’s Expand Rota’s Twelvefold Way For Counting Partitions! Robert A. Proctor 0606404.pdf

https://arxiv.org/abs/math/0606404

http://www.unc.edu/math/Faculty/rap/30fold.html

(Cambridge Mathematical Library) Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan-Combinatorics_ The Rota Way -Cambridge University Press (2009).pdf

@book{book:122564,
title = {Combinatorics: The Rota Way },
author = {Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan},
publisher = {Cambridge University Press},
isbn = {052188389X,9780521883894,052173794X,9780521737944},
year = {2009},
series = {Cambridge Mathematical Library},
edition = {1},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=9D68BCCCA779B1D38F88C72D22145B48}
}

Ian Stewart explains connection of work:

@article{barnabei1985exterior,
  title={On the exterior calculus of invariant theory},
  author={Barnabei, Marilena and Brini, Andrea and Rota, Gian-Carlo},
  journal={Journal of Algebra},
  volume={96},
  number={1},
  pages={120--160},
  year={1985},
  publisher={Academic Press}
}

http://kalx.net/dsS2011/BarBriRot1985.pdf

with Cartan differential forms, Cayley and Sylvester Invariants and Grassmann progressive and regressive product.

@article{stewart1986hermann,
  title={Hermann grassmann was right (News and Views)},
  author={Stewart, I},
  journal={Nature},
  volume={321},
  pages={17},
  year={1986}
}

http://www.nature.com/nature/journal/v321/n6065/pdf/321017a0.pdf

See also Crelle J types of multiplication in A1.

(Cambridge studies in advanced mathematics, 49) Richard P Stanley -Enumerative combinatorics, vol. 1-Cambridge University Press (2011).pdf

“Richard Stanley’s two-volume basic introduction to enumerative combinatorics has become the standard guide to the topic for students and experts alike. This thoroughly revised second edition of Volume 1 includes ten new sections and more than 300 new exercises, most with solutions, reflecting numerous new developments since the publication of the first edition in 1986. The author brings the coverage up to date and includes a wide variety of additional applications and examples, as well as updated and expanded chapter bibliographies. Many of the less difficult new exercises have no solutions so that they can more easily be assigned to students. The material on P-partitions has been rearranged and generalized; the treatment of permutation statistics has been greatly enlarged; and there are also new sections on q-analogues of permutations, hyperplane arrangements, the cd-index, promotion and evacuation and differential posets”– Read more… What is enumerative combinatorics? — Sieve methods — Partially ordered sets — Rational generating functions

@book{book:924553,
title = {Enumerative combinatorics, vol. 1},
author = {Richard P Stanley },
publisher = {Cambridge University Press},
isbn = {9781107015425,1107015421,9781107602625,1107602629},
year = {2011},
series = {Cambridge studies in advanced mathematics, 49},
edition = {2nd ed},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=89d7295bde5a1da4e9eef6db7f412d20}
}

Richard P. Stanley and Sergey P. Fomin-Enumerative Combinatorics_ Volume 2 Edition 1-Cambridge University Press (2001).pdf

This second volume of a two-volume basic introduction to enumerative combinatorics covers the composition of generating functions, trees, algebraic generating functions, D-finite generating functions, noncommutative generating functions, and symmetric functions. The chapter on symmetric functions provides the only available treatment of this subject suitable for an introductory graduate course on combinatorics, and includes the important Robinson-Schensted-Knuth algorithm. Also covered are connections between symmetric functions and representation theory. An appendix by Sergey Fomin covers some deeper aspects of symmetric function theory, including jeu de taquin and the Littlewood-Richardson rule. As in Volume 1, the exercises play a vital role in developing the material. There are over 250 exercises, all with solutions or references to solutions, many of which concern previously unpublished results. Graduate students and research mathematicians who wish to apply combinatorics to their work will find this an authoritative reference.

@book{book:811231,
title = {Enumerative Combinatorics: Volume 2 Edition 1},
author = {Richard P. Stanley and Sergey P. Fomin},
publisher = {Cambridge University Press},
isbn = {0521789877,9780521789875},
year = {2001},
series = {},
edition = {edition1},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=630bda5760d01b5192d66103931a1d68}
}

Stanley R.P.-Enumerative combinatorics, vol. 2_ Supplement (2012).pdf

@book{book:925469,
title = {Enumerative combinatorics, vol. 2: Supplement},
author = {Stanley R.P.},
publisher = {},
isbn = {},
year = {2012},
series = {},
edition = {web version},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=f9ea2e248224806c721890175af8bf0f}
}

Sergey Fomin-Knuth Equivalence, Jeu de Taquin, and the Littlewood-Richardson Rule [Appendix 1 to Chapter 7 in_ R. P. Stanley, Enumerative Combinatorics, vol. 2] (1997).pdf

@book{book:1450167,
title = {Knuth Equivalence, Jeu de Taquin, and the Littlewood-Richardson Rule [Appendix 1 to Chapter 7 in: R. P. Stanley, Enumerative Combinatorics, vol. 2]},
author = {Sergey Fomin},
publisher = {},
isbn = {},
year = {1997},
series = {},
edition = {},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=a68260bc194c340221f1fdd3720ec26d}
}

Richard P. Stanley-Catalan addendum (to_ Enumerative Combinatorics Volume 2) (2013).pdf

@book{book:1604688,
title = {Catalan addendum (to: Enumerative Combinatorics Volume 2)},
author = {Richard P. Stanley},
publisher = {},
isbn = {},
year = {2013},
series = {},
edition = {},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=d4e81020faecda72ee987a849f1246c6}
}

Bogart K.P.-Combinatorics Through Guided Discovery.pdf

Kenneth P. Bogart, 2004. — 190 pages.This book is an introduction to combinatorial mathematics, also known as combinatorics. The book focuses especially but not exclusively on the part of combinatorics that mathematicians refer to as counting. The book consists almost entirely of problems. Some of the problems are designed to lead you to think about a concept, others are designed to help you figure out a concept and state a theorem about it, while still others ask you to prove the theorem. Other problems give you a chance to use a theorem you have proved. From time to time there is a discussion that pulls together some of the things you have learned or introduces a new idea for you to work with. Many of the problems are designed to build up your intuition for how combinatorial mathematics works. There are problems that some people will solve quickly, and there are problems that will take days of thought for everyone. Probably the best way to use this book is to work on a problem until you feel you are not making progress and then go on to the next one. Think about the problem you couldn’t get as you do other things. The next chance you get, discuss the problem you are stymied on with other members of the class. Often you will all feel you’ve hit dead ends, but when you begin comparing notes and listening carefully to each other, you will see more than one approach to the problem and be able to make some progress. In fact, after comparing notes you may realize that there is more than one way to interpret the problem. In this case your first step should be to think together about what the problem is actually asking you to do. You may have learned in school that for every problem you are given, there is a method that has already been taught to you, and you are supposed to figure out which method applies and apply it. That is not the case here. Based on some simplified examples, you will discover the method for yourself. Later on, you may recognize a pattern that suggests you should try to use this method again.

@book{book:1981786,
title = {Combinatorics Through Guided Discovery},
author = {Bogart K.P.},
publisher = {},
isbn = {},
year = {},
series = {},
edition = {},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=ef85ff6a0ee54bf45c72a9c9a895e993}
}

Ronald L. Graham, Donald E. Knuth, Oren Patashnik-Concrete Mathematics_ A Foundation for Computer Science (2nd Edition)-Addison-Wesley Professional (1994).pdf

Table of contents :
Cover……Page 1
Concrete Mathematics (Second edition)……Page 4
Copyright……Page 5
Preface……Page 6
A Note on Notation……Page 11
Contents……Page 13
1.1 The Tower of Hanoi……Page 15
1.2 Lines in the Plane……Page 18
1.3 The Josephus Problem……Page 22
Exercises……Page 31
2.1 Notation……Page 35
2.2 Sums and Recurrences……Page 39
2.3 Manipulation of Sums……Page 44
2.4 Multiple Sums……Page 48
2.5 General Methods……Page 55
2.6 Finite and Infinite Calculus……Page 61
2.7 Infinite Sums……Page 70
Exercises……Page 76
3.1 Floors and Ceilings……Page 81
3.2 Floor/Ceiling Applications……Page 84
3.3 Floor/Ceiling Recurrences……Page 92
3.4 ‘mod’: The Binary Operation……Page 95
3.5 Floor/Ceiling Sums……Page 100
Exercises……Page 109
4.1 Divisibility……Page 116
4.2 Primes……Page 119
4.3 Prime Examples……Page 121
4.4 Factorial Factors……Page 125
4.5 Relative Primality……Page 129
4.6 ‘mod’: The Congruence Relation……Page 137
4.7 Independent Residues……Page 140
4.8 Additional Applications……Page 143
4.9 Phi and Mu……Page 147
Exercises……Page 158
5.1 Basic Identities……Page 167
5.2 Basic Practice……Page 186
5.3 Tricks of the Trade……Page 200
5.4 Generating Functions……Page 210
5.5 Hypergeometric Functions……Page 218
5.6 Hypergeometric Transformations……Page 230
5.7 Partial Hypergeometric Sums……Page 237
5.8 Mechanical Summation……Page 243
Exercises……Page 256
6.1 Stirling Numbers……Page 271
6.2 Eulerian Numbers……Page 281
6.3 Harmonic Numbers……Page 286
6.4 Harmonic Summation……Page 293
6.5 Bernoulli Numbers……Page 297
6.6 Fibonacci Numbers……Page 304
6.7 Continuants……Page 315
Exercises……Page 323
7.1 Domino Theory and Change……Page 334
7.2 Basic Maneuvers……Page 345
7.3 Solving Recurrences……Page 351
7.4 Special Generating Functions……Page 364
7.5 Convolutions……Page 367
7.6 Exponential Generating Functions……Page 378
7.7 Dirichlet Generating Functions……Page 384
Exercises……Page 385
8.1 Definitions……Page 395
8.2 Mean and Variance……Page 401
8.3 Probability Generating Functions……Page 408
8.4 Flipping Coins……Page 415
8.5 Hashing……Page 425
Exercises……Page 441
9 Asymptotics……Page 453
9.1 A Hierarchy……Page 454
9.2 O Notation……Page 457
9.3 O Manipulation……Page 464
9.4 Two Asymptotic Tricks……Page 477
9.5 Euler’s Summation Formula……Page 483
9.6 Final Summations……Page 490
Exercises……Page 503
A. Answers to Exercises……Page 511
B. Bibliography……Page 618
C. Credits for Exercises……Page 646
Index……Page 651
List of Tables……Page 671
Errata, 1994–1997……Page 673

@book{book:833773,
title = {Concrete Mathematics: A Foundation for Computer Science (2nd Edition)},
author = {Ronald L. Graham, Donald E. Knuth, Oren Patashnik},
publisher = {Addison-Wesley Professional},
isbn = {0201558025,9780201558029},
year = {1994},
series = {},
edition = {2},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=5ae3b97e5641dc6ba027477767d1f289}
}

(Graduate Texts in Mathematics, Vol. 203) Bruce Sagan-The Symmetric Group_ Representations, Combinatorial Algorithms, and Symmetric Functions-Springer (2001).djvu

https://www.amazon.com/Symmetric-Group-Representations-Combinatorial-Mathematics/dp/0387950672 $59.49

https://www.bookdepository.com/Symmetric-Group-Bruce-E-Sagan/9780387950679 AUD$75.89

This book brings together many of the important results in this field.
From the reviews: “”A classic gets even better….The edition has new material including the Novelli-Pak-Stoyanovskii bijective proof of the hook formula, Stanley’s proof of the sum of squares formula using differential posets, Fomin’s bijective proof of the sum of squares formula, group acting on posets and their use in proving unimodality, and chromatic symmetric functions.” –ZENTRALBLATT MATH

@book{book:1388622,
title = {The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions},
author = {Bruce Sagan},
publisher = {Springer},
isbn = {0387950672,9780387950679},
year = {2001},
series = {Graduate Texts in Mathematics, Vol. 203},
edition = {2nd},
volume = {},
url = {http://gen.lib.rus.ec/book/index.php?md5=c20c8ee8e38f27d18f9e01a6eee3fb35}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s