39:
that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into
651:
Problems that admit bijective proofs are not limited to binomial coefficient identities. As the complexity of the problem increases, a bijective proof can become very sophisticated. This technique is particularly useful in areas of
641:
129:
346:
285:
567:
and thus a bijection. The result now follows since the existence of a bijection between these finite sets shows that they have the same size, that is,
877:
811:
792:
703:
570:
920:
831:
748:
743:
59:
823:
857:
925:
689:
302:
246:
718:
900:
753:
367:
199:
More abstractly and generally, the two quantities asserted to be equal count the subsets of size
870:"Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees"
483:), using the fact that the complement of a complement of a set is the original set, to obtain
845:
869:
653:
8:
758:
679:
391:
32:
31:
technique for proving that two sets have equally many elements, or that the sets in two
850:
504:
36:
28:
675:
827:
819:
788:
711:
889:
882:
763:
738:
693:
878:"Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials"
697:
725:
914:
707:
665:
657:
174:
The key idea of the proof may be understood from a simple example: selecting
20:
683:
661:
671:
The most classical examples of bijective proofs in combinatorics include:
135:
904:
48:
894:
862:
710:, giving a proof of a classical result on the number of certain
180:
children to be rewarded with ice cream cones, out of a group of
186:
children, has exactly the same effect as choosing instead the
564:
815:
787:, The Mathematical Association of America, p. 28,
602:
575:
307:
251:
53:
The symmetry of the binomial coefficients states that
858:"A direct bijective proof of the hook-length formula"
573:
305:
249:
62:
636:{\displaystyle {\tbinom {n}{k}}={\tbinom {n}{n-k}}}
438:. To show that f is a bijection, first assume that
348:. There is a simple bijection between the two sets
635:
340:
279:
123:
112:
91:
79:
66:
49:Proving the symmetry of the binomial coefficients
912:
124:{\displaystyle {n \choose k}={n \choose n-k}.}
626:
605:
591:
578:
331:
310:
267:
254:
390:. More formally, this can be written using
134:This means that there are exactly as many
16:Technique for proving sets have equal size
370:, which contains precisely the remaining
724:Bijective proofs of the formula for the
479:. Take the complements of each side (in
196:children to be denied ice cream cones.
537:-element subset, and so, an element of
913:
362:-element subset (that is, a member of
782:
169:
13:
804:
609:
582:
341:{\displaystyle {\tbinom {n}{n-k}}}
314:
258:
95:
70:
14:
937:
901:Garsia-Milne Involution Principle
838:
749:Double counting (proof technique)
646:
280:{\displaystyle {\tbinom {n}{k}}.}
43:
890:"Partition Bijections, a Survey"
776:
35:have equal size, by finding a
1:
785:Combinatorics / A Guided Tour
769:
160:things in a set of size
150:as there are combinations of
810:Loehr, Nicholas A. (2011).
690:Robinson-Schensted algorithm
434:and the complement taken in
7:
732:
386:, and hence is a member of
10:
942:
744:Schröder–Bernstein theorem
40:each or both of the sets.
921:Enumerative combinatorics
719:pentagonal number theorem
783:Mazur, David R. (2010),
754:Combinatorial principles
717:Bijective proofs of the
144:things in a set of size
873:– by Gilles Schaeffer.
812:Bijective Combinatorics
215:, respectively, of any
637:
356:: it associates every
342:
281:
125:
638:
343:
299:, the set B has size
282:
126:
33:combinatorial classes
692:, giving a proof of
678:, giving a proof of
654:discrete mathematics
571:
523:. Its complement in
303:
247:
235:-element subsets of
60:
926:Mathematical proofs
846:"Division by three"
759:Combinatorial proof
696:'s formula for the
511:-element subset of
430:-element subset of
392:functional notation
375: −
210: −
191: −
155: −
712:integer partitions
682:for the number of
633:
631:
596:
499:. This shows that
463:, that is to say,
338:
336:
291:be the set of all
277:
272:
231:be the set of all
121:
37:bijective function
794:978-0-88385-762-5
624:
589:
329:
265:
170:A bijective proof
110:
77:
933:
883:Doron Zeilberger
865:and Stoyanovsky.
798:
797:
780:
764:Categorification
739:Binomial theorem
680:Cayley's formula
642:
640:
639:
634:
632:
630:
629:
623:
608:
597:
595:
594:
581:
562:
558:
540:
536:
532:
526:
522:
518:
514:
510:
502:
498:
482:
478:
462:
437:
433:
429:
425:
421:
407:
389:
385:
379:
365:
361:
355:
351:
347:
345:
344:
339:
337:
335:
334:
328:
313:
298:
294:
290:
286:
284:
283:
278:
273:
271:
270:
257:
242:
238:
234:
230:
226:
220:
214:
204:
195:
185:
179:
165:
159:
149:
143:
130:
128:
127:
122:
117:
116:
115:
109:
94:
84:
83:
82:
69:
941:
940:
936:
935:
934:
932:
931:
930:
911:
910:
861:– by Novelli,
849:– by Doyle and
841:
807:
805:Further reading
802:
801:
795:
781:
777:
772:
735:
726:Catalan numbers
698:symmetric group
676:Prüfer sequence
649:
625:
613:
604:
603:
601:
590:
577:
576:
574:
572:
569:
568:
560:
542:
538:
534:
528:
524:
520:
516:
512:
508:
507:. Now take any
500:
497:
490:
484:
480:
477:
470:
464:
460:
449:
439:
435:
431:
427:
423:
409:
395:
387:
381:
371:
363:
357:
353:
349:
330:
318:
309:
308:
306:
304:
301:
300:
296:
292:
288:
266:
253:
252:
250:
248:
245:
244:
240:
236:
232:
228:
222:
216:
206:
200:
187:
181:
175:
172:
161:
151:
145:
139:
111:
99:
90:
89:
88:
78:
65:
64:
63:
61:
58:
57:
51:
46:
25:bijective proof
17:
12:
11:
5:
939:
929:
928:
923:
909:
908:
898:
886:
874:
866:
854:
840:
839:External links
837:
836:
835:
832:978-1439848845
806:
803:
800:
799:
793:
774:
773:
771:
768:
767:
766:
761:
756:
751:
746:
741:
734:
731:
730:
729:
722:
715:
708:Young diagrams
701:
687:
648:
647:Other examples
645:
628:
622:
619:
616:
612:
607:
600:
593:
588:
585:
580:
495:
488:
475:
468:
458:
447:
333:
327:
324:
321:
317:
312:
276:
269:
264:
261:
256:
171:
168:
132:
131:
120:
114:
108:
105:
102:
98:
93:
87:
81:
76:
73:
68:
50:
47:
45:
44:Basic examples
42:
15:
9:
6:
4:
3:
2:
938:
927:
924:
922:
919:
918:
916:
906:
902:
899:
896:
892:
891:
887:
884:
880:
879:
875:
872:
871:
867:
864:
860:
859:
855:
852:
848:
847:
843:
842:
833:
829:
825:
821:
817:
813:
809:
808:
796:
790:
786:
779:
775:
765:
762:
760:
757:
755:
752:
750:
747:
745:
742:
740:
737:
736:
727:
723:
720:
716:
713:
709:
705:
702:
699:
695:
691:
688:
685:
684:labeled trees
681:
677:
674:
673:
672:
669:
667:
666:number theory
663:
659:
658:combinatorics
655:
644:
620:
617:
614:
610:
598:
586:
583:
566:
557:
553:
549:
545:
531:
506:
494:
487:
474:
467:
457:
453:
446:
442:
420:
416:
412:
406:
402:
398:
393:
384:
378:
374:
369:
360:
325:
322:
319:
315:
274:
262:
259:
225:
221:-element set
219:
213:
209:
203:
197:
194:
190:
184:
178:
167:
164:
158:
154:
148:
142:
137:
118:
106:
103:
100:
96:
85:
74:
71:
56:
55:
54:
41:
38:
34:
30:
26:
22:
21:combinatorics
888:
876:
868:
856:
844:
784:
778:
670:
662:graph theory
650:
555:
551:
547:
543:
529:
492:
485:
472:
465:
455:
451:
444:
440:
418:
414:
410:
404:
400:
396:
382:
380:elements of
376:
372:
358:
223:
217:
211:
207:
201:
198:
192:
188:
182:
176:
173:
162:
156:
152:
146:
140:
136:combinations
133:
52:
24:
18:
704:Conjugation
408:defined by
366:) with its
295:subsets of
915:Categories
824:143984884X
770:References
505:one-to-one
368:complement
239:, the set
905:MathWorld
816:CRC Press
618:−
323:−
243:has size
104:−
895:Igor Pak
733:See also
694:Burnside
656:such as
563:is also
541:. Since
399: :
903:– from
533:, is a
851:Conway
830:
822:
791:
664:, and
519:, say
227:. Let
893:– by
881:– by
550:) = (
29:proof
27:is a
828:ISBN
820:ISBN
789:ISBN
565:onto
554:) =
450:) =
426:any
422:for
417:) =
394:as,
352:and
287:Let
205:and
863:Pak
826:,
818:.
814:.
706:of
515:in
509:n−k
503:is
293:n−k
138:of
19:In
917::
668:.
660:,
643:.
559:,
527:,
491:=
471:=
403:→
166:.
23:,
907:.
897:.
885:.
853:.
834:.
728:.
721:.
714:.
700:.
686:.
627:)
621:k
615:n
611:n
606:(
599:=
592:)
587:k
584:n
579:(
561:f
556:Y
552:Y
548:Y
546:(
544:f
539:A
535:k
530:Y
525:S
521:Y
517:B
513:S
501:f
496:2
493:X
489:1
486:X
481:S
476:2
473:X
469:1
466:X
461:)
459:2
456:X
454:(
452:f
448:1
445:X
443:(
441:f
436:S
432:S
428:k
424:X
419:X
415:X
413:(
411:f
405:B
401:A
397:f
388:B
383:S
377:k
373:n
364:A
359:k
354:B
350:A
332:)
326:k
320:n
316:n
311:(
297:S
289:B
275:.
268:)
263:k
260:n
255:(
241:A
237:S
233:k
229:A
224:S
218:n
212:k
208:n
202:k
193:k
189:n
183:n
177:k
163:n
157:k
153:n
147:n
141:k
119:.
113:)
107:k
101:n
97:n
92:(
86:=
80:)
75:k
72:n
67:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.