Summary
In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof: A proof by double counting. A combinatorial identity is proven by counting the number of elements of some carefully chosen set in two different ways to obtain the different expressions in the identity. Since those expressions count the same objects, they must be equal to each other and thus the identity is established. A bijective proof. Two sets are shown to have the same number of members by exhibiting a bijection, i.e. a one-to-one correspondence, between them. The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof in combinatorics. However, as writes in his review of (a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory. An archetypal double counting proof is for the well known formula for the number of k-combinations (i.e., subsets of size k) of an n-element set: Here a direct bijective proof is not possible: because the right-hand side of the identity is a fraction, there is no set obviously counted by it (it even takes some thought to see that the denominator always evenly divides the numerator). However its numerator counts the Cartesian product of k finite sets of sizes n, n − 1, ..., n − k + 1, while its denominator counts the permutations of a k-element set (the set most obviously counted by the denominator would be another Cartesian product k finite sets; if desired one could map permutations to that set by an explicit bijection). Now take S to be the set of sequences of k elements selected from our n-element set without repetition. On one hand, there is an easy bijection of S with the Cartesian product corresponding to the numerator , and on the other hand there is a bijection from the set C of pairs of a k-combination and a permutation σ of k to S, by taking the elements of C in increasing order, and then permuting this sequence by σ to obtain an element of S.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (3)
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
MATH-101(e): Analysis I
Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable.
MATH-110(a): Advanced linear algebra I
L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux de ce sujet.
Related lectures (34)
Combinatorial Proofs: Frobenius Theorem
Explores combinatorial proofs for the Frobenius Theorem, demonstrating mathematical reasoning and calculations.
Algebraic Identities and Trigonometry
Covers algebraic identities, trigonometry, and real functions, including injective, surjective, bijective, and reciprocal functions.
Counting Poker Dices: Combinatorial and Analytical Proofs
Explores cable connections, poker dice rolls, and analytical proofs in mathematics.
Show more
Related publications (13)

Computational Imaging SPAD Cameras

Andrei Ardelean

Vision systems built around conventional image sensors have to read, encode and transmit large quantities of pixel information, a majority of which is redundant. As a result, new computational imaging sensor architectures were developed to preprocess the r ...
EPFL2023

Computation of Al-Salam Carlitz and Askey-Wilson moments using Motzkin paths

Gaspard Ohlmann

In this paper we study the moments of polynomials from the Askey scheme, and we focus on Askey-Wilson polynomials. More precisely, we give a combinatorial proof for the case where d = 0. Their values have already been computed by Kim and Stanton in 2015, h ...
ELECTRONIC JOURNAL OF COMBINATORICS2021

A combinatorial proof of a sumset conjecture of Furstenberg

Florian Karl Richter

We give a new proof of a sumset conjecture of Furstenberg that was first proved by Hochman and Shmerkin in 2012: if logr/logs\log r / \log s is irrational and XX and YY are ×r\times r- and ×s\times s-invariant subsets of [0,1][0,1], respectively, then $\dim_\text{ ...
2021
Show more
Related concepts (4)
Combinatorial principles
In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion–exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets have the same number of elements. The pigeonhole principle often ascertains the existence of something or is used to determine the minimum or maximum number of something in a discrete context.
Binomial coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n; this coefficient can be computed by the multiplicative formula which using factorial notation can be compactly expressed as For example, the fourth power of 1 + x is and the binomial coefficient is the coefficient of the x2 term.
Generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers (an) by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.