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.

Many combinatorial identities arise from double counting methods or the method of distinguished element. Generating functions and recurrence relations are powerful tools that can be used to manipulate sequences, and can describe if not resolve many combinatorial situations.

Rule of sum

The rule of sum is an intuitive principle stating that if there are a possible outcomes for an event (or ways to do something) and b possible outcomes for another event (or ways to do another thing), and the two events cannot both occur (or the two things can't both be done), then there are a + b total possible outcomes for the events (or total possible ways to do one of the things). More formally, the sum of the sizes of two disjoint sets is equal to the size of their union.

Rule of product

The rule of product is another intuitive principle stating that if there are a ways to do something and b ways to do another thing, then there are a · b ways to do both things.

Inclusion–exclusion principle

Inclusion–exclusion illustrated for three sets

The inclusion–exclusion principle relates the size of the union of multiple sets, the size of each set, and the size of each possible intersection of the sets. The smallest example is when there are two sets: the number of elements in the union of A and B is equal to the sum of the number of elements in A and B, minus the number of elements in their intersection.

Generally, according to this principle, if A₁, …, A_n are finite sets, then

{\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}

Rule of division

The rule of division states that there are n/d ways to do a task if it can be done using a procedure that can be carried out in n ways, and for every way w, exactly d of the n ways correspond to way w.

Bijective proof

Bijective proofs prove that two sets have the same number of elements by finding a bijective function (one-to-one correspondence) from one set to the other.

Double counting

Double counting is a technique that equates two expressions that count the size of a set in two ways.

Pigeonhole principle

The pigeonhole principle states that if a items are each put into one of b boxes, where a > b, then one of the boxes contains more than one item. Using this one can, for example, demonstrate the existence of some element in a set with some specific properties.

Method of distinguished element

The method of distinguished element singles out a "distinguished element" of a set to prove some result.

Generating function

Generating functions can be thought of as polynomials with infinitely many terms whose coefficients correspond to terms of a sequence. This new representation of the sequence opens up new methods for finding identities and closed forms pertaining to certain sequences. The (ordinary) generating function of a sequence a_n is

G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.

Recurrence relation

A recurrence relation defines each term of a sequence in terms of the preceding terms. Recurrence relations may lead to previously unknown properties of a sequence, but generally closed-form expressions for the terms of a sequence are more desired.

References

van Lint, J.H.; Wilson, R.M. (2001). A Course in Combinatorics (2nd ed.). Cambridge University Press. ISBN 0-521-00601-5.

Read other articles:

Minamimaki, Nagano

Minamimaki 南牧村DesaMinamimaki Village Hall BenderaLambangLokasi Minamimaki di Prefektur NaganoMinamimaki Koordinat: 36°1′15″N 138°29′31.7″E / 36.02083°N 138.492139°E / 36.02083; 138.492139Koordinat: 36°1′15″N 138°29′31.7″E / 36.02083°N 138.492139°E / 36.02083; 138.492139NegaraJepangWilayahChūbu (Kōshin'etsu)PrefekturNaganoDistrikMinamisakuLuas • Total133,09 km2 (5,139 sq mi)Populasi&...

Spencer Perceval

Spencer Perceval Perdana Menteri Britania RayaMasa jabatan4 Oktober 1809 – 11 Mei 1812Penguasa monarkiGeorge III (dan Pangeran Bupati) PendahuluThe Duke of PortlandPenggantiThe Earl of LiverpoolMenteri Keuangan Britania RayaMasa jabatan26 Maret 1807 – 11 Mei 1812Penguasa monarkiGeorge III (dan Pangeran Bupati) PendahuluLord Henry PettyPenggantiNicholas Vansittart Informasi pribadiLahir(1762-11-01)1 November 1762Bujur Sangkar Audley, LondonMeninggal11 Mei 1812(1812-05-11)...

Real estate in Puerto Rico

Real estate industry in Puerto Rico This article may contain an excessive amount of intricate detail that may interest only a particular audience. Please help by spinning off or relocating any relevant information, and removing excessive detail that may be against Wikipedia's inclusion policy. (September 2013) (Learn how and when to remove this template message) Finance, insurance, and real estate constitutes 19.5% of the gross domestic product of Puerto Rico. Part of a series on theEconomy o...

John G. Jackson (politician)

American judge (1777–1825) John G. JacksonJudge of the United States District Court for the Western District of VirginiaIn officeFebruary 24, 1819 – March 28, 1825Appointed byJames MonroePreceded bySeat established by 3 Stat. 478Succeeded byPhilip C. PendletonMember of the U.S. House of Representativesfrom Virginia's 1st districtIn officeMarch 4, 1813 – March 3, 1817Preceded byThomas WilsonSucceeded byJames PindallIn officeMarch 4, 1803 – Septemb...

Don Ameche

Don Ameche pada tahun 1964 Don Ameche (31 Mey 1908 - 6 Desember 1993) adalah seorang aktor yang populer pada tahun 1930-an dan 1940-an.[1] Ia juga populer sebagai penyiar radio pada zamannya.[1] Ia memulai debutnya dalam film melalui film pendek Beauty at the World's Fair (1933).[1] Setelah itu, ia pindah ke Hollywood untuk melakukan tes di studio MGM.[1] Akan tetapi, MGM menolaknya. Lalu, pada tahun 1935 ia berhasil mendapatkan peran kecil di Clive of India da...

Sayur asam

Sayur asamSayur asamSajianhidangan utamaTempat asalIndonesia[1]DaerahJakarta, Jawa Barat, BantenSuhu penyajianpanas dan suhu ruangBahan utamaberbagai jenis sayuran dalam sup asamSunting kotak info • L • BBantuan penggunaan templat ini Media: Sayur asam Bumbu untuk sayur asam Sayur asam atau sayur asem adalah masakan sejenis sayur yang khas Indonesia. Ada banyak variasi lokal sayur asam seperti sayur asam Jakarta (variasi dari orang Betawi di Jakarta), sayur asa...

Sculpture

Pour les articles homonymes, voir Sculpture (homonymie). Sculpture en ronde-bosse : David de Michel-Ange. La sculpture est une activité artistique qui consiste à concevoir et réaliser des formes en volume, en relief, soit en ronde-bosse (statuaire), en haut-relief, en bas-relief, par modelage, par taille directe, par soudure ou assemblage. Le terme de sculpture désigne également l'objet résultant de cette activité. Le mot sculpture vient étymologiquement du latin « sculper...

Guido Sforza Gonzaga

Questa voce sugli argomenti militari italiani e nobili italiani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. A questa voce o sezione va aggiunto il template sinottico {{Militare}} Puoi aggiungere e riempire il template secondo le istruzioni e poi rimuovere questo avviso. Se non sei in grado di riempirlo in buona parte, non fare nulla; non inserire template vuoti. Guido Sforza Gon...

Anglicisme

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (janvier 2021). Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes. Exemple d'anglicisme : people, abréviation d...

Renan Abner do Carmo de Oliveira

Questa voce sull'argomento calciatori brasiliani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Renan de Oliveira Nazionalità Brasile Altezza 186 cm Peso 84 kg Calcio Ruolo Attaccante Squadra Sarajevo Carriera Giovanili Juventus-SP São Bernardo Squadre di club1 2017-2018→ ViOn Z.M.4 (0)2018-2019 Mosta9 (2)2019 San Ġwann12 (10)2019-2020 L'viv27 (6)2020-2...

M14 rifle

American battle rifle M14 rifle An M14 rifle shown with a 20-round magazineTypeBattle riflePlace of originUnited StatesService historyIn service1957–present1957–1964 (as the standard U.S. service rifle)[1]Used bySee UsersWarsSee ConflictsProduction historyDesigned1954ManufacturerSpringfield ArmoryWinchesterHarrington & RichardsonThompson-Ramo-Wooldridge, Inc.Produced1959–1980[2][3]No. built1.3 million[4]VariantsSee VariantsSpe...

Andreas Brehme

German footballer (1960–2024) Andreas Brehme Brehme with Germany in 1994Personal informationDate of birth (1960-11-09)9 November 1960[1]Place of birth Hamburg, West GermanyDate of death 20 February 2024(2024-02-20) (aged 63)Place of death Munich, GermanyHeight 1.76 m (5 ft 9 in)Position(s) Left-back, left wing-back, defensive midfielderYouth career1965–1978 HSV Barmbek-UhlenhorstSenior career*Years Team Apps (Gls)1978–1980 HSV Barmbek-Uhlenhorst 66 (10)1980�...

Повітряні сили Збройних сил України

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Мат...

Carlos Monzón

Argentine boxer (1942–1995) Carlos MonzónMonzón in 1974BornCarlos Roque Monzón(1942-08-07)7 August 1942San Javier, ArgentinaDied8 January 1995(1995-01-08) (aged 52)Santa Rosa de Calchines, ArgentinaOther namesEscopetaStatisticsWeight(s)MiddleweightHeight181 cm (5 ft 11 in)Reach193 cm (76 in)StanceOrthodox Boxing recordTotal fights100Wins87Wins by KO59Losses3Draws9No contests1 Carlos Roque Monzón (7 August 1942 – 8 January 1995), nicknamed Escopeta (S...

Венгер, Леонид Абрамович

В Википедии есть статьи о других людях с такой фамилией, см. Венгер. Леонид Абрамович Венгер Дата рождения 26 мая 1925(1925-05-26) Место рождения Харьков Дата смерти 17 июня 1992(1992-06-17) (67 лет) Место смерти Москва Страна СССР Род деятельности психолог Научная сфера возраст�...

Postal codes in Vietnam

Postal codes in Vietnam have five digits.[1] The exact postal code designated for local government areas, local post offices, government offices or embassies and consulates can be searched on National Postal Code Website.Regional and provincial postal codes of Viet Nam Structure The postal code system of Vietnam has officially been changed from 6 digits to 5 digits. Each country has its own separate postal code or zip code system. The postal code of Vietnam is composed of 5 digits, w...

Cuba en los Juegos Olímpicos de México 1968

Cuba en los Juegos Olímpicos Bandera de CubaCódigo COI CUBCON Comité Olímpico CubanoJuegos Olímpicos de México 1968Deportistas 115 en 13 deportesAbanderado Héctor RamírezMedallasPuesto: 31 0 4 0 4 Historia olímpicaJuegos de verano 1900 • 1904 • 1908 • 1912 • 1920 • 1924 • 1928 • 1932 • 1936 • 1948 • 1952 • 1956 • 1960 • 1964 • ...

Uppsala Synod

1593 synod of the Church of Sweden You can help expand this article with text translated from the corresponding article in Swedish. (April 2024) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Consider adding a ...

88 Greenwich Street

Residential skyscraper in Manhattan, New York 88 Greenwich StreetAlternative namesGreenwich Club Residences19 Rector StreetGeneral informationTypeResidentialArchitectural styleArt DecoLocation88 Greenwich StreetManhattan, New York CityCoordinates40°42′28.5″N 74°0′51″W / 40.707917°N 74.01417°W / 40.707917; -74.01417Construction started1929Completed1930OwnerThor Equities[2]HeightRoof466 ft (142 m)Top floor427 ft (130 m)Technical de...

Колобжег

У этого термина существуют и другие значения, см. Колобжег (значения). ГородКолобжегKołobrzeg Флаг[вд] Герб 54°10′ с. ш. 15°34′ в. д.HGЯO Страна Польша Воеводство Западно-Поморское Повят Колобжегский Президент города Анна Миечковская История и география Основан 1000 Пр...