Lovegrove Mathematicals

logo

"Dedicated to making Likelinesses the entity of prime interest"

|ΩN(n)|

Introduction

The formal proof that |ΩN(n)|=n+(N-1)CN-1 is as a consequence of the Combination Theorem.

I for one, however, do not like having to remember formulæ, so it is fortunate that there is a less formal way to reconstruct this particular one more or less instantly. Like a lot of things, it takes longer to explain it than to do it.

The Reconstruction

We begin with a diagrammatic way to display an integram of degree N and sample size n. In this example, N=6 and n=19.

We take any line of any length, and on it we mark any (N-1) points to subdivide it into N subintervals. Each subinterval represents one of the outputs "1",..."N". Call those (N-1) points the 'boundary marks'.

starting to show an integram

Using a different symbol, in the interval representing output "i" we make g(i) marks, where g is the integram being represented. Call these the 'observation marks'.

the integram

We have now made (N-1) boundary marks and n observation marks, giving a total of n+(N-1) marks. The numbers, here, might seem familiar -look back at the formula we are trying to develop.

Now blur over the differences between the two different types of mark by making them all the same and removing the labelling.

blurring the difference

We can now show any integram of degree N(=6) and sample size n(=19) by selecting any (N-1) points to become the boundary marks. Here are two examples.

two different integrams

How many ways are there to do this, that is to select (N-1) from n+(N-1)?  There are n+(N-1)CN-1 ways, each of which gives a different integram, and each integram corresponds to one such way. So |ΩN(n)|=n+(N-1)CN-1 .

So, how many integrams are there of degree 17 and sample size 64? There are 64+16=80 marks, of which 16 are boundary marks, so the number of integrams is 80C16 = 80!/16!64! = 2.70E+16.