Contar el número de los distintos sistemas de

Question

Esta es una enumeración problema junto con algunos de la lotería de problemas.

Dado un entero $N \ge 5$. Deje un billete de ser un conjunto de 5 enteros distintos entre $1$$N$. Dado un entero $T$$1$${{N}\choose{5}}$. Vamos a un sistema de tamaño $T$ ser un conjunto de $T$ distintas entradas.

Dado $N \ge 5$, quiero contar cómo muchos sistemas distintos de tamaño $T$ existen.

Dos sistemas de $S_1$ $S_2$ son distintos si no podemos encontrar una permutación de $\{1,..,N\}$, por lo que que la imagen de $S_1$ bajo permutación es $S_2$.

He probado algunos cálculos para valores pequeños de a$N$$T$.

$N=7$

$T= 1, 2, 3, 4, 5, 6, 7, 8, 9$

número de los distintos sistemas de = $1, 2, 5, 10, 21, 41, 65, 97, 131, 148$

(Parece que esta secuencia de números se conoce como A008406 en oeis.org)

$N=8$

$T= 1, 2, 3, 4, 5, 6, 7, 8, 9$

número de los distintos sistemas de = $1, 3, 11, 52, 252, 1413, 7812, 41868, 207277$

$N=9$

$T= 1, 2, 3, 4, 5, 6, 7 $

número de los distintos sistemas de = $1, 4, 20, 155, 1596, 20528, 282246$

Hay un método para "adivinar" los números y encontrar el más grande de los valores ?

Me pregunto si Polya enumeración puede ser utilizado allí. Yo actualmente no se sabe cómo.

Actualización: echar un vistazo a http://ac.cs.princeton.edu/home/

Deje $s(T,N)$ ser el número de los distintos sistemas de tamaño $T$ ($1 \le T \le{{N}\choose{5}}$), dado $N$.

$\forall N \ge 5, s(1,N) = 1$

$\forall N \ge 10, s(2,N) = 5$

$\forall N \ge 15, s(3,N) = 44$

Answer 1

Esto parece ser un problema interesante que puede ser atacada mediante Potencia la Enumeración de grupos en conjuntos como se describe en bastante detalle en la siguiente MSE enlace.

Ese enlace se describe el número de los diferentes subconjuntos de un estándar $52$ tarjeta de la cubierta bajo el traje de permutación. Aquí tenemos el grupo de permuting la ranuras en las que vamos a distribuir las cartas es el grupo simétrico y el grupo permuting tarjetas es la cardinalidad de las veinticuatro inducida por la acción en las tarjetas de todas las permutaciones de los cuatro palos.

El billete de lotería problema que aquí se propone sigue exactamente el mismo modelo, sólo que ahora estamos distribución de boletos en las ranuras de ser permutada por el grupo simétrico y el grupo que actúa sobre las entradas la inducida por la acción del grupo simétrico $S_N.$ El número de términos en el ciclo de los índices de $Z(S_N)$ $Z(S_T)$ está dado por la partición función y obtenemos un algoritmo que es de asintóticamente orden inferior que el ingenuo $N!\times T!.$

La única que no es cuestión trivial, que no es ya figuran en el solución para la distribución de tarjetas es cómo calcular el ciclo de índice de la inducida por la acción de $S_N$ ${N\choose Q}$ boletos de $Q$ elementos. Esto se puede hacer de una manera bastante eficaz mediante el cálculo de una representante de la permutación de la forma del ciclo de índice del grupo simétrico, dejándola actuar en las entradas, y de factoring, el resultado en los ciclos de contribución a la deseada ciclo de índice.

Establecimiento $Q=5$ como en la cuestión que debemos obtener para $N=7$ la secuencia $$1, 2, 5, 10, 21, 41, 65, 97, 131, 148, 148, 131,\ldots$$ para $N=8$ la secuencia $$1, 3, 11, 52, 252, 1413, 7812, 41868, 207277, 936130, 3826031,\\ 14162479,\ldots$$ para $N=9$ la secuencia $$1, 4, 20, 155, 1596, 20528, 282246, 3791710, 47414089, 542507784,\\ 5659823776,53953771138,\ldots$$ y finalmente, para $N=10$ la secuencia $$1, 5, 28, 324, 5750, 142148, 3937487, 108469019, 2804300907,\\ 66692193996,1452745413957, 29041307854703,\ldots.$$

Para ilustrar la buena complejidad de este algoritmo es aquí el secuencia para $N=13:$ $$1, 5, 42, 813, 34871, 2777978, 304948971, 37734074019,\\ 4719535940546, 566299855228261, 63733180893169422,\\ 6674324951638852138,\ldots$$

Finalmente obtenemos para $N$ variable $Q=5$ $T=3$ la secuencia $$0, 0, 0, 0, 0, 1, 5, 11, 20, 28, 35, 39, 42, 43,\\ 44, 44, 44, 44,\ldots$$

El Arce código para calcular estos fue el siguiente:

con(planta);
con(numtheory);

pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

 terml := [];

 cf := varp;
 para v en indets(varp) ¿
 d := grado(varp, v);
 terml := [op(terml), seq(v, k=1..d)];
 cf := cf/v^d;
od;

 [cf, terml];
end;

pet_autom2cycles :=
proc(src, aut)
numa local, numsubs;
local de marcas, pos, cycs, cpos, clen;

 numsubs := [seq(src[k]=k, k=1..nops(src))];
 numa := subs(numsubs, aut);

 marcas := Array([seq(true, pos=1..nops(aut))]);

 cycs := []; pos := 1;

 mientras pos <= nops(aut) 
 si las marcas[pos] 
 clen := 0; cpos := pos;

 mientras que las marcas[cpos] ¿
 marcas[cpos] := false;
 cpos := numa[cpos];
 clen := clen+1;
od;

 cycs := [op(cycs), clen];
fi;

 pos := pos+1;
od;

 volver mul(a[cycs[k]], k=1..nops(cycs));
end;

pet_cycleind_symm :=
proc(n)
local p, s;
opción de recordar;

 si n=0 entonces devolver 1; fi;

 ampliar(1/n*añadir(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_flat2rep :=
proc(f)
local p, q, res, t, len;

 q := 1; res := [];

 para t en f ¿
 len := op(1, t);
 res := [op(res), seq(p, p=q+1..q+len-1), q];
 q := q+len;
od;

res;
end;

pet_cycleind_tickets :=
proc(N, P)
 opción de recordar;
 local cind, entradas, q, plazo, rep, subsl, ptickets,
 idx, plana;

 si N=1 entonces
 idx : = [[1]]
otra cosa
 idx := pet_cycleind_symm(N);
fi;

 cind := 0;

 entradas := convertir(a elegir({sec(q, q=1..N)}, P), `la lista`);

 durante el plazo en idx ¿
 plano := pet_flatten_term(plazo);
 rep := pet_flat2rep plano ([2]);

 subsl := [seq(p=rep[p], p=1..N)];

 ptickets := subs(subsl, entradas);

 cind := cind +
 plano[1]*pet_autom2cycles(entradas, ptickets);
od;

cind;
end;


X :=
proc(N, P, T)
 opción de recordar;
 local idx_slots, res, a, b,
 flat_a, flat_b, cycs_a, cycs_b, q,
 tbl_a, tbl_b, f1, f2, f3;

 si T=1 entonces
 idx_slots : = [[1]]
otra cosa
 idx_slots := pet_cycleind_symm(T);
fi;

 res := 0;

 para una en idx_slots ¿
 flat_a := pet_flatten_term(a);
 cycs_a := sort(flat_a[2]);

 tbl_a := tabla();
 por q en convertir(cycs_a, 'conjunto múltiple') 
 tbl_a[op(1, p[1])] := p[2];
od;

 f1 := map(p -> op(1, q), cycs_a);
 f1 := mul(f1[p], p=1..nops(cycs_a));

 f2 := convert(map(p -> op(1, q), cycs_a), 'conjunto múltiple');
 f2 := map(q -> p[2], f2);
 f2 := mul(f2[p]!, q=1..nops(f2));

 para el b en pet_cycleind_tickets(N, P) ¿
 flat_b := pet_flatten_term(b);
 cycs_b := sort(flat_b[2]);


 tbl_b := tabla();
 por q en convertir(cycs_b, 'conjunto múltiple') 
 tbl_b[op(1, p[1])] := p[2];
od;

 f3 := 1;
 por q en [índices(tbl_a, 'nolist')] ¿
 si el tipo(tbl_b[q], entero), a continuación,
 f3 := f3*binomial(tbl_b[q], tbl_a[q]);
otra cosa
 f3 := 0;
fi;
od;

 res := res + f3*f2*f1*flat_a[1]*flat_b[1];
od;
od;

res;
end;

Anexo A Viernes De 14 De Agosto De 2015. La secuencia de $Q=5$ $N=20$ es $$1, 5, 44, 966, 53484, 7023375, 1756229468, 710218125299, \\ 411620592905173, 308212635851733551, 271743509344779773214,\ldots$$

Anexo Sat El 15 De Agosto De 2015. La secuencia de $Q=5$ $N=22$ es $$1, 5, 44, 966, 53529, 7041834, 1773511264, 734330857318, \\ 452455270344141, 383969184978128899, 416614280701828877344, \\ 536531456518633409220043, 766723127226754935510254929,\ldots$$

Anexo Mié Ago 19 De 2015. La secuencia de $Q=5$ $N=24$ es $$1, 5, 44, 966, 53534, 7043732, 1775444689, 737776095236, \\ 460462767067281, 405308264117856150, 477303563740811267063, \\ 712445246443357547546003, 1271053814158420923816386794,\ldots$$

Answer 2

Hay $\binom{N}{5}$ posible boletos, usted está preguntando cuántas $T$-subconjuntos de los que hay, es decir, el número de sistemas es:

$$ \binom{\binom{N}{5}}{T} $$

(de alguna manera me siento solo estoy siendo estúpido aquí... no puede ser que fácil?)