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 = ⟨s₁, s₂, … s_n⟩        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 = {h₁, h₂, … h_x, v₁, v₂, … v_y},

where h_n represents a horizontal segment, and v_n 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,

• ⟨h₁, h₂, h₃, v₁, v₂⟩,
• ⟨h₁, h₃, h₂, v₁, v₂⟩, and
• ⟨h₁, h₃, h₂, v₂, v₁⟩.

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 = {h₁, h₂, h₃, h₄, v₁, v₂, v₃},

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