Partitions of set with maximal cardinality

Question

Is there a way to compute the number of partitions such that each set in the partition has a cardinality lower or equal to two? If yes, is there also an efficient algorithm to compute these partitions?

Answer 1

Let us call "classes" the subsets of a given partition.

One can associate to any of these partitions in a unique way a symmetric boolean ((0-1) entries) matrix $P$ with $P_{i,j}=0$ everywhere excepted:

• $P_{i,i}=1$ if $\{i\}$ is a "class" with one-element (singleton),

• $P_{i,j}=P_{j,i}=1$ if $\{i,j\}$ is a "class" with two elements.

We can therefore reformulate the issue into counting the number of symmetric boolean matrices with sum of lines or columns equal to $1$, i.e., symmetric permutation matrices, i.e., as well permutation matrices $P$ such that $P^2=I$.

This is known as the OEIS A000085 with recurrence relationship:

$$a_n=a_{n-1}+(n-1)a_{n-2}$$

A reference here.

Edit: This approach provides a rather direct way to program all these partitions. Here is a Matlab program which does the job for any (reasonable) $n$ :

n=5;
T=perms(1:n), % the n! x n array of all permutations
II=eye(n); % unit matrix
p=0; % counts the number of solutions
for k=1:factorial(n)
    P=II(:,T(k,:)); % k-th permutation matrix
    if P==P'
        p=p+1;fprintf('%d: ',p);
        D=diag(P);
        E=find(D');
        if any(E);fprintf('{%d}',E);end;
        P=P-diag(D); % getting rid of diag. entries
        [I,J]=find(P); % indices of nonzero entries
        s=length(I);
        if s>0
        K=[I,J];U=find((J-I)>0);K=K(U,:);L=size(K,1);
        for k=1:L;fprintf('{%d,%d}',K(k,:));end;
        end;
    fprintf('\n');
    end;
end;

Output for $n=5$:

 1: {3}{2,4}{1,5}
 2: {4}{2,3}{1,5}
 3: {2}{3}{4}{1,5}
 4: {2}{3,4}{1,5}
 5: {3}{1,4}{2,5}
 6: {5}{2,3}{1,4}
 7: {2}{3}{5}{1,4}
 8: {2}{1,4}{3,5}
 9: {5}{1,3}{2,4}
 10: {4}{1,3}{2,5}
 11: {2}{4}{5}{1,3}
 12: {2}{1,3}{4,5}
 13: {3}{1,2}{4,5}
 14: {3}{4}{5}{1,2}
 15: {4}{1,2}{3,5}
 16: {5}{1,2}{3,4}
 17: {1}{3}{5}{2,4}
 18: {1}{2,4}{3,5}
 19: {1}{4}{5}{2,3}
 20: {1}{2,3}{4,5}
 21: {1}{2}{3}{4}{5}
 22: {1}{2}{3}{4,5}
 23: {1}{2}{5}{3,4}
 24: {1}{2}{4}{3,5}
 25: {1}{3}{4}{2,5}
 26: {1}{3,4}{2,5}