597:
211:
158:
592:{\displaystyle {\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}}}
727:
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
171:
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
827:
216:
843:
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
699:, 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.
111:
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
166:
43:
866:
664:
115:
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
74:
890:
743:
608:
708:
78:
89:
are powerful tools that can be used to manipulate sequences, and can describe if not resolve many combinatorial situations.
62:
often ascertains the existence of something or is used to determine the minimum or maximum number of something in a
47:
70:
885:
844:
713:
The method of distinguished element singles out a "distinguished element" of a set to prove some result.
669:
Double counting is a technique that equates two expressions that count the size of a set in two ways.
678:
63:
59:
838:
722:
86:
82:
652:
862:
646:
128:
51:
39:
879:
116:
20:
651:
Bijective proofs prove that two sets have the same number of elements by finding a
157:
617:
ways to do a task if it can be done using a procedure that can be carried out in
98:
55:
35:
133:
The rule of product is another intuitive principle stating that if there are
103:
The rule of sum is an intuitive principle stating that if there are
156:
107:
possible outcomes for an event (or ways to do something) and
822:{\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}
54:
are utilized to demonstrate that two sets have the same
655:(one-to-one correspondence) from one set to the other.
188:, minus the number of elements in their intersection.
746:
214:
821:
591:
180:is equal to the sum of the number of elements in
847:for the terms of a sequence are more desired.
161:Inclusion–exclusion illustrated for three sets
8:
861:(2nd ed.). Cambridge University Press.
613:The rule of division states that there are
191:Generally, according to this principle, if
810:
800:
790:
779:
757:
745:
571:
552:
531:
488:
475:
462:
423:
419:
403:
393:
375:
362:
329:
325:
315:
298:
284:
273:
264:
249:
239:
228:
215:
213:
141:ways to do another thing, then there are
683:The pigeonhole principle states that if
857:van Lint, J.H.; Wilson, R.M. (2001).
119:is equal to the size of their union.
7:
791:
31:are commonly recognized and used.
14:
665:Double counting (proof technique)
609:Rule of division (combinatorics)
709:Method of distinguished element
703:Method of distinguished element
687:items are each put into one of
395:
79:method of distinguished element
769:
750:
1:
167:Inclusion–exclusion principle
153:Inclusion–exclusion principle
44:inclusion–exclusion principle
16:Methods used in combinatorics
907:
836:
720:
706:
676:
662:
644:
606:
164:
126:
96:
859:A Course in Combinatorics
137:ways to do something and
621:ways, and for every way
149:ways to do both things.
71:combinatorial identities
29:combinatorial principles
891:Mathematical principles
845:closed-form expressions
728:function of a sequence
633:ways correspond to way
823:
795:
593:
289:
244:
205:are finite sets, then
162:
19:In proving results in
824:
775:
594:
269:
224:
160:
744:
679:Pigeonhole principle
673:Pigeonhole principle
212:
87:recurrence relations
83:Generating functions
60:pigeonhole principle
839:Recurrence relation
833:Recurrence relation
723:Generating function
717:Generating function
46:are often used for
25:combinatorial rules
819:
653:bijective function
589:
587:
452:
352:
163:
56:number of elements
510:
504:
399:
311:
898:
872:
828:
826:
825:
820:
815:
814:
805:
804:
794:
789:
762:
761:
603:Rule of division
598:
596:
595:
590:
588:
581:
577:
576:
575:
557:
556:
542:
541:
530:
526:
508:
502:
498:
494:
493:
492:
480:
479:
467:
466:
451:
394:
389:
385:
381:
380:
379:
367:
366:
351:
307:
303:
302:
288:
283:
265:
259:
255:
254:
253:
243:
238:
52:Bijective proofs
906:
905:
901:
900:
899:
897:
896:
895:
876:
875:
869:
856:
853:
841:
835:
806:
796:
753:
742:
741:
736:
725:
719:
711:
705:
681:
675:
667:
661:
659:Double counting
649:
647:Bijective proof
643:
641:Bijective proof
611:
605:
586:
585:
567:
548:
547:
543:
519:
515:
514:
484:
471:
458:
457:
453:
387:
386:
371:
358:
357:
353:
294:
290:
260:
245:
223:
219:
210:
209:
203:
197:
169:
155:
131:
129:Rule of product
125:
123:Rule of product
101:
95:
77:methods or the
75:double counting
40:rule of product
23:several useful
17:
12:
11:
5:
904:
902:
894:
893:
888:
878:
877:
874:
873:
867:
852:
849:
837:Main article:
834:
831:
830:
829:
818:
813:
809:
803:
799:
793:
788:
785:
782:
778:
774:
771:
768:
765:
760:
756:
752:
749:
732:
721:Main article:
718:
715:
707:Main article:
704:
701:
677:Main article:
674:
671:
663:Main article:
660:
657:
645:Main article:
642:
639:
607:Main article:
604:
601:
600:
599:
584:
580:
574:
570:
566:
563:
560:
555:
551:
546:
540:
537:
534:
529:
525:
522:
518:
513:
507:
501:
497:
491:
487:
483:
478:
474:
470:
465:
461:
456:
450:
447:
444:
441:
438:
435:
432:
429:
426:
422:
418:
415:
412:
409:
406:
402:
398:
392:
390:
388:
384:
378:
374:
370:
365:
361:
356:
350:
347:
344:
341:
338:
335:
332:
328:
324:
321:
318:
314:
310:
306:
301:
297:
293:
287:
282:
279:
276:
272:
268:
263:
261:
258:
252:
248:
242:
237:
234:
231:
227:
222:
218:
217:
201:
195:
165:Main article:
154:
151:
127:Main article:
124:
121:
97:Main article:
94:
91:
15:
13:
10:
9:
6:
4:
3:
2:
903:
892:
889:
887:
886:Combinatorics
884:
883:
881:
870:
868:0-521-00601-5
864:
860:
855:
854:
850:
848:
846:
840:
832:
816:
811:
807:
801:
797:
786:
783:
780:
776:
772:
766:
763:
758:
754:
747:
740:
739:
738:
735:
731:
724:
716:
714:
710:
702:
700:
698:
694:
691:boxes, where
690:
686:
680:
672:
670:
666:
658:
656:
654:
648:
640:
638:
636:
632:
628:
624:
620:
616:
610:
602:
582:
578:
572:
568:
564:
561:
558:
553:
549:
544:
538:
535:
532:
527:
523:
520:
516:
511:
505:
499:
495:
489:
485:
481:
476:
472:
468:
463:
459:
454:
448:
445:
442:
439:
436:
433:
430:
427:
424:
420:
416:
413:
410:
407:
404:
400:
396:
391:
382:
376:
372:
368:
363:
359:
354:
348:
345:
342:
339:
336:
333:
330:
326:
322:
319:
316:
312:
308:
304:
299:
295:
291:
285:
280:
277:
274:
270:
266:
262:
256:
250:
246:
240:
235:
232:
229:
225:
220:
208:
207:
206:
204:
194:
189:
187:
183:
179:
175:
168:
159:
152:
150:
148:
145: ·
144:
140:
136:
130:
122:
120:
118:
117:disjoint sets
114:
110:
106:
100:
92:
90:
88:
84:
80:
76:
72:
67:
65:
61:
57:
53:
49:
45:
41:
37:
32:
30:
26:
22:
21:combinatorics
858:
842:
733:
729:
726:
712:
696:
692:
688:
684:
682:
668:
650:
634:
630:
626:
622:
618:
614:
612:
199:
192:
190:
185:
181:
177:
173:
170:
146:
142:
138:
134:
132:
112:
108:
104:
102:
68:
33:
28:
24:
18:
99:Rule of sum
93:Rule of sum
73:arise from
48:enumerative
36:rule of sum
880:Categories
851:References
625:, exactly
66:context.
50:purposes.
792:∞
777:∑
565:∩
562:⋯
559:∩
536:−
521:−
506:⋯
500:−
482:∩
469:∩
446:≤
428:≤
401:∑
369:∩
346:≤
334:≤
313:∑
309:−
271:∑
226:⋃
64:discrete
629:of the
865:
509:
503:
58:. The
42:, and
695:>
198:, …,
113:a + b
69:Many
863:ISBN
440:<
434:<
340:<
184:and
176:and
85:and
34:The
737:is
615:n/d
27:or
882::
637:.
81:.
38:,
871:.
817:.
812:n
808:x
802:n
798:a
787:0
784:=
781:n
773:=
770:)
767:x
764:;
759:n
755:a
751:(
748:G
734:n
730:a
697:b
693:a
689:b
685:a
635:w
631:n
627:d
623:w
619:n
583:.
579:|
573:n
569:A
554:1
550:A
545:|
539:1
533:n
528:)
524:1
517:(
512:+
496:|
490:k
486:A
477:j
473:A
464:i
460:A
455:|
449:n
443:k
437:j
431:i
425:1
421::
417:k
414:,
411:j
408:,
405:i
397:+
383:|
377:j
373:A
364:i
360:A
355:|
349:n
343:j
337:i
331:1
327::
323:j
320:,
317:i
305:|
300:i
296:A
292:|
286:n
281:1
278:=
275:i
267:=
257:|
251:i
247:A
241:n
236:1
233:=
230:i
221:|
202:n
200:A
196:1
193:A
186:B
182:A
178:B
174:A
147:b
143:a
139:b
135:a
109:b
105:a
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
