Don't take life too seriously: it's just a temporary situation

Eulero a zig zag (numeri di)

Analisi  Matematica combinatoria 

I numeri di Eulero a zig zag, indicati con E*n sono il numero di permutazioni dei primi n interi nelle quali gli interi di posto pari sono maggiori dei due adiacenti, vale a dire le permutazioni “a zig zag”, nelle quali il valore sale e scende alternativamente. Per questo i numeri di indice dispari sono anche detti numeri zig, mentre quelli di indice pari sono detti numeri zag.

Per esempio, E*4 = 5, perché vi sono 5 permutazioni del genere dei primi 4 interi:

  • 1, 3, 2, 4;

  • 1, 4, 2, 3;

  • 2, 3, 1, 4;

  • 2, 4, 1, 3;

  • 3, 4, 1, 2.

 

Il problema della determinazione del numero totale delle permutazioni a zig zag è noto come problema di André. Dato che la prima variazione può essere sia a salire che a scendere, originando due soluzioni simmetriche, la soluzione al problema è data dal doppio dei numeri di Eulero a zig zag.

 

Le permutazioni a zig zag sono anche talvolta chiamate permutazioni alternate, ma tale termine va più propriamente riferito alle permutazioni di parità pari, ottenibili cioè con un numero pari di scambi tra coppie di oggetti.

 

Possono essere calcolati come E*n = n!an, dove an è definito dalla sequenza a0 = a1 = 0, Ricorrenza per il calcolo dei numeri di Eulero a zig zag, oppure sfruttando le relazioni con i numeri di Entringer, Eulero e Bernoulli:

E*n = En, n, dove En, n è un numero di Entringer;

Formula per il calcolo dei numeri di Eulero a zig zag

 

Le funzioni generatrici sono 1 / cos(x) per i termini di indice pari e tanx per quelli di indice dispari, ovvero Funzione generatrice per i termini di indice pari, Funzione generatrice per i termini di indice dispari e Funzione generatrice per i numeri di eulero a zig zag, per Valore assoluto di x minore di π diviso 2.

Per la splendida dimostrazione di Désiré André (1879) rimando a Mathematical Gems III.

Questo significa che i termini di indice pari sono le derivate di ordine pari della funzione 1 / cos(x), detta “secante”, nell’origine (le derivate di ordine dispari sono nulle) e quelli di indice dispari sono le derivate di ordine dispari della funzione tanx (le derivate di ordine pari sono nulle), sempre nell’origine. Per questo motivo i termini di indice pari sono detti “numeri secanti” e quelli di indice dispari “numeri tangenti”.

 

I termini di ordine dispari sono legati alla funzione γ dalla relazione Relazione tra i termini di ordine dispari e la funzione γ.

 

Nel 1877 Philipp Ludwig von Seidel scoprì un grazioso algoritmo per calcolare i numeri di Eulero a zig zag, basato sul triangolo mostrato di seguito.

 

 

 

1

 

 

 

 

 

1

1

 

 

 

 

2

2

1

 

 

2

4

5

5

 

 

16

16

14

10

5

16

32

46

56

61

61

 

Si inizia con 1 sulla prima riga, poi si aggiungono righe, percorrendole in senso alternato, come indicato dalle frecce.

In ogni riga il primo numero è uguale a quello della riga precedente, sulla stessa colonna, poi si somma il numero immediatamente sopra alla casella da riempire con l’ultimo scritto: nelle righe riempite andando a destra si somma il numero a sinistra con quello sovrastante, nelle altre il numero a destra con quello sovrastante. Alla fine della riga si duplica l’ultimo numero scritto.

I numeri E*n duplicati all’estremità di ogni riga costituiscono la sequenza 1, 1, 2, 5, 16, 61, …, alla quale si aggiunge, per convenzione, E*0 = 1.

 

Nel 2013 Florian Luca e Pantelimon Stănică dimostrarono che sono vere le congetture proposte da Zhi-Wei Sun l’anno precedente:

  • Formula che coinvolge i numeri di Eulero a zig zag è strettamente crescente;

  • Formula che coinvolge i numeri di Eulero a zig zag è strettamente decrescente per n > 1.

Nel 2013 Yi Wang e Bao-Xuan Zhu dimostrarono che Formula che coinvolge i numeri di Eulero a zig zag è strettamente crescente.

Per i numeri di Eulero a zig zag vale l’interessante limite Limite che coinvolge i numeri di Eulero a zig zag.

Nel 1967 Donald Ervin Knuth e Thomas J. Buckholtz, 1967 dimostrarono che E*2n + 1 è multiplo di 2n e che i resti dei numeri di Eulero a zig zag modulo una potenza di un primo dispari pk si ripetono, a partire da un termine con indice almeno pari a k, con un periodo di lunghezza:

  • (p – 1)pk – 1, se p ha ha forma 4m + 1;

  • 2(p – 1)pk – 1, se p ha ha forma 4m + 3.

 

 

Nel 2011 Zhi-Wei Sun avanzò la congettura che ogni numero di Eulero a zig zag di indice dispari maggiore di 5 ha un fattore primo primitivo, cioè è multiplo di un primo che non divide alcun numero di Eulero a zig zag di indice dispari inferiore.

 

La tabella seguente mostra i numeri di Eulero a zig zag fino a E*50.

n

E*n

0

1

1

1

2

1

3

2

4

5

5

16

6

61

7

272

8

1385

9

7936

10

50521

11

353792

12

2702765

13

22368256

14

199360981

15

1903757312

16

19391512145

17

209865342976

18

2404879675441

19

29088885112832

20

370371188237525

21

4951498053124096

22

69348874393137901

23

1015423886506852352

24

15514534163557086905

25

246921480190207983616

26

4087072509293123892361

27

70251601603943959887872

28

1252259641403629865468285

29

23119184187809597841473536

30

441543893249023104553682821

31

8713962757125169296170811392

32

177519391579539289436664789665

33

3729407703720529571097509625856

34

80723299235887898062168247453281

35

1798651693450888780071750349094912

36

41222060339517702122347079671259045

37

970982810785059112379399707952152576

38

23489580527043108252017828576198947741

39

583203324917310043943191641625494290432

40

14851150718114980017877156781405826684425

41

387635983772083031828014624002175135645696

42

10364622733519612119397957304745185976310201

43

283727921907431909304183316295787837183229952

44

7947579422597592703608040510088070619519273805

45

227681379129930886488600284336316164603920777216

46

6667537516685544977435028474773748197524107684661

47

199500252157859031027160499643195658166340757225472

48

6096278645568542158691685742876843153976539044435185

49

190169564657928428175235445073924928592047775873499136

50

6053285248188621896314383785111649088103498225146815121

 

Bibliografia

  • Honsberger, Ross;  Mathematical Gems III, The Mathematical Association of America,, 1985.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.