E.S. 2014 – 5

Dei numeri 1,2,3,…,6000, quanti non sono divisibili né per 2, né per 3, né per 5?

Osserva l’immagine a destra e considera che

  • #(X \cup Y)=#(X)+#(Y)
    solo se X\cap Y=\empty altrimenti
    #(X \cup Y)=#(X)+#(Y)-#(X\cap Y)
  • #(X \setminus Y)=#(X)-#(Y)
    solo se Y \subseteq X altrimenti
    #(X \setminus Y)=#(X)-#(X\cap Y)

Calcola la cardinalità degli insiemi

I 1, 2, 3, 4, …, 6000 #(I) = 6000
M2 2, 4, 6, 8, …, 6000 #(M2) = 3000
M3 3, 6, 9, 12, …, 6000 #(M3) = 2000
M5 5, 10, 15, 20, …, 6000 #(M5) = 1200
M6 = M2 ∩ M3 6, 12, 18, 24, …, 6000 #(M6) = 1000
M10 = M2 ∩ M5 10, 20, 30, 40, …, 6000 #(M10) = 600
M15 = M3 ∩ M5 15, 30, 45, 60, …, 6000 #(M15) = 400
M30 = M2 ∩ M3 ∩ M5 30, 60, 90, 120, …, 6000 #(M30) = 200
M2 ∪ M3 ∪ M5 2, 3, 4, 5, …, 6000 #(M2 ∪ M3 ∪ M5) = ?
I \ (M2 ∪ M3 ∪ M5) 1, 7, 11, 13, … #(I \ (M2 ∪ M3 ∪ M5)) = ?

Osserva

M2 ∪ M3 ∪ M5 = M2 ∪ (M3 \ M6) ∪ [M5 \ M10 \ (M15 \ M30)]

e

#(M2 ∪ M3 ∪ M5)

= #{M2  ∪ (M3 \ M6) ∪ [M5 \ M10 \ (M15 \ M30)]}
= #(M2)+(#(M3)-#(M6))+{#(M5)-#(M10)-[#(M15)-#(M30)]}
= 3000+(2000-1000)+[1200-600-(400-200)]
= 3000+1000+400
= 4400

quindi

#(I \ (M2 ∪ M3 ∪ M5))

= 6000-4400
= 1600

E.S. 2008 – 6

Se {n \choose 1}, {n \choose 2}, {n \choose 3}, con n>3, sono in progressione aritmetica, qual è il valore di n?

Osserva

  1. {n \choose k} =\frac{n!}{k!(n-k)!}
  2. {n \choose k} =\frac{n(n-1)\ \cdots\ (n-k+1)}{k!}
  3. n \ge k \ge 0
  4. n \ge 3 (n\ge1n\ge2n\ge3)
  5. {n \choose 1}+x={n \choose 2}
  6. {n \choose 2}+x={n \choose 3}

Risolvi l’equazione

\begin{array}{l}{n \choose 3}-{n \choose 2}={n \choose 2}-{n \choose 1}\\ \\ \\ {n \choose 3}-2{n \choose 2}+{n \choose 1}=0\end{array}

n=7

In alternativa

  1. calcola i coefficienti binomiali con la formula
  2. genera le combinazioni e contale…
n {n \choose 1} {n \choose 2} {n \choose 3}
3 3

a b c

3

ab ac bc

1

abc

4 4

a b c d

6

ab ac ad bc bd cd

4

abc abd acd bcd

5 5

a b c d e

10

ab ac ad ae bc bd be cd ce de

10

abc abd abe acd ace ade bcd bce bde cde

6 6

a b c d e f

15

ab ac ad ae af bc bd be bf cd ce cf de df ef

20

abc abd abe abf acd ace acf ade adf aef bcd bce bcf bde bdf bef cde cdf cef def

7 7

a b c d e f g

21

ab ac ad ae af ag bc bd be bf bg cd ce cf cg de df dg ef eg fg

35

abc abd abe abf abg acd ace acf acg ade adf adg aef aeg afg bcd bce bcf bcg bde bdf bdg bef beg bfg cde cdf cdg cef ceg cfg def deg dfg efg

8 8

a b c d e f g h

28

ab ac ad ae af ag ah bc bd be bf bg bh cd ce cf cg ch de df dg dh ef eg eh fg fh gh

56

E.S. 2003 – 9

Si consideri una data estrazione in una determinata Ruota del Lotto.
Calcolare quante sono le possibili cinquine che contengono i numeri 1 e 90.

Le cinquine sono tutte della forma: (1, x, y, z, 90)

Le possibili triple (x, y, z), ordinate, con valori diversi in 2…89 (88 valori) sono

{88 \choose 3}=\frac{88!}{3!85!}=\dots=109.736

Permutazioni con ripetizioni

Se un simbolo si ripete k volte le permutazioni si riducono di k! (Il numero di permutazioni dei k simboli uguali)

La scrittura Pn;k significa le permutazioni di n simboli con un simbolo che si ripete k volte

P_{n;k}=\frac{n!}{k!}

Ancora

P_{n;k_1,k_2}=\frac{n!}{k_1!k_2!}

In generale

P_{n;k_1,k_2,...}=\frac{P_n}{k_1!k_2!\ ...}={n \choose k_1k_2\ ...}, coefficiente multinomiale

Quanti anagrammi si possono creare con n lettere se una si ripete k volte?

1 {A}

\frac{1!}{1!}=1

A

2 {A,A}

\frac{2!}{2!}=1

AA

{A,B}

\frac{2!}{1!}=2

AB BA

3 {A,A,A}

\frac{3!}{3!}=1

AAA

{A,A,B}

\frac{3!}{2!1!}=3

AAB ABA
BAA

{A,B,C}

\frac{3!}{1!1!1!}=6

ABC ACB BAC
BCA CAB CBA

4 {A,A,A,A}

\frac{4!}{4!}=1

AAAA

{A,A,A,B}

\frac{4!}{3!1!}=4

AAAB AABA
ABAA BAAA

{A,A,B,B}

\frac{4!}{2!2!}=6

AABB ABAB ABBA
BAAB BABA BBAA

{A,A,B,C}

\frac{4!}{2!1!1!}=12

AABC …

5 {A,A,A,A,A}

\frac{5!}{5!}=1

AAAAAA

{A,A,A,A,B}

\frac{5!}{4!1!}=5

AAAAB AAABA
AABAA ABAAA
BAAAA

{A,A,A,B,B}

\frac{5!}{3!2!}=10

AAABB AABAB AABBA
ABAAB ABABA ABBAA
BAAAB BAABA BABAA
BBAAA

{A,A,A,B,C}

\frac{5!}{3!1!1!}=20

AAABC …

{A,A,B,B,C}

\frac{5!}{2!2!1!}=30

AABBC …

6 {A,A,A,A,A,A}

\frac{6!}{6!}=1

AAAAAA

{A,A,A,A,A,B}

\frac{6!}{5!1!}=6

AAAAAB AAAABA
AAABAA AABAAA
ABAAAA BAAAAA

{A,A,A,A,B,B}

\frac{6!}{4!2!}=15

AAAABB AAABAB AAABBA
AABAAB AABABA AABBAA
ABAAAB ABAABA ABABAA
ABBAAA BAAAAB BAAABA
BAABAA BABAAA BBAAAA

{A,A,A,B,B,B}

\frac{6!}{3!3!}=20

AAABBB AABABB AABBAB
AABBBA ABAABB ABABAB
ABABBA ABBAAB ABBABA
ABBBAA …

{A,A,A,A,B,C}

\frac{6!}{4!1!1!}=30