// Cuenta de verdad las hojas y los nodos de los dos árboles, sin escribir cada resultado.
#include <stdio.h>

#define MAX_ITEMS 16

typedef struct {
    long leaves;
    long nodes;
} Count;

static void subsets(int n, int index, Count *count) {
    count->nodes++;
    if (index == n) {
        count->leaves++;
        return;
    }
    subsets(n, index + 1, count);
    subsets(n, index + 1, count);
}

static void permutations(int n, int *used, int depth, Count *count) {
    count->nodes++;
    if (depth == n) {
        count->leaves++;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;
            permutations(n, used, depth + 1, count);
            used[i] = 0;
        }
    }
}

int main(void) {
    printf(" n | subconjuntos    nodos | permutaciones      nodos\n");
    for (int n = 1; n <= 10; n++) {
        Count sub = {0, 0};
        Count perm = {0, 0};
        int used[MAX_ITEMS] = {0};

        subsets(n, 0, &sub);
        permutations(n, used, 0, &perm);
        printf("%2d | %12ld %8ld | %13ld %10ld\n", n, sub.leaves, sub.nodes, perm.leaves, perm.nodes);
    }
    return 0;
}