1055:
508:
1503:
763:
823:
245:
1235:
302:
1326:
1337:
597:
551:
287:
1115:
585:
811:
1050:{\displaystyle \sum _{k=\alpha }^{n}{n \choose k}(-1)^{n-k}f(k)={\frac {-n!}{2\pi i}}\int _{c-i\infty }^{c+i\infty }{\frac {f(z)}{z(z-1)(z-2)\cdots (z-n)}}\,dz}
1548:
techniques; by contrast, the forward difference series can be extremely hard to evaluate numerically, because the binomial coefficients grow rapidly for large
814:
817:
on the right hand side of the complex plane, then the contour may be extended to infinity on the right hand side, allowing the transform to be written as
116:
503:{\displaystyle \sum _{k=\alpha }^{n}{n \choose k}(-1)^{n-k}f(k)={\frac {n!}{2\pi i}}\oint _{\gamma }{\frac {f(z)}{z(z-1)(z-2)\cdots (z-n)}}\,dz}
1139:
1072:
The
Poisson–Mellin–Newton cycle, noted by Flajolet et al. in 1985, is the observation that the resemblance of the Nørlund–Rice integral to the
17:
1498:{\displaystyle f_{n}={\frac {(-1)^{n}}{2\pi i}}\int _{\gamma }{\frac {\phi (-s)}{\Gamma (-s)}}{\frac {n!}{s(s-1)\cdots (s-n)}}\,ds}
1246:
1645:
1331:
one can then regain the original sequence by means of the Nörlund–Rice integral (see
References "Mellin, seen from the sky"):
1566:
1540:
The integral representation for these types of series is interesting because the integral can often be evaluated using
758:{\displaystyle \sum _{k=\alpha }^{n}{n \choose k}(-1)^{k}f(k)=-{\frac {1}{2\pi i}}\oint _{\gamma }B(n+1,-z)f(z)\,dz}
82:. Nørlund's contribution was to define the integral; Rice's contribution was to demonstrate its utility by applying
1587:
1513:
1655:
1532:
is related to the Mellin transform: rather than dealing with infinite series, it deals with finite series.
1609:
1660:
1625:
1130:
524:
1545:
83:
1650:
1595:
1561:
253:
554:
1528:. Very roughly, it can be said to be related to the Nörlund–Rice integral in the same way that
1087:
564:
75:
1541:
290:
787:
8:
1529:
1077:
99:
59:
47:
1073:
63:
79:
1509:
1639:
1081:
781:
55:
51:
240:{\displaystyle \Delta ^{n}(x)=\sum _{k=0}^{n}{n \choose k}(-1)^{n-k}f(x+k)}
67:
1596:
Mellin transforms and asymptotics: Finite differences and Rice's integrals
1230:{\displaystyle g(t)=e^{-t}\sum _{n=0}^{\infty }{\frac {t^{n}}{n!}}f_{n}.}
518:
71:
31:
1525:
1118:
1524:
A closely related integral frequently occurs in the discussion of
1613:
553:, and the contour of integration is understood to circle the
1321:{\displaystyle \phi (s)=\int _{0}^{\infty }g(t)t^{s-1}\,dt,}
1340:
1249:
1142:
1090:
826:
790:
600:
567:
527:
305:
256:
119:
1497:
1320:
1229:
1109:
1076:is not accidental, but is related by means of the
1049:
805:
757:
579:
545:
502:
281:
239:
864:
851:
638:
625:
343:
330:
273:
260:
188:
175:
1637:
1582:, (1954) Chelsea Publishing Company, New York.
1067:
1104:
1091:
1594:Philippe Flajolet and Robert Sedgewick, "
1488:
1308:
1040:
748:
561:, but encircles neither integers 0, ...,
493:
1614:The Electronic Journal of Combinatorics
591:. The integral may also be written as
58:. It commonly appears in the theory of
14:
1638:
296:The Nörlund–Rice integral is given by
1567:List of factorial and binomial topics
1580:Vorlesungen uber Differenzenrechnung
546:{\displaystyle 0\leq \alpha \leq n}
24:
1512:which cancels with the gamma from
1420:
1275:
1187:
964:
950:
855:
629:
334:
264:
179:
121:
74:lengths. It is named in honour of
25:
1672:
1591:, (1973), Vol. 3 Addison-Wesley.
557:located at the integers α, ...,
1588:The Art of Computer Programming
1482:
1470:
1464:
1452:
1432:
1423:
1415:
1406:
1367:
1357:
1289:
1283:
1259:
1253:
1152:
1146:
1034:
1022:
1016:
1004:
1001:
989:
981:
975:
904:
898:
880:
870:
800:
794:
745:
739:
733:
712:
672:
666:
654:
644:
487:
475:
469:
457:
454:
442:
434:
428:
383:
377:
359:
349:
234:
222:
204:
194:
145:
139:
136:
130:
13:
1:
1646:Factorial and binomial topics
1624:Philippe Flajolet, lecture, "
1572:
1519:
282:{\displaystyle {n \choose k}}
89:
62:and has also been applied in
1600:Theoretical Computer Science
1240:Taking its Mellin transform
7:
1555:
1131:Poisson generating function
1068:Poisson–Mellin–Newton cycle
10:
1677:
1535:
1514:Ramanujan's Master Theorem
1626:Mellin, seen from the sky
1621:(1996) Issue 2 Article 7.
1562:Table of Newtonian series
1110:{\displaystyle \{f_{n}\}}
580:{\displaystyle \alpha -1}
587:nor any of the poles of
1129:) be the corresponding
84:saddle-point techniques
1608:Peter Kirschenhofer, "
1499:
1322:
1231:
1191:
1111:
1084:. In this cycle, let
1051:
847:
807:
759:
621:
581:
547:
504:
326:
283:
241:
171:
1500:
1323:
1232:
1171:
1112:
1064:is to the left of α.
1052:
827:
808:
760:
601:
582:
548:
505:
306:
284:
242:
151:
36:Nørlund–Rice integral
27:Mathematical integral
18:Nörlund–Rice integral
1578:Niels Erik Nørlund,
1542:asymptotic expansion
1338:
1247:
1140:
1088:
824:
815:polynomially bounded
806:{\displaystyle f(z)}
788:
598:
565:
525:
517:is understood to be
303:
291:binomial coefficient
254:
117:
1656:Integral transforms
1279:
1060:where the constant
968:
784:. If the function
521:, α is an integer,
86:to its evaluation.
50:of a function to a
38:, sometimes called
1661:Finite differences
1605:(1995) pp 101–124.
1495:
1318:
1265:
1227:
1107:
1078:binomial transform
1047:
936:
803:
755:
577:
543:
500:
279:
237:
100:forward difference
76:Niels Erik Nørlund
60:finite differences
48:forward difference
1585:Donald E. Knuth,
1486:
1436:
1388:
1212:
1038:
934:
862:
697:
636:
491:
410:
341:
271:
186:
16:(Redirected from
1668:
1651:Complex analysis
1530:Perron's formula
1504:
1502:
1501:
1496:
1487:
1485:
1447:
1439:
1437:
1435:
1418:
1401:
1399:
1398:
1389:
1387:
1376:
1375:
1374:
1355:
1350:
1349:
1327:
1325:
1324:
1319:
1307:
1306:
1278:
1273:
1236:
1234:
1233:
1228:
1223:
1222:
1213:
1211:
1203:
1202:
1193:
1190:
1185:
1170:
1169:
1116:
1114:
1113:
1108:
1103:
1102:
1074:Mellin transform
1056:
1054:
1053:
1048:
1039:
1037:
984:
970:
967:
953:
935:
933:
922:
911:
894:
893:
869:
868:
867:
854:
846:
841:
812:
810:
809:
804:
764:
762:
761:
756:
708:
707:
698:
696:
682:
662:
661:
643:
642:
641:
628:
620:
615:
586:
584:
583:
578:
552:
550:
549:
544:
509:
507:
506:
501:
492:
490:
437:
423:
421:
420:
411:
409:
398:
390:
373:
372:
348:
347:
346:
333:
325:
320:
288:
286:
285:
280:
278:
277:
276:
263:
246:
244:
243:
238:
218:
217:
193:
192:
191:
178:
170:
165:
129:
128:
64:computer science
21:
1676:
1675:
1671:
1670:
1669:
1667:
1666:
1665:
1636:
1635:
1575:
1558:
1538:
1522:
1508:where Γ is the
1448:
1440:
1438:
1419:
1402:
1400:
1394:
1390:
1377:
1370:
1366:
1356:
1354:
1345:
1341:
1339:
1336:
1335:
1296:
1292:
1274:
1269:
1248:
1245:
1244:
1218:
1214:
1204:
1198:
1194:
1192:
1186:
1175:
1162:
1158:
1141:
1138:
1137:
1133:, that is, let
1098:
1094:
1089:
1086:
1085:
1070:
985:
971:
969:
954:
940:
923:
912:
910:
883:
879:
863:
850:
849:
848:
842:
831:
825:
822:
821:
789:
786:
785:
780:) is the Euler
703:
699:
686:
681:
657:
653:
637:
624:
623:
622:
616:
605:
599:
596:
595:
566:
563:
562:
526:
523:
522:
438:
424:
422:
416:
412:
399:
391:
389:
362:
358:
342:
329:
328:
327:
321:
310:
304:
301:
300:
272:
259:
258:
257:
255:
252:
251:
207:
203:
187:
174:
173:
172:
166:
155:
124:
120:
118:
115:
114:
92:
80:Stephen O. Rice
28:
23:
22:
15:
12:
11:
5:
1674:
1664:
1663:
1658:
1653:
1648:
1634:
1633:
1622:
1606:
1592:
1583:
1574:
1571:
1570:
1569:
1564:
1557:
1554:
1537:
1534:
1521:
1518:
1510:gamma function
1506:
1505:
1494:
1491:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1446:
1443:
1434:
1431:
1428:
1425:
1422:
1417:
1414:
1411:
1408:
1405:
1397:
1393:
1386:
1383:
1380:
1373:
1369:
1365:
1362:
1359:
1353:
1348:
1344:
1329:
1328:
1317:
1314:
1311:
1305:
1302:
1299:
1295:
1291:
1288:
1285:
1282:
1277:
1272:
1268:
1264:
1261:
1258:
1255:
1252:
1238:
1237:
1226:
1221:
1217:
1210:
1207:
1201:
1197:
1189:
1184:
1181:
1178:
1174:
1168:
1165:
1161:
1157:
1154:
1151:
1148:
1145:
1106:
1101:
1097:
1093:
1069:
1066:
1058:
1057:
1046:
1043:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
983:
980:
977:
974:
966:
963:
960:
957:
952:
949:
946:
943:
939:
932:
929:
926:
921:
918:
915:
909:
906:
903:
900:
897:
892:
889:
886:
882:
878:
875:
872:
866:
861:
858:
853:
845:
840:
837:
834:
830:
802:
799:
796:
793:
766:
765:
754:
751:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
706:
702:
695:
692:
689:
685:
680:
677:
674:
671:
668:
665:
660:
656:
652:
649:
646:
640:
635:
632:
627:
619:
614:
611:
608:
604:
576:
573:
570:
542:
539:
536:
533:
530:
511:
510:
499:
496:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
436:
433:
430:
427:
419:
415:
408:
405:
402:
397:
394:
388:
385:
382:
379:
376:
371:
368:
365:
361:
357:
354:
351:
345:
340:
337:
332:
324:
319:
316:
313:
309:
275:
270:
267:
262:
248:
247:
236:
233:
230:
227:
224:
221:
216:
213:
210:
206:
202:
199:
196:
190:
185:
182:
177:
169:
164:
161:
158:
154:
150:
147:
144:
141:
138:
135:
132:
127:
123:
110:) is given by
102:of a function
91:
88:
42:, relates the
26:
9:
6:
4:
3:
2:
1673:
1662:
1659:
1657:
1654:
1652:
1649:
1647:
1644:
1643:
1641:
1631:
1627:
1623:
1620:
1616:
1615:
1610:
1607:
1604:
1601:
1597:
1593:
1590:
1589:
1584:
1581:
1577:
1576:
1568:
1565:
1563:
1560:
1559:
1553:
1551:
1547:
1543:
1533:
1531:
1527:
1517:
1515:
1511:
1492:
1489:
1479:
1476:
1473:
1467:
1461:
1458:
1455:
1449:
1444:
1441:
1429:
1426:
1412:
1409:
1403:
1395:
1391:
1384:
1381:
1378:
1371:
1363:
1360:
1351:
1346:
1342:
1334:
1333:
1332:
1315:
1312:
1309:
1303:
1300:
1297:
1293:
1286:
1280:
1270:
1266:
1262:
1256:
1250:
1243:
1242:
1241:
1224:
1219:
1215:
1208:
1205:
1199:
1195:
1182:
1179:
1176:
1172:
1166:
1163:
1159:
1155:
1149:
1143:
1136:
1135:
1134:
1132:
1128:
1124:
1120:
1099:
1095:
1083:
1082:Newton series
1079:
1075:
1065:
1063:
1044:
1041:
1031:
1028:
1025:
1019:
1013:
1010:
1007:
998:
995:
992:
986:
978:
972:
961:
958:
955:
947:
944:
941:
937:
930:
927:
924:
919:
916:
913:
907:
901:
895:
890:
887:
884:
876:
873:
859:
856:
843:
838:
835:
832:
828:
820:
819:
818:
816:
797:
791:
783:
782:beta function
779:
775:
771:
752:
749:
742:
736:
730:
727:
724:
721:
718:
715:
709:
704:
700:
693:
690:
687:
683:
678:
675:
669:
663:
658:
650:
647:
633:
630:
617:
612:
609:
606:
602:
594:
593:
592:
590:
574:
571:
568:
560:
556:
540:
537:
534:
531:
528:
520:
516:
497:
494:
484:
481:
478:
472:
466:
463:
460:
451:
448:
445:
439:
431:
425:
417:
413:
406:
403:
400:
395:
392:
386:
380:
374:
369:
366:
363:
355:
352:
338:
335:
322:
317:
314:
311:
307:
299:
298:
297:
294:
292:
268:
265:
231:
228:
225:
219:
214:
211:
208:
200:
197:
183:
180:
167:
162:
159:
156:
152:
148:
142:
133:
125:
113:
112:
111:
109:
105:
101:
97:
87:
85:
81:
77:
73:
69:
65:
61:
57:
56:complex plane
53:
52:line integral
49:
45:
41:
40:Rice's method
37:
33:
19:
1629:
1618:
1612:
1602:
1599:
1586:
1579:
1549:
1546:saddle-point
1539:
1523:
1507:
1330:
1239:
1126:
1122:
1071:
1061:
1059:
777:
773:
769:
767:
588:
558:
514:
512:
295:
249:
107:
103:
95:
93:
70:to estimate
68:graph theory
43:
39:
35:
29:
1526:Riesz means
519:meromorphic
72:binary tree
32:mathematics
1640:Categories
1573:References
1520:Riesz mean
1121:, and let
90:Definition
1617:, Volume
1477:−
1468:⋯
1459:−
1427:−
1421:Γ
1410:−
1404:ϕ
1396:γ
1392:∫
1382:π
1361:−
1301:−
1276:∞
1267:∫
1251:ϕ
1188:∞
1173:∑
1164:−
1029:−
1020:⋯
1011:−
996:−
965:∞
951:∞
945:−
938:∫
928:π
914:−
888:−
874:−
839:α
829:∑
728:−
705:γ
701:∮
691:π
679:−
648:−
613:α
603:∑
572:−
569:α
538:≤
535:α
532:≤
482:−
473:⋯
464:−
449:−
418:γ
414:∮
404:π
367:−
353:−
318:α
308:∑
212:−
198:−
153:∑
122:Δ
1628:", page
1556:See also
1119:sequence
1080:and the
1536:Utility
289:is the
54:on the
768:where
513:where
250:where
34:, the
1117:be a
555:poles
1598:",
94:The
78:and
66:and
1611:",
1603:144
1544:or
813:is
98:th
46:th
30:In
1642::
1630:35
1552:.
1516:.
293:.
1632:.
1619:3
1550:n
1493:s
1490:d
1483:)
1480:n
1474:s
1471:(
1465:)
1462:1
1456:s
1453:(
1450:s
1445:!
1442:n
1433:)
1430:s
1424:(
1416:)
1413:s
1407:(
1385:i
1379:2
1372:n
1368:)
1364:1
1358:(
1352:=
1347:n
1343:f
1316:,
1313:t
1310:d
1304:1
1298:s
1294:t
1290:)
1287:t
1284:(
1281:g
1271:0
1263:=
1260:)
1257:s
1254:(
1225:.
1220:n
1216:f
1209:!
1206:n
1200:n
1196:t
1183:0
1180:=
1177:n
1167:t
1160:e
1156:=
1153:)
1150:t
1147:(
1144:g
1127:t
1125:(
1123:g
1105:}
1100:n
1096:f
1092:{
1062:c
1045:z
1042:d
1035:)
1032:n
1026:z
1023:(
1017:)
1014:2
1008:z
1005:(
1002:)
999:1
993:z
990:(
987:z
982:)
979:z
976:(
973:f
962:i
959:+
956:c
948:i
942:c
931:i
925:2
920:!
917:n
908:=
905:)
902:k
899:(
896:f
891:k
885:n
881:)
877:1
871:(
865:)
860:k
857:n
852:(
844:n
836:=
833:k
801:)
798:z
795:(
792:f
778:b
776:,
774:a
772:(
770:B
753:z
750:d
746:)
743:z
740:(
737:f
734:)
731:z
725:,
722:1
719:+
716:n
713:(
710:B
694:i
688:2
684:1
676:=
673:)
670:k
667:(
664:f
659:k
655:)
651:1
645:(
639:)
634:k
631:n
626:(
618:n
610:=
607:k
589:f
575:1
559:n
541:n
529:0
515:f
498:z
495:d
488:)
485:n
479:z
476:(
470:)
467:2
461:z
458:(
455:)
452:1
446:z
443:(
440:z
435:)
432:z
429:(
426:f
407:i
401:2
396:!
393:n
387:=
384:)
381:k
378:(
375:f
370:k
364:n
360:)
356:1
350:(
344:)
339:k
336:n
331:(
323:n
315:=
312:k
274:)
269:k
266:n
261:(
235:)
232:k
229:+
226:x
223:(
220:f
215:k
209:n
205:)
201:1
195:(
189:)
184:k
181:n
176:(
168:n
163:0
160:=
157:k
149:=
146:)
143:x
140:(
137:]
134:f
131:[
126:n
108:x
106:(
104:f
96:n
44:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.