# Matrices for binary relations? Fwd: TOPIC:Sequences

Meeussen Wouter (bkarnd) wouter.meeussen at vandemoortele.com
Thu Nov 24 12:07:29 CET 2005

```sounds like Set Partitions and Bell Numbers.
The binary matrix looks like the non-attacking rooks picture of those Set Partitions.

BellList[1] = {{{1}}}; (* the basic case *)

BellList[n_Integer?Positive] := BellList[n] = (* do some caching *)
Flatten[      Join[
Map[ReplaceList[#,{S__}->{S,{n}}]&, BellList[n-1]],
Map[ReplaceList[#,{b___,{S__},a___}->{b,{S,n},a}]&, BellList[n-1]]],
1]

W.

-----Original Message-----
From: Antti Karttunen [mailto:antti.karttunen at gmail.com]
Sent: donderdag 24 november 2005 10:56
To: seqfan at ext.jussieu.fr; s040321 at student.dtu.dk
Subject: Matrices for binary relations? Fwd: TOPIC:Sequences

With Kristjan's permit, I'll post his question to the list:
on the To:-line, as he is not a memeber of SeqFan-list.

---------- Forwarded message ----------
From: Kristjan Haukur Flosason <s040321 at student.dtu.dk>
Date: Nov 22, 2005 5:07 PM
Subject: TOPIC:Sequences
To: antti.karttunen<#>gmail.com

Hi Antti,
I am working on my M.Sc. thesis in electrical engineering at DTU in Denmark and I got stuck in a combinatorial problem. I need to generate a number of alternative solutions that will later be examined for feasibility. Since I saw your name on the Encyclopedia of Integer Sequences, I thought you might have a hint for me. The problem formulation I am facing is the following:
Given are n objects x1…xn and binary relational matrix FRij. The objects are to be assigned to slots where each slot can contain one or more objects. Two objects x i and xj can only exist in the same slot if their relation is given with FRij = 1. FRij = 1 does not force the objects into the same slot. How many alternative assignments are possible?
Moreover: Which algorithm can be used to efficiently find all alternative assignments?
Do you have a hint on how to approach a solution, where to find www resources or other hints?
Best regards,
--------------------------------
Kristján Haukur Flosason
stud.nr. s040321

Ørsted-DTU, Automation
- byg. 326, rum 117 -
DK 2800, Kgs. Lyngby
Mobile: 2964 3674
E-mail: s040321 at student.dtu.dk
--------------------------------

===============================
This email is confidential and intended solely for the use of the individual to whom it is addressed.
If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited.
You are explicitly requested to notify the sender of this email that the intended recipient was not reached.

```