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

Ballottaggio (numeri del)

Matematica combinatoria 

I numeri del ballottaggio sono legati al problema del ballottaggio di Bertrand, che può essere espresso in questi termini: in un ballottaggio tra due candidati, A vince con a voti su B, che ne totalizza b. Qual è la probabilità che durante lo spoglio A sia sempre in vantaggio?

La risposta è (a – b) / (a + b), come dimostrò William Allen Whitworth (Runcorn, Inghilterra, 1/2/1840 – 12/3/1905) nel 1878. Nel 1987 Joseph Louis François Bertrand (Parigi, 11/3/1822 – Parigi, 5/4/1900) riscoprì la soluzione e da allora problema e soluzione sono impropriamente attribuiti a lui.

 

Un problema leggermente diverso è determinare la probabilità che il perdente non sia mai in vantaggio; la risposta è (a – b + 1) / (a + 1).

 

Un problema equivalente al problema del ballottaggio è determinare quanti cammini che iniziano nell’origine, consistono di n passi uguali a 1 o –1 e terminano nel punto m non raggiungano mai punti con coordinata negativa; la risposta è (m + 1) / ((n + m) / 2 + 1) * C(n, (n + m) / 2); nel caso particolare n = 2k e m = 0 abbiamo i numeri di Catalan C(k) = 1 / (k + 1) * C(2 * k, k).

 

I numeri del ballottaggio Ba, b sono i numeri di modi differenti nei quali può avvenire lo spoglio, rispettando la condizione che A sia sempre in vantaggio dopo il primo voto e sono dati da B(a, b) = (a – b) / (a + b) * C(a + b, a).

 

Il numero del ballottaggio Ba, b è il numero di cammini in un reticolo quadrato che iniziano nell’origine, sono composti da a passi verso destra e b passi verso l’alto, quindi terminano nel punto (a, b), e che restano sempre al di sotto della diagonale del primo quadrante.

La figura seguente mostra i 5 cammini che terminano nel punto (4, 3) corrispondenti a B4, 3.

 

I 5 cammini che terminano nel punto (4, 3)

 

 

Alcuni valori particolari:

Ba, 1 = a – 1;

Ba, a = 0;

Ba, a – 1 = Ba, a – 2 = Ca – 1, dove Cn è l’n-esimo numero di Catalan.

 

Alcune formule per il calcolo dei numeri del ballottaggio:

Ba, b = Ba – 1, b + Ba, b – 1;

Ba, b = –Bb, a;

Formula per il calcolo dei numeri del ballottaggio.

 

Alcune formule che coinvolgono i numeri del ballottaggio:

Formula che coinvolge i numeri del ballottaggio;

Formula che coinvolge i numeri del ballottaggio dove Cn è l’n-esimo numero di Catalan

Formula che coinvolge i numeri del ballottaggio.

 

Le funzioni generatrici dei numeri del ballottaggio sono Funzione generatrice dei numeri del ballottaggio e Funzione generatrice dei numeri del ballottaggio.

 

Le tabelle seguenti mostrano i numeri del ballottaggio per n e k fino a 20.

a \ b

0

1

2

3

4

5

6

7

8

0

1

–1

–1

–1

–1

–1

–1

–1

–1

1

1

0

–1

–2

–3

–4

–5

–6

–7

2

1

1

0

–2

–5

–9

–14

–20

–27

3

1

2

2

0

–5

–14

–28

–48

–75

4

1

3

5

5

0

–14

–42

–90

–165

5

1

4

9

14

14

0

–42

–132

–297

6

1

5

14

28

42

42

0

–132

–429

7

1

6

20

48

90

132

132

0

–429

8

1

7

27

75

165

297

429

429

0

9

1

8

35

110

275

572

1001

1430

1430

10

1

9

44

154

429

1001

2002

3432

4862

11

1

10

54

208

637

1638

3640

7072

11934

12

1

11

65

273

910

2548

6188

13260

25194

13

1

12

77

350

1260

3808

9996

23256

48450

14

1

13

90

440

1700

5508

15504

38760

87210

15

1

14

104

544

2244

7752

23256

62016

149226

16

1

15

119

663

2907

10659

33915

95931

245157

17

1

16

135

798

3705

14364

48279

144210

389367

18

1

17

152

950

4655

19019

67298

211508

600875

19

1

18

170

1120

5775

24794

92092

303600

904475

20

1

19

189

1309

7084

31878

123970

427570

1332045

a \ b

9

10

11

12

13

14

0

–1

–1

–1

–1

–1

–1

1

–8

–9

–10

–11

–12

–13

2

–35

–44

–54

–65

–77

–90

3

–110

–154

–208

–273

–350

–440

4

–275

–429

–637

–910

–1260

–1700

5

–572

–1001

–1638

–2548

–3808

–5508

6

–1001

–2002

–3640

–6188

–9996

–15504

7

–1430

–3432

–7072

–13260

–23256

–38760

8

–1430

–4862

–11934

–25194

–48450

–87210

9

0

–4862

–16796

–41990

–90440

–177650

10

4862

0

–16796

–58786

–149226

–326876

11

16796

16796

0

–58786

–208012

–534888

12

41990

58786

58786

0

–208012

–742900

13

90440

149226

208012

208012

0

–742900

14

177650

326876

534888

742900

742900

0

15

326876

653752

1188640

1931540

2674440

2674440

16

572033

1225785

2414425

4345965

7020405

9694845

17

961400

2187185

4601610

8947575

15967980

25662825

18

1562275

3749460

8351070

17298645

33266625

58929450

19

2466750

6216210

14567280

31865925

65132550

124062000

20

3798795

10015005

24582285

56448210

121580760

245642760

a \ b

15

16

17

18

19

20

0

–1

–1

–1

–1

–1

–1

1

–14

–15

–16

–17

–18

–19

2

–104

–119

–135

–152

–170

–189

3

–544

–663

–798

–950

–1120

–1309

4

–2244

–2907

–3705

–4655

–5775

–7084

5

–7752

–10659

–14364

–19019

–24794

–31878

6

–23256

–33915

–48279

–67298

–92092

–123970

7

–62016

–95931

–144210

–211508

–303600

–427570

8

–149226

–245157

–389367

–600875

–904475

–1332045

9

–326876

–572033

–961400

–1562275

–2466750

–3798795

10

–653752

–1225785

–2187185

–3749460

–6216210

–10015005

11

–1188640

–2414425

–4601610

–8351070

–14567280

–24582285

12

–1931540

–4345965

–8947575

–17298645

–31865925

–56448210

13

–2674440

–7020405

–15967980

–33266625

–65132550

–121580760

14

–2674440

–9694845

–25662825

–58929450

–124062000

–245642760

15

0

–9694845

–35357670

–94287120

–218349120

–463991880

16

9694845

0

–35357670

–129644790

–347993910

–811985790

17

35357670

35357670

0

–129644790

–477638700

–1289624490

18

94287120

129644790

129644790

0

–477638700

–1767263190

19

218349120

347993910

477638700

477638700

0

–1767263190

20

463991880

811985790

1289624490

1767263190

1767263190

0

 

Nel 2018 Wun-Seng Chou, Tian-Xiao He e Peter J.-S. Shiue dimostrarono che gli unici numeri di ballottaggio primi sono:

  • Bp + 1, 1 = p, se p è primo;

  • B3, 2 = 2;

  • B4, 2 = B4, 3 = 5.

Contattami

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