각기둥 그래프를 다음과 같이 정의한다. 꼭짓점은 위쪽 각형의 꼭짓점 개와 아래쪽 각형의 꼭짓점 개, 총 개이다. 간선은 다음 세 종류이다.
따라서 간선은 총 개이다.
이 그래프의 각 꼭짓점에 또는 을 적는 방법을 배치라 하자. 이 개의 꼭짓점은 서로 구별되므로, 가능한 배치는 모두 가지이다.
아래 두 조건을 모두 만족하는 배치의 개수를 구하라.
