EGF del gráfico acíclico dirigido mínimo arraigado

Question

Estoy tratando de encontrar la exponencial de generación de función de un mínimo de gráficos acíclicos (que yo llamo dag), donde cada nodo hoja no tiene dos bordes salientes.

Contexto: Un simple árbol algoritmo de compresión consta de guardar repetido subárboles sólo una vez. Más incidentes repetidos árboles son simplemente vinculado a la primera ocurrencia. De esta manera se obtiene un único mínima gráfico acíclico dirigido, y desde que empezamos con un árbol arraigado. Por simplicidad, me gustaría tratar árboles binarios, por lo tanto, dos bordes salientes por nodo hoja no.
Una pregunta natural es lo grande de dags de árboles binarios de tamaño $n$, y la pregunta ha sido respondida aquí (el papel de la Analítica de las Variaciones en el Común de la Subexpresión Problema, por Flajolet et al).

Me gustaría hacer una pregunta diferente, a saber, cómo muchos diferentes dag de tamaño $n$ existen, o, equivalentemente, ¿cuántos arraigada plano de árboles binarios tienen un dag de tamaño $n$?

Como un ejemplo, para $n=3$, tenemos tres árboles, es decir, $a(a(a,a),a(a,a))$, $a(a(a,a),a)$ y $a(a,a(a,a))$.
Para $n=4$ hay $15$ árboles, para $n=5$ hay $111$.
Un prometedor secuencia de OEIS es A001063, pero puedo ni sentido de la ecuación diferencial que ahí se menciona, ni tampoco tengo una combinatoria explicación de la fórmula hay que calcula el $a_{n+1}$, determinado $a_1,\dots,a_n$: $$ a_{n+1} = \sum_{k=0..n} \frac{n!}{k!} \cdot \binom{n-1}{k-1}\cdot a_k $$

Si se solicita, se podría agregar donde me quedé atrapado (sobre todo me trató de dar sentido a la fórmula), pero creo que mi post ya es muy largo.

Addendum. Esta pregunta ha generado sus propias OEIS de la serie (A254789)! Gracias a todos los involucrados!

Answer 1

Me gustaría presentar una secuencia de comandos para calcular este estadístico con el fin de generar actividad en esta pregunta y motivar la investigación en rápido algoritmos con la finalidad de calcular las suficientes condiciones para un OEIS de entrada. Los enlaces de papel muestra que esto probablemente no será todo lo que fácil.

La siguiente secuencia de comandos Perl puede ser usada para calcular este dato hasta $a_7.$ Salidas de las distribuciones del número de los distintos subárboles de un árbol binario en $k$ nodos con $k\le 2^n$ al $a_n$ se calculada.

Hereis la salida para $a_6,$, lo que confirma los valores presentados en de los comentarios.

1: u (1)
2: 2 u^2 (2)
3: u^2 + 4 u^3 (5)
4: 6 u^3 + 8 u^4 (14)
5: 4 u^3 + 22 u^4 + 16 u^5 (42)
6: 32 u^4 + 68 u^5 + 32 u^6 (132)
7: u^3 + 20 u^4 + 152 u^5 + 192 u^6 (365)
8: 10 u^4 + 196 u^5 + 584 u^6 (790)
9: 12 u^4 + 158 u^5 + 1140 u^6 (1310)
10: 160 u^5 + 1436 u^6 (1596)
11: 6 u^4 + 96 u^5 + 1692 u^6 (1794)
12: 68 u^5 + 1568 u^6 (1636)
13: 88 u^5 + 1284 u^6 (1372)
14: 24 u^5 + 1256 u^6 (1280)
15: u^4 + 36 u^5 + 1112 u^6 (1149)
16: 6 u^5 + 760 u^6 (766)
17: 24 u^5 + 854 u^6 (878)
18: 408 u^6 (408)
19: 18 u^5 + 504 u^6 (522)
20: 308 u^6 (308)
21: 416 u^6 (416)
22: 48 u^6 (48)
23: 8 u^5 + 246 u^6 (254)
24: 92 u^6 (92)
25: 160 u^6 (160)
26: 32 u^6 (32)
27: 144 u^6 (144)
28: 0 (0)
29: 72 u^6 (72)
30: 0 (0)
31: u^5 + 52 u^6 (53)
32: 6 u^6 (6)
33: 12 u^6 (12)
34: 0 (0)
35: 42 u^6 (42)
36: 0 (0)
37: 0 (0)
38: 0 (0)
39: 24 u^6 (24)
40: 0 (0)
41: 0 (0)
42: 0 (0)
43: 0 (0)
44: 0 (0)
45: 0 (0)
46: 0 (0)
47: 10 u^6 (10)
48: 0 (0)
49: 0 (0)
50: 0 (0)
51: 0 (0)
52: 0 (0)
53: 0 (0)
54: 0 (0)
55: 0 (0)
56: 0 (0)
57: 0 (0)
58: 0 (0)
59: 0 (0)
60: 0 (0)
61: 0 (0)
62: 0 (0)
63: u^6 (1)
64: 0 (0)
-
u + 3 u^2 + 15 u^3 + 111 u^4 + 1119 u^5 + 14487 u^6

El guión es realmente muy compacto y puede ser que el beneficio de siendo re-escrito en C. Este es el código:

#! /usr/bin/perl -w
#

sub gf2str {
 my ($gf) = @_;

 volver "0" si escalares(teclas(%$gf)) == 0;

 mi @términos;
 foreach my $exp (sort { $a <=> $b } teclas de %$gf){
 mi $q = $gf->{$exp};

 if($n == 1 && $exp == 1){
 push @términos, "u";
}
 elsif($n == 1){
 push @términos, "u^$exp";
}
 elsif($exp == 1){
 push @términos, 
 sprintf "%d", $contr;
}
else{
 push @términos,
 sprintf "%d u^%d", $n, $exp;
}
}

 join(' + ', @términos);
}


PRINCIPAL: {
 mi $mx = shift || 1;

 mi %grand;


 mi $memo = [];
 push @{ $memo->[0]->[0] }, {};

 para(mi $n=1; $n <= 2**$mx; $n++){
 para(mi $m=0; $j<=$n-1; $j++){
 para(mi $dst1 = 0; $dst1 < $mx; $dst1++){
 para(mi $dst2 = 0; $dst2 < $mx; $dst2++){
 si(existe($memo->[$m]->[$dst1]) &&
existe($memo->[$n-1-$m]->[$dst2])){
 mi $t1 = $memo->[$m]->[$dst1];
 mi $t2 = $memo->[$n-1-$m]->[$dst2];

 para mi $ta (@$t1){
 para mi $tb (@$t2){
 mi $árbol = {};

 @$árbol{ llaves %$ta } = 
 (1) x escalares(teclas de %$ta);
 @$árbol{ llaves %$tb } = 
 (1) x escalares(teclas de %$tb);

 $arbol->{$árbol} = 1;

 mi $count = escalar(teclas de %$árbol);
 if($count <= $mx){
 push @{ $memo->[$n]->[$cuenta] },
$árbol;
}
}
}
}
}
}
}

 mi %gf = (); my $total = 0;
 para(mi $dst = 0; $dst <= $mx; $dst++){
si(existe($memo->[$n]->[$dst])){
 mi $val = escalar(@{ $memo->[$n]->[$dst] });
 $gf{$dst} = $val;

 $total += $val;
 $grand{$dst} += $val;
}
}


 print "$n: ";
 imprimir gf2str(\%gf);
 print "($total)\n";
}

 print "-\n";

 imprimir gf2str(\%grand);
 print "\n";
}

Answer 2

OK, ahora que se ve mejor: estoy bastante seguro de que se inicia la secuencia

(1,1)
(2,3)
(3,15)
(4,111)
(5,1119)
(6,14487)
(7,230943)
(8,4395855)
(9,97608831)
(10,2482988079)
(11,71321533887)
(12,2286179073663)
(13,80984105660415)
(14,3144251526824991)
(15,132867034410319359)

y que se computa dentro de un par de segundos, utilizando el siguiente enfoque:

basada en la función de count :: [[Bool]] -> Int donde count xss es el número de dags con map length xss nodos en el nivel respectivo, y en cada nivel, codificado por un elemento xs :: [Bool] de xss, las entradas de xs marcar si este nodo debe tener un predecesor.

En más detalle, aquí está la especificación de count:

Definimos una función (sólo para la especificación, no es en la fuente de abajo) shape :: DAG -> [[Bool]] que toma un DAG (cualquier DAG, puede tener varias raíces), calcula la lista de conjuntos de nivel, a continuación, para cada conjunto, un canónica de pedido (una lista) de sus nodos (lexicográfica izquierdo del niño, el derecho del niño, mediante la ordenación de los niveles inferiores), entonces para cada nodo, si tiene un predecesor (un nodo más alto que los puntos aquí). Ahora count s da el número de Dag d que shape d == s.

El punto es que podemos definir de la count de forma recursiva (inducción por el número de niveles), y que nunca realmente construir Dag - acabamos de contar.

Y mientras contamos, podemos evitar recomputations, usando memoFix (un punto fijo combinador con una memoria caché, la verdad). Usted puede simplemente pensar count arg = case arg ... return $ count ...

Para ejecutar este con ghc, usted necesita los paquetes lens y memoize. Usted puede cargar el código fuente en ghci y evaluar expresiones como count [[False],[True],[True]]. (Parece que el código de sangría aquí está roto. Vigilar que las expresiones del interior do están alineados correctamente.)

import Control.Monad ( guard, forM_ )
import Control.Applicative
import Control.Lens
import Data.List (tails, sort)
import Data.Function.Memoize
import System.IO

type Shape = [[Bool]]

main = forM_ [ 1 .. ] $ \ s -> do
       print ( s, sum $ map count $ shapes s )
   hFlush stdout

shapes s = do  sh <- deep_shapes (s-1) ;  return $ [False] : sh

deep_shapes :: Int -> [Shape]
deep_shapes 0 = return []
deep_shapes s = do
  x <- [ 1 .. s ] ; xs <- deep_shapes (s-x)
  return $ (replicate x True) : xs

count :: Shape -> Int
count = memoFix $ \ self arg -> case arg of
       [] -> 1
       (sh : ape) -> sum $ do
      guard $ and $ map not sh
      top <- pairs (length sh) ape
      return $ self $ apply top ape

type Node = (Int,Int)
type Pair = (Node,Node)

apply :: [Pair] -> Shape -> Shape
apply top shape = 
    foldr ( \ (h,k) sh -> sh & ix (length shape - h) . ix k .~ False ) 
      shape $ do (p,q) <- top ; [p,q]

pairs s shape = pick s $ sort $ do
    let cs = candidates shape
        lower = concat $ drop 1 cs
            top = concat $ take 1 cs
    (left,right) <- [(lower,top),(top,top),(top,lower)]
    (,) <$> left <*> right

candidates :: [[Bool]] -> [[(Int,Int)]]
candidates shape = ( do
   (h,ops) <- zip [length shape, length shape-1 ..] shape
   return $ do (n, _) <- zip [0..] ops ; return (h,n) ) ++ [[(0,0)]]

pick :: Int -> [a] -> [[a]]
pick 0 _ = return []
pick s xs = do
  z : ys <- tails xs ; guard $ length ys >= s-1
      zs <- pick (s-1) ys ; return $ z : zs

Answer 3

EDIT: mucho mejor de enfoque, consulte otra respuesta.

Confirmando sus valores (hasta 8) - con un enfoque diferente, que también debe permitir una más ingenioso método de conteo.

Siguiente programa de necesidades < 30 min (en un núcleo) para imprimir

(1,1)
(2,3)
(3,15)
(4,111)
(5,1119)
(6,14487)
(7,230943)
(8,4395855)

Podemos enumerar canónica de los representantes de estos Dag. Un representante es una lista de pares de números, por ejemplo, [(4,3),(3,2),(1,0),(1,1),(0,0)]. Esto significa que el nodo superior (5) ha dejado niño 4, niño correcto 3, el nodo 4 tiene hijos (3,2), etc., hacia el nodo 1 con los niños (0,0).

El representante canónico si

• todas las parejas son diferentes
• cada nodo (excepto la primera) está vinculado de algún lugar por encima de
• para cada nivel (la distancia de la hoja), las parejas de este nivel son monótonas.

Por ejemplo, el nivel de asignación de es [(0,0),(1,1),(2,2),(3,2),(4,3),(5,4), lo [(1,0),(1,1)] están en el mismo nivel, y esta lista es monótono.

Ahora, en lugar de generar-y-prueba (lo que hace el programa), se debe codificar estas condiciones en la lógica proposicional, y el uso de BDDs para contar.

(EDICIÓN de aquí, el programa original de abajo)

Con un poco de mejora de la representación interna, mi programa (ahora demasiado tiempo para publicar aquí, tal vez puedo jugar código de golf más tarde) dice a9 = 97608831

Me pregunto si podemos usar la siguiente: $a[x_k,..,x_0] =$ el número de dags con $x_h$ nodos en el nivel $h$. (E. g., $a[1,2,1,1]=6$). Aquí está la lista (por $\sum x_i=9$, le llaman a esto "8 nodos" ya que no se tienen en cuenta la hoja)

([1,1,1,1,1,1,1,1,1],2027025)
([1,1,1,1,1,2,1,1],424710)
([1,1,1,1,2,1,1,1],489060)
([1,1,1,1,3,1,1],9108)
([1,1,1,2,1,1,1,1],417690)
([1,1,1,2,2,1,1],208428)
([1,1,1,3,1,1,1],14400)
([1,1,2,1,1,1,1,1],279720)
([1,1,2,1,2,1,1],56844)
([1,1,2,2,1,1,1],188280)
([1,1,2,3,1,1],4764)
([1,1,3,1,1,1,1],6300)
([1,1,3,2,1,1],7200)
([1,2,1,1,1,1,1,1],103950)
([1,2,1,1,2,1,1],20520)
([1,2,1,2,1,1,1],22560)
([1,2,1,3,1,1],348)
([1,2,2,1,1,1,1],74340)
([1,2,2,2,1,1],37368)
([1,2,3,1,1,1],3240)

¿Hay alguna relación que permita calcular estos números, sin mirar ningún árboles, gráficos, dag? Algunas observaciones:

• $a[1,\dots,1]$ $(2k-1)!!$
• y los otros son aún (por lo que debe ser capaz de acelerar la enumeración 2)?

fuente original de código siguiente:

import qualified Data.Set as S
import qualified Data.Map.Strict as M
import Data.List ( sort )
import Control.Monad ( guard, when, forM_ )
import Control.Applicative
import System.IO

main = forM_ [1 .. ] $ \ n -> do
      print (n, length $ filter dag_ok $ candidates n )
  hFlush stdout

type DAG = [(Int,Int)]

dag_ok :: DAG -> Bool
dag_ok dag =
  nodes_different dag && nodes_linked dag && levels_ok dag

nodes_different dag =
  length dag == S.size (S.fromList dag)

nodes_linked dag =
  S.fromList [0 .. length dag-1]
  == S.fromList (do (x,y) <- dag ; [x, y] )

levels_ok dag =
  let n = length dag ; m = levels dag
      s = M.fromListWith S.union $ do (p,h) <- M.toList m ; return (h, S.singleton p)
      in  weakly_monotone ( map snd $ M.toAscList m )
      && and ( do 
         ( h, ps ) <- M.toList s
         return $ monotone $  do p <- S.toDescList ps ; return $ dag !! (n-p)
         )

monotone xs = and $ zipWith (<) xs $ tail xs
weakly_monotone xs = and $ zipWith (<=) xs $ tail xs

levels [] = M.fromList [(0,0)]
levels ((x,y):d) =
  let m = levels d
  in  M.insert (length d+1) (succ $ max ( m M.! x) (m M.! y)) m

candidates 0 = [ []]
candidates n = do
  d <- candidates (n-1)
  x <- [ 0 .. n-1] ; y <- [ 0 .. n-1]
  return ((x,y):d)