747:, Encyclopedia of Mathematics and Its Applications, vol. 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.),
784:
715:
756:
691:
486:
54:
686:
748:
268:
80:
47:
263:. The name "shuffle product" refers to the fact that the product can be thought of as a sum over all ways of
84:
76:
668:, Textos de Matemática. Série B, vol. 9, Coimbra: Universidade de Coimbra Departamento de Matemática,
836:
831:
610:
557:
79:; this is because it is able to preserve the relative order of factors being multiplied together - the
681:
276:
272:
635:
574:
65:
780:
752:
711:
627:
605:
798:
779:, London Mathematical Society Monographs. New Series, vol. 7, Oxford University Press,
762:
729:
703:
651:
619:
601:
590:
566:
58:
794:
725:
673:
647:
586:
555:(1958), "Free differential calculus. IV. The quotient groups of the lower central series",
802:
790:
766:
733:
721:
669:
655:
643:
594:
582:
491:
304:
264:
825:
702:, Mathematical Surveys and Monographs, vol. 168, American Mathematical Society,
816:
552:
237:
24:
774:
663:
740:
69:
27:
with a basis corresponding to words on some set, whose product is given by the
631:
548:
46:: the sum of all ways of interlacing them. The interlacing is given by the
282:
The shuffle product of two words in some alphabet is often denoted by the
297:
134:
ways of interleaving the two words, as shown in the following examples:
707:
639:
578:
287:
623:
570:
64:
Over the rational numbers, the shuffle algebra is isomorphic to the
698:
Hazewinkel, Michiel; Gubareni, Nadiya; Kirichenko, V. V. (2010),
477:
The infiltration product is also commutative and associative.
53:
The shuffle algebra on a finite set is the graded dual of the
700:
Algebras, rings and modules. Lie algebras and Hopf algebras
87:, which becomes appropriate when factors are commutative.
323:. It is defined inductively on words over an alphabet
75:The shuffle product occurs in generic settings in
665:Shuffle algebras, Lie algebras and quantum groups
260:
320:
8:
534:
522:
510:
95:The shuffle product of words of lengths
503:
608:(1953), "On the groups of H(Π,n). I",
259:The shuffle product was introduced by
83:. This can be held in contrast to the
7:
14:
185:It may be defined inductively by
267:two words together: this is the
773:Reutenauer, Christophe (1993),
261:Eilenberg & Mac Lane (1953)
1:
321:Chen, Fox & Lyndon (1958)
487:Hopf algebra of permutations
55:universal enveloping algebra
687:Encyclopedia of Mathematics
853:
749:Cambridge University Press
269:riffle shuffle permutation
81:riffle shuffle permutation
48:riffle shuffle permutation
248:are single elements, and
680:Hazewinkel, M. (2001) ,
77:non-commutative algebras
85:divided power structure
817:Shuffle product symbol
745:Combinatorics on words
284:shuffle product symbol
662:Green, J. A. (1995),
611:Annals of Mathematics
558:Annals of Mathematics
256:are arbitrary words.
317:infiltration product
315:The closely related
311:Infiltration product
16:Mathematical concept
296:, derived from the
606:Mac Lane, Saunders
319:was introduced by
271:. The product is
103:is a sum over the
66:polynomial algebra
19:In mathematics, a
786:978-0-19-853679-6
776:Free Lie algebras
717:978-0-8218-5262-0
682:"Shuffle algebra"
614:, Second Series,
602:Eilenberg, Samuel
561:, Second Series,
513:, p. 101,126
302:⟨ш⟩
290:character U+29E2
844:
805:
769:
736:
708:10.1090/surv/168
694:
676:
658:
597:
553:Lyndon, Roger C.
547:Chen, Kuo-Tsai;
538:
532:
526:
520:
514:
508:
303:
295:
294:
265:riffle shuffling
133:
131:
130:
120:
117:
59:free Lie algebra
852:
851:
847:
846:
845:
843:
842:
841:
822:
821:
813:
808:
787:
772:
759:
739:
718:
697:
679:
661:
624:10.2307/1969820
600:
571:10.2307/1970044
546:
542:
541:
533:
529:
521:
517:
509:
505:
500:
492:Zinbiel algebra
483:
313:
301:
293:SHUFFLE PRODUCT
292:
291:
236:where ε is the
121:
118:
107:
106:
104:
93:
91:Shuffle product
29:shuffle product
21:shuffle algebra
17:
12:
11:
5:
850:
848:
840:
839:
834:
824:
823:
820:
819:
812:
811:External links
809:
807:
806:
785:
770:
757:
737:
716:
695:
677:
659:
598:
543:
540:
539:
527:
515:
502:
501:
499:
496:
495:
494:
489:
482:
479:
475:
474:
441:
408:
407:
374:
312:
309:
234:
233:
200:
183:
182:
169:
92:
89:
15:
13:
10:
9:
6:
4:
3:
2:
849:
838:
837:Hopf algebras
835:
833:
832:Combinatorics
830:
829:
827:
818:
815:
814:
810:
804:
800:
796:
792:
788:
782:
778:
777:
771:
768:
764:
760:
758:0-521-59924-5
754:
750:
746:
742:
738:
735:
731:
727:
723:
719:
713:
709:
705:
701:
696:
693:
689:
688:
683:
678:
675:
671:
667:
666:
660:
657:
653:
649:
645:
641:
637:
633:
629:
625:
621:
618:(1): 55–106,
617:
613:
612:
607:
603:
599:
596:
592:
588:
584:
580:
576:
572:
568:
564:
560:
559:
554:
550:
549:Fox, Ralph H.
545:
544:
537:, p. 128
536:
535:Lothaire 1997
531:
528:
525:, p. 126
524:
523:Lothaire 1997
519:
516:
512:
511:Lothaire 1997
507:
504:
497:
493:
490:
488:
485:
484:
480:
478:
473:
469:
465:
461:
457:
453:
449:
445:
442:
440:
436:
432:
428:
424:
420:
416:
413:
412:
411:
410:For example:
406:
402:
398:
394:
390:
386:
382:
378:
375:
373:
369:
365:
361:
357:
353:
349:
345:
341:
337:
333:
330:
329:
328:
326:
322:
318:
310:
308:
306:
299:
289:
285:
280:
278:
274:
270:
266:
262:
257:
255:
251:
247:
243:
239:
232:
228:
224:
220:
216:
212:
208:
204:
201:
199:
195:
191:
188:
187:
186:
181:
177:
173:
170:
168:
164:
160:
156:
152:
148:
144:
140:
137:
136:
135:
128:
124:
115:
111:
102:
98:
90:
88:
86:
82:
78:
73:
71:
67:
62:
60:
56:
51:
49:
45:
41:
38:of two words
37:
33:
30:
26:
22:
775:
744:
741:Lothaire, M.
699:
685:
664:
615:
609:
565:(1): 81–95,
562:
556:
530:
518:
506:
476:
471:
467:
463:
459:
455:
451:
447:
443:
438:
434:
430:
426:
422:
418:
414:
409:
404:
400:
396:
392:
388:
384:
380:
376:
371:
367:
363:
359:
355:
351:
347:
343:
339:
335:
331:
324:
316:
314:
283:
281:
258:
253:
249:
245:
241:
235:
230:
226:
222:
218:
214:
210:
206:
202:
197:
193:
189:
184:
179:
175:
171:
166:
162:
158:
154:
150:
146:
142:
138:
126:
122:
113:
109:
100:
96:
94:
74:
70:Lyndon words
63:
61:on the set.
52:
43:
39:
35:
31:
28:
25:Hopf algebra
20:
18:
277:associative
273:commutative
826:Categories
803:0798.17001
767:0874.20040
734:1211.16023
656:0050.39304
595:0142.22304
498:References
238:empty word
192:⧢ ε = ε ⧢
692:EMS Press
632:0003-486X
743:(1997),
481:See also
298:Cyrillic
795:1231799
726:2724822
674:1399082
648:0056295
640:1969820
587:0102539
579:1970044
300:letter
288:Unicode
132:
105:
68:in the
57:of the
801:
793:
783:
765:
755:
732:
724:
714:
672:
654:
646:
638:
630:
593:
585:
577:
636:JSTOR
575:JSTOR
180:aaaaa
23:is a
781:ISBN
753:ISBN
712:ISBN
628:ISSN
472:baba
468:baab
464:abba
460:abab
439:abab
435:aabb
433:+ 4
275:and
252:and
244:and
178:= 10
167:xyab
163:xayb
159:axyb
155:xaby
151:axby
147:abxy
99:and
799:Zbl
763:Zbl
730:Zbl
704:doi
652:Zbl
620:doi
591:Zbl
567:doi
466:+ 2
462:+ 2
456:bab
452:aba
437:+ 2
431:abb
429:+ 2
427:aab
425:+ 2
395:+ (
383:= (
362:+ (
350:+ (
338:= (
327:by
307:).
305:sha
286:⧢ (
221:+ (
209:= (
172:aaa
828::
797:,
791:MR
789:,
761:,
751:,
728:,
722:MR
720:,
710:,
690:,
684:,
670:MR
650:,
644:MR
642:,
634:,
626:,
616:58
604:;
589:,
583:MR
581:,
573:,
563:68
551:;
470:+
458:+
454:+
450:=
448:ba
446:↑
444:ab
423:ab
421:=
419:ab
417:↑
415:ab
399:↑
397:fa
389:gb
387:↑
381:gb
379:↑
377:fa
366:↑
354:↑
352:fa
344:ga
342:↑
336:ga
334:↑
332:fa
279:.
240:,
225:⧢
223:ua
215:vb
213:⧢
207:vb
205:⧢
203:ua
196:=
176:aa
174:⧢
165:+
161:+
157:+
153:+
149:+
145:=
143:xy
141:⧢
139:ab
116:)!
72:.
50:.
42:,
34:⧢
706::
622::
569::
405:b
403:)
401:g
393:a
391:)
385:f
372:a
370:)
368:g
364:f
360:a
358:)
356:g
348:a
346:)
340:f
325:A
254:v
250:u
246:b
242:a
231:b
229:)
227:v
219:a
217:)
211:u
198:u
194:u
190:u
129:!
127:n
125:!
123:m
119:/
114:n
112:+
110:m
108:(
101:n
97:m
44:Y
40:X
36:Y
32:X
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.