Problema de trobades

En combinatòria, els números de trobades (o també, números de reencontres) formen una matriu triangular de número entero que enumeren les permutació del conjunt { 1, ..., n } en números especificats de punts fixos, o en atres paraules, en un número determinat de restriccions parcials. Per a n ≥ 0 i 0 ≤ k ≤ n, el número de trobades D_n, k és el número de permutació de { 1, ..., n } que tenen exactament k punts fixos.

Per eixemple, si es donen a l'encert sèt regals a sèt persones diferents, pero es considera el cas de que solament dos van a rebre el regal correcte, hi ha D_7, 2 = 924 formes en que açò podria succeir. Un atre eixemple que se cita a sovint és el d'una escola de ball en 7 parelles, a on, despuix de la pausa del té, se'ls diu als participants que troben "a l'encert" una parella per a continuar, i una volta més, hi ha D_7, 2 = 924 possibilitats de que 2 parelles anteriors es retroben per casualitat.

Valors numèrics

A continuació figura el començ d'esta matriu Plantilla:OEIS:

Plantilla:Diagonal split header	0	1	2	3	4	5	6	7	8
0	1
1	0	1
2	1	0	1
3	2	3	0	1
4	9	8	6	0	1
5	44	45	20	10	0	1
6	265	264	135	40	15	0	1
7	1854	1855	924	315	70	21	0	1
8	14833	14832	7420	2464	630	112	28	0	1

Ordenat pel número d'elements moguts
La forma habitual de mostrar els números de trobades és en columnes corresponents al número de punts fixos $k$. Pero també es poden ordenar en columnes corresponents al número d'elements moguts $i=n-k$ Plantilla:OEIS. Cada entrada és el producte d'un coeficient binomial i un subfactorial. En este orde cada columna correspon a un subfactorial: $T(n,i)=(\genfrac{}{}{0ex}{}{n}{i})\cdot !i$
Plantilla:Diagonal split header 0 1 2 3 4 5 6 7 8 0 1 1 1 0 2 1 0 1 3 1 0 3 2 4 1 0 6 8 9 5 1 0 10 20 45 44 6 1 0 15 40 135 264 265 7 1 0 21 70 315 924 1855 1854 8 1 0 28 112 630 2464 7420 14832 14833	Plantilla:Diagonal split header 0 1 2 3 4 5 6 7 8 0 1⋅1 1 1⋅1 1⋅0 2 1⋅1 2⋅0 1⋅1 3 1⋅1 3⋅0 3⋅1 1⋅2 4 1⋅1 4⋅0 6⋅1 4⋅2 1⋅9 5 1⋅1 5⋅0 10⋅1 10⋅2 5⋅9 1⋅44 6 1⋅1 6⋅0 15⋅1 20⋅2 15⋅9 6⋅44 1⋅265 7 1⋅1 7⋅0 21⋅1 35⋅2 35⋅9 21⋅44 7⋅265 1⋅1854 8 1⋅1 8⋅0 28⋅1 56⋅2 70⋅9 56⋅44 28⋅265 8⋅1854 1⋅14833

Fòrmules

Els números en la columna k = 0 enumeren subfactorialés. D'esta manera

$D_{0,0}=1,$

$D_{1,0}=0,$

$D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})$

per a n no negativa. Resulta que

$D_{n,0}=\lceil \frac{n!}{e}\rfloor ,$

a on la relació es redoneja cap a dalt per a n parell i es redoneja cap a avall per a n impar. Per a n ≥ 1, açò dona el sancer més propenc.

Més generalment, per a qualsevol $k\ge 0$, es té que

$D_{n,k}=(\genfrac{}{}{0ex}{}{n}{k})\cdot D_{n-k,0}.$

La demostració és fàcil una volta que se sap cóm enumerar les restriccions: elegixquen-se els k punts fixos del conjunt de n punts; i després elegixca's l'ajust dels atres n − k punts restants.

Els números D_n,0/(n!) són generats per series de potències i^−z/(1 − z). Análogament, es pot obtindre una fòrmula explícita per a D_n, m de la següent manera:

$D_{n,m}=\frac{n!}{m!}[z^{n-m}]\frac{e^{-z}}{1-z}=\frac{n!}{m!}\sum _{k=0}^{n-m}\frac{(-1{)}^k}{k!}.$

Açò implica immediatament que

$D_{n,m}=(\genfrac{}{}{0ex}{}{n}{m})D_{n-m,0}\text{y }\frac{D_{n,m}}{n!}\approx \frac{e^{-1}}{m!}$

per a n gran i m fix.

Vore també

• Problema de Oberwolfach, un problema matemàtic diferent relacionat en la disposició dels comensals en les taules
• Problema del menage, un problema similar que implica restriccions parcials

Bibliografia

• Riordan, John, An Introduction to Combinatorial Analysis, Nova York, Wiley, 1958, pàgines 57, 58 i 65.
• Plantilla:Mathworld