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

Robbins (numeri di)

Matematica combinatoria  Sequenze 

Si chiamano “matrici a segni alternati” le matrici quadrate contenenti solo 0, 1 e –1, tali che la somma di ogni riga e di ogni colonna sia 1 e che, escludendo gli zeri, 1 e –1 si alternino su ogni riga e colonna. Tra queste un sottoinsieme importante è quello delle matrici nelle quali il primo e l’ultimo elemento di ogni riga e colonna, sempre escludendo gli zeri, siano 1.

Il numero di tali matrici di ordine n è detto n-esimo numero di Robbins Rn, in onore di Howard Robbins, uno dei pionieri delle ricerche nel settore.

 

Per esempio, il terzo numero di Robbins è 7, perché solo le seguenti 7 matrici hanno le proprietà richieste: Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3, Matrice a segni alternati di ordine 3.

 

Questi numeri sono anche noti come “numeri di Andrews – Mills – Robbins – Rumsey”, dal nome dei matematici che per primi fecero indagini in questo campo.

 

La definizione può sembrare arbitraria, ma ha radici nel calcolo dei determinanti.

Charles Lutwidge Dodgson (più noto come Lewis Carroll) inventò nel 1866 un metodo per il calcolo dei determinanti, noto come “condensazione”. Data una matrice di ordine n, si calcolano matrici di ordine decrescente n – 1, n – 2 ecc., fino a restare con una matrice di ordine 1, che ha come unico elemento il determinante desiderato. Una matrice di ordine k nella sequenza ha come elementi i k2 determinanti delle matrici di ordine 2 formate da quadrati 2 × 2 di elementi adiacenti nella matrice precedente, divisi per l’elemento centrale del corrispondente quadrato 3 × 3 della matrice di ordine k + 2 costruita in precedenza. La divisione non si effettua al primo passaggio.

Per esempio, data la matrice Matrice di ordine 3, la si sostituisce con la matrice Matrice di ordine 2 e questa con la matrice avente come unico elemento Determinante della matrice, determinante della matrice originale. I 7 monomi che compaiono nell’espressione finale corrispondono alle 7 matrici a segni alternati: per ognuna di esse, infatti, si può costruire il corrispondente monomio moltiplicando tra loro gli elementi della matrice originaria corrispondenti ai valori 1 e dividendo il risultato per il prodotto di quelli corrispondenti ai valori –1. Il monomio va poi moltiplicato per il determinante della matrice a segni alternati usata per costruirlo. Per esempio, dalla penultima delle 7 matrici riportate sopra si ricava il monomio afh, perché la matrice a segni alternati contiene tre valori 1 in corrispondenza degli elementi a, f e h della matrice di partenza e nessun elemento –1; il segno è negativo perché il determinante della matrice a segni alternati è –1.

Nel caso della matrice di ordine 3 ci ritroviamo alla fine 3 monomi con segno positivo, altrettanti con segno negativo e uno da eliminare, perché moltiplicato per zero. Nel caso della matrice di ordine 4 lo stesso procedimento produce 12 monomi con segno positivo, altrettanti con segno negativo e 18 da eliminare, perché moltiplicati per zero.

Il metodo di Dodgson è utile solo per il calcolo manuale di matrici di ordine 3 o 4, perché per ordini superiori è nettamente meno efficiente di metodi alternativi, come l’eliminazione di Gauss.

 

Dopo aver calcolato il numero di matrici a segni alternati di ordine fino a 20, William H. Mills, David P. Robbins e Howard Rumsey nel 1983 proposero la cosiddetta “congettura delle matrici a segni alternati”, cioè che il numero di tali matrici di ordine n sia Numero di matrici a segni alternati di ordine n. La congettura fu dimostrata da Doron Zeilberger nel 1992 (ma la dimostrazione fu verificata e accettata come valida solo nel 1995) e il numero di matrici a segni alternati di ordine n divenne noto come “numero di Robbins” Rn.

 

George E. Andrews dimostrò nel 1979 che il numero di partizioni piane discendenti che possono essere contenute in un cubo di spigolo n è il numero di Robbins Rn + 1.

 

Nel 1983 David P. Robbins propose la congettura che il numero di partizioni piane totalmente simmetriche auto-complementari contenute in un cubo 2n × 2n × 2n sia Rn; nel 1992 George Andrews dimostrò che la congettura è vera.

 

I numeri di Robbins sono anche dati dalla ricorrenza R0 = 1, Ricorrenza per il calcolo dei numeri di Robbins.

Una formula alternativa per il calcolo dei numeri di Robbins è Formula per il calcolo dei numeri di Robbins.

 

Il comportamento asintotico dei numeri di Robbins si ricava dal limite Limite asintotico cui tende R(n).

 

La funzione generatrice dei numeri di Robbins è Funzione generatrice dei numeri di Robbins.

 

La tabella seguente mostra i numeri di Robbins fino a R20.

n

Rn

1

1

2

2

3

7

4

42

5

429

6

7436

7

218348

8

10850216

9

911835460

10

129534272700

11

31095744852375

12

12611311859677500

13

8639383518297652500

14

9995541355448167482000

15

19529076234661277104897200

16

64427185703425689356896743840

17

358869201916137601447486156417296

18

3374860639258750562269514491522925456

19

53580350833984348888878646149709092313244

20

1436038934715538200913155682637051204376827212

 

Nel 2000 Darrin D. Frey e James A. Sellers dimostrarono che Rn è dispari se e solo se n è un numero di Jacobsthal e che pertanto esistono infiniti numeri di Robbins pari e infiniti numeri di Robbins dispari.

Nel 2002 Darrin D. Frey e James A. Sellers dimostrarono che per ogni intero positivo k:

  • per ogni primo p maggiore di 3 esistono infiniti numeri di Robbins divisibili per pk, ma non per pk + 1; in particolare, se Rn ha tale proprietà, anche Rn + pm l’ha, per m > k;

  • esistono infiniti numeri di Robbins divisibili per 3k;

  • esiste un numero finito di numeri di Robbins divisibili per 2k, ma non per potenze maggiori di 2.

 

Tabelle numeriche

I numeri di Robbins fino a R100.

Bibliografia

  • Bressoud, David M.;  Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, Cambridge, Cambridge University Press, 1999.

Contattami

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