## Monday, October 31, 2011

### Quiz Time: X-Y Path Permutations

Q: In an x-y coordinate system (or Cartesian coordinate system), how many paths are there from the point of origin to a point with coordinates ⟨x, y⟩, where
• x ∧ y ∈ Z + (x and y are positive integers),
• a path is built up from exactly x + y segments, each with a length of one (1), and
• a line segment must be either horizontal or vertical?

See below for answer.

A: When visualizing the path, we can imagine a cursor, drawing the path starting from ⟨0, 0⟩, moving to ⟨x, y⟩ in x + y discrete steps.

This movement forms an n-length list of segments, where n = x + y.

L = ⟨s1, s2, … sn⟩        n = x + y

A segment can either be horizontal (h), or vertical (v). To reach from the point of origin to ⟨x, y⟩ we need to move the cursor x units to the right (horizontally), and y units up (vertically). This gives us the following set of segments, which corresponds to the list L,

S = {h1, h2, … hx, v1, v2, … vy},

where hn represents a horizontal segment, and vn a vertical.

One way of getting all the possible paths is to list all the permutations of the set S. The number of permutations of an n-element set is n! (n factorial). The problem with this approach, however, is that it gives us several identical paths. Consider the three lists,
• ⟨h1, h2, h3, v1, v2⟩,
• ⟨h1, h3, h2, v1, v2⟩, and
• ⟨h1, h3, h2, v2, v1⟩.

These are all identical as paths. In fact, all h-segments should be considered equivalent, and so should v-segments. Therefore, to get the number of unique lists, we need to divide our result up into equivalence classes, and then count the number of these.

Since there are x number of h-segments, there are x! lists in each class of lists that should be considered equivalent with respect to their h-segments. Similarly, there are y! list arrangements that correspond to the same y-element set.

Dividing the number of S permutations (x + y)! by x! × y! therefore gives us the number of unique paths from ⟨0, 0⟩ to ⟨x, y⟩.

This is also known as the binomial coefficient. We use the familiar n choose k-notation to express this as:

The number of paths from ⟨0, 0⟩ to ⟨x, y⟩ is therefore:

# Example:

Take x = 4, and y = 3.
This gives us,

S = {h1, h2, h3, h4, v1, v2, v3},

and n = 7.

By selecting the various elements of S, and putting them in a list, we get the (x + y)! number of permutations of S:

This gives us 7 × 6 × 5 × 4 × 3 × 2 × 1 (= 5040) lists. To partition this set of lists into groups, each containing all the lists we consider equivalent, we recollect that an x-element set has x! permutations:

This gives us 7! / (4! × 3!) = 35 paths.

The following is a C++ program that draws the paths from the origin to a point ⟨x, y⟩. It uses the Qt library:

cartpathwidget.h:
```#ifndef CARTPATHWIDGET_H
#define CARTPATHWIDGET_H

#include <QWidget>
#include <vector>

class QSlider;
class QEvent;

class CartPathWidget : public QWidget
{
Q_OBJECT

public:
CartPathWidget(int x, int y, QWidget *parent = 0);
~CartPathWidget() {}

void rebuild();

protected slots:
void setX(int x);
void setY(int y);

protected:
bool eventFilter(QObject *object, QEvent *event);

private:
void build(int n, int x = 1);

int m_x;
int m_y;
std::vector<bool> m_e;
std::vector<std::vector<bool> > m_result;
QSlider *const m_slider;
};

#endif // CARTPATHWIDGET_H```
mainwindow.h:
```#ifndef MAINWINDOW_H
#define MAINWINDOW_H

#include <QtGui/QMainWindow>

class MainWindow : public QMainWindow
{
Q_OBJECT

public:
explicit MainWindow(QWidget *parent = 0);
~MainWindow();
};

#endif // MAINWINDOW_H```
cartpathwidget.cpp:
```#include <QSpinBox>
#include <QSlider>
#include <QEvent>
#include <QHBoxLayout>
#include <QPainter>
#include "cartpathwidget.h"

CartPathWidget::CartPathWidget(int x, int y, QWidget *parent)
: QWidget(parent),
m_x(x),
m_y(y),
m_slider(new QSlider(Qt::Vertical))
{
rebuild();
QWidget *w = new QWidget;
QHBoxLayout *layout = new QHBoxLayout;
QVBoxLayout *vlayout = new QVBoxLayout;
vlayout->addLayout(layout);
QHBoxLayout *hlayout = new QHBoxLayout;
vlayout->addLayout(hlayout);
setLayout(vlayout);
layout->addWidget(w);
layout->addWidget(m_slider);
w->installEventFilter(this);
QSpinBox *sb1 = new QSpinBox;
sb1->setRange(1, 9);
sb1->setValue(m_x);
hlayout->addWidget(sb1);
QSpinBox *sb2 = new QSpinBox;
sb2->setRange(1, 9);
sb2->setValue(m_y);
hlayout->addWidget(sb2);
connect(m_slider, SIGNAL(valueChanged(int)), w, SLOT(update()));
connect(sb1, SIGNAL(valueChanged(int)), this, SLOT(setX(int)));
connect(sb2, SIGNAL(valueChanged(int)), this, SLOT(setY(int)));
}

void CartPathWidget::setX(int x)
{
if (m_x != x) {
m_x = x;
rebuild();
}
}

void CartPathWidget::setY(int y)
{
if (m_y != y) {
m_y = y;
rebuild();
}
}

void CartPathWidget::rebuild()
{
m_result.clear();
m_e.clear();
for (int i = 0; i < m_x + m_y; ++i)
m_e.push_back(false);
build(m_y + 2);
m_slider->setRangesetValue(0);
update();
}

bool CartPathWidget::eventFilter(QObject *object, QEvent *event)
{
if (QEvent::Paint == event->type()) {
QWidget *w = qobject_cast<QWidget *>(object);
if (!w)
return QWidget::eventFilter(object, event);
QPainter painter(w);
QTransform t;
t.translate(w->width() / 4, w->height() / 4);
t.scale(w->width() / (m_x * 2), w->height() / (m_y * 2));
painter.setTransform(t);
// Draw grid
for (int x = 0; x <= m_x; ++x) {
painter.drawLine(x, 0, x, m_y);
}
for (int y = 0; y <= m_y; ++y) {
painter.drawLine(0, y, m_x, y);
}
// Draw path
const std::vector<bool> &path = m_result[m_slider->value()];
int x = 0;
int y = 0;
QPen pen;
pen.setColor(Qt::red);
pen.setWidthF(0.15);
painter.setPen(pen);
std::vector<bool>::const_iterator i;
QPolygonF p;
p.push_back(QPointF(m_x, 0));
for (i = path.begin(); i != path.end(); ++i) {
(*i ? x : y) += 1;
p.push_back(QPointF(m_x - x, y));
}
painter.drawPolyline(p);
}
return QWidget::eventFilter(object, event);
}

void CartPathWidget::build(int n, int x)
{
int e = n - (m_y + 1);
for (int c = x; c < n; ++c) {
m_e[c - 1] = true;
(e < m_x) ? build(n + 1, c + 1) : m_result.push_back(m_e);
m_e[c - 1] = false;
}
}```
main.cpp:
```#include <QtGui/QApplication>
#include "mainwindow.h"

int main(int argc, char *argv[])
{
QApplication a(argc, argv);
MainWindow w;
w.show();

return a.exec();
}```
mainwindow.cpp:
```#include "mainwindow.h"
#include "cartpathwidget.h"

MainWindow::MainWindow(QWidget *parent)
: QMainWindow(parent)
{
setCentralWidget(new CartPathWidget(3, 2));
}

MainWindow::~MainWindow()
{
}```
paths.pro:
```QT       += core gui

TARGET = paths
TEMPLATE = app

SOURCES += main.cpp\
mainwindow.cpp \
cartpathwidget.cpp

HEADERS  += mainwindow.h \
cartpathwidget.h```