Combinaciones de números aleatorios que no se repitan

[NSD]

Al fin logre hacerlo andar tras mucha horas sin dormir y varias tasas de cafe!!

Gracias por la ayuda, tratare de explicar como lo resolví para que si alguien mas tiene el mismo problema le sirva de ayuda.

Tanto los algoritmos de @informacionsys como el de @MMan y el sugerido por @pateketrueke y también la solución 1 propuesta en el primer mensaje tienen el mismo gran problema:
Para generar un cartón nuevo, necesitan conocer a los que ya están generados previamente, y, como previamente puede haber hasta 253338471349989000 combinaciones, claro esta que no hay server que soporte levantar todas esas combinaciones a memoria en simultaneo.

La solución que diseñe es la siguiente:

1) Supongamos (hipotéticamente, ya dije que no es posible) que pudiéramos crear un array que contenga las 253338471349989000 combinaciones posibles, a cada una, le correspondería un indice numérico correlativo que la identificaría dentro del array.

2) Supongamos también, que a esa lista de combinaciones la pudiera "desordenar" o "ordenar aleatoriamente" en base a una semilla (seed) de forma tal, que cada vez que la genere, este siempre en el mismo orden.

3) Cada cliente tiene un ID autoincrementado único en la base de datos, que se podría corresponder con los indices de la lista de combinaciones ordenada aleatoriamente.

4) Afirmemos que se puede obtener la combinación de una posición de la lista, sin generar a todas las demás combinaciones, es decir, obtener una combinación sin conocer a la lista completa.

5) El resultado, es que cada alta de un nuevo cliente, lleva asociada una combinación de números aleatoria (que seria el cartón del bingo que le corresponde) única, sin mas requisitos que tener un campo autoincremental como clave primaria.

6) Para desordenar la lista, el algoritmo de fisher-yates (comúnmente usado para la reproducción de listas de canciones aleatoriamente y sin repetición) con semilla, es la solución genial.

7) El código de la solución comentado:

Código PHP:

<?php
    class Factorial
    {
        /*/
         * Factoriales previamente calculados, como siempre se usan los mismos
         * y ademas son pocos, no hace falta recalcularlos todo el tiempo.
        /*/
        private static $cache = [];
        
        /*/
         * Calcular el factorial de un numero si no esta cacheado.
        /*/
        public static function calc($nro) {
            
            if(!array_key_exists($nro, self::$cache))
            {
                self::$cache[$nro] = 1;
                $numero = $nro;
                while($numero >= 1 && (self::$cache[$nro] *= $numero--));                
            }
            
            return self::$cache[$nro];
        }
    }
 
    /*/
     * @param $items array Los elementos que pueden componer un carton.
     * @param $cantidad int La cantidad de elementos por carton.
     * @param $posicion_buscada int La posicion o numero de carton buscada.
    /*/
    function carton($items, $cantidad, $posicion_buscada)
    {        
        // Una semilla constante, permite desordenar siempre de la misma manera.
        mt_srand(123456789);
        
        // Recorrer los todos elementos.
        for($posicion=count($items)-1; $posicion; $posicion--)
        {
            // Realizar los intercambios.
            $posicion_nueva = mt_rand(0, $posicion);
            $backup = $items[$posicion];
            $items[$posicion] = $items[$posicion_nueva];
            $items[$posicion_nueva] = $backup;
        }
        unset($posicion, $posicion_nueva, $backup);
        
        // Variables de uso general.
        $carton = [];
        $items_count = count($items);
        $posicion_actual = 0;
        
        // Para cada elemento que tengo que agregar al carton.
        for($elemento=0; $elemento<$cantidad; $elemento++)
        {
            // Variables para uso de cada elemento en particular.
            $items_count_combinacion = $items_count;
            $items_count_avaible = $items_count - $cantidad + $elemento;            
            $cantidad_elementos = $cantidad - $elemento;            
            $posicion_tope = $posicion_actual;
            
            // Recorrer cada item disponible.
            for($item_numero = 0; $item_numero<=$items_count_avaible; $item_numero++)
            {
                $mc = $items_count_combinacion - $item_numero - 1;
                $nc = $cantidad_elementos - 1;  
                // Hasta que posicion le corresponde este elemento.
                $posicion_tope += (Factorial::calc($mc) / (Factorial::calc($nc) * Factorial::calc($mc - $nc)));
                $item = array_shift($items);
                $items_count--;
                
                // Si la posicion buscada es menor al tope que le corresponde al elemento.
                if($posicion_buscada <= $posicion_tope)
                {
                    // Asignar el elemento al carton.
                    $carton[] = $item;
                    break;
                }
                else // Seguir buscando desde el tope en adelante.
                    $posicion_actual = $posicion_tope;
            }
        }
        
        // El carton vuelve ordenado.
        sort($carton);
        
        return $carton;
    }
    
    // Test: Generar los primeros 100 cartones.
    $cartones = [];
    $items = range(0, 99);    
    for($idx=1; $idx<=100; $idx++)
        $cartones[] = implode(", ", carton($items, 15, $idx));
    var_dump($cartones);