Dubbio su calcolo combinatorio

[Daffeen]

Ciao, avrei un piccolo problema:
Sia $A = {n in mathbf{N} : n<14}$
Quante sono le parti $X$ di $A$ che verificano contemporaneamente
1. $|X| = 5$
2. $7 notin X$
3. $6 in X$

In accordo al punto 1 è facile verificare che si tratta del numero di permutazioni di $k$ oggetti (5) su un insieme di $n$ (14).
Dato che $7 notin X$ allora questi oggetti saranno 13 invece di 14, poco male.
Ma come verifico invece quanti sono quelli che contengono 6?
Grazie infinite in anticipo e buona giornata

[axpgn]

Per quanto riguarda il punto 3 ...

I sottoinsiemi di $A$ con esattamente cinque elementi sono le combinazioni di cinque oggetti presi da un insieme di quattordici elementi e sono $2002$
Ora, dato che ciascuno di questi ne contiene cinque, in totale i $2002$ insiemi contengono $10010$ elementi.
Ripetuti, ovviamente, ma ripetuti esattamente tutti nella stessa quantità (perché un elemento dovrebbe esserci più volte di un altro? Non ce n'è motivo); quindi basta dividere $10010$ per $14$ cioè $715$ e questi sono gli insiemi che contengono il $6$ (non ho tenuto conto in questo contesto della condizione del punto 2)


Cordialmente, Alex

[gugo82]

"daffeen":Ciao, avrei un piccolo problema:
Sia $A = {n in \mathbf{N} : n<14}$
Quante sono le parti $X$ di $A$ che verificano contemporaneamente
1. $|X| = 5$
2. $7 notin X$
3. $6 in X$

In accordo al punto 1 è facile verificare che si tratta del numero di permutazioni di $k$ oggetti (5) su un insieme di $n$ (14).

L'ultima frase è falsissima!

Le permutazioni non contano insiemi di $k$ elementi, ma $k$-uple ordinate.
Tanto per capirci, se prendi $n=3$ elementi, diciamo $a,b,c$, e vuoi elencare le permutazioni di lunghezza $k=2$ di tali oggetti ottieni:

$(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)$

le quali sono $6=(3!)/(1!) =(3!)/((3-2)!)$; invece, elencando gli insiemi di cardinalità $k=2$ formabili con quei tre oggetti lì trovi:

$\{1,2\}, \{1,3\}, \{2,3\}$

che sono $3=(3!)/(2!*1!) = ((3),(2))$.
In generale, dunque, il numero di sottoinsiemi di cardinalità $k$ di un insieme avente cardinalità $n$ coincide col numero di combinazioni semplici di $n$ oggetti di lunghezza $k$, i.e. col coefficiente binomiale $((n),(k))$.

***

Per risolvere il problema, ragioniamo "con le mani".

Visto che $A = \{ 0,1,2, ..., 11, 12,13\}$ e che cerchiamo $X$ in modo che $|X|=5$, dobbiamo chiederci come fissare i cinque elementi di $X$ tra quelli "consentiti" di $A$.
In particolare, sappiamo che un elemento di $A$ certamente non appartiene ad $X$, perché $7 notin X$; quindi più precisamente abbiamo $X sube A \setminus \{ 7\}$.
In più, sappiamo che un elemento di $X$ è fissato, perché $6 in X$: ciò significa che:

$X = \{ 6\} uu X^\prime$,

in cui $X^\prime$ è il sottoinsieme dei quattro elementi di $X$ diversi da $6$; perciò $|X^\prime| = 4$ ed $X^\prime sube A \setminus \{ 6,7\}$.
Da questo ragionamento segue che il numero di insiemi $X$ che soddisfano le richieste della traccia è uguale al numero di sottoinsiemi $X^\prime$ di $A\setminus \{ 6,7\}$ contenenti quattro elementi; quindi basta contare questi ultimi.

I sottoinsiemi di $A\setminus \{ 6,7\}$ contenenti quattro elementi sono tanti quante le combinazioni senza ripetizione di $n=12$ oggetti (i.e., gli elementi di $A\setminus \{ 6,7\}$) di lunghezza $k=4$ (i.e., $|X^\prime|$) ed il Calcolo Combinatorio fornisce il numero esatto attraverso l'uso di un opportuno coefficiente binomiale: tale numero è:

$C_4^(12) := ((12), (4)) = (12!)/(4! * 8!) = (12*11*10*9*8!)/(4*3*2*8!) = 495$.

Dunque gli insiemi $X$ che ci viene chiesto di contare sono $495$.