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