Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the following arithmetic function, $f(a,b) = (a+1, \lceil a- \frac{a}{b} \rceil , \lceil a- \frac{2a}{b} \rceil, \dots, \lceil \frac{a}{b} \rceil, 1)$, where all terms except the first and last are computed by the application of a ceiling function.

For any pair of positive integers $(a,b)$, the vector $f(a,b)$ consists of the terms of an integer partition of length $a+1$. Moreover, $f(a,b)$ and $f(b,a)$ represent dual partitions and have reflected Ferrers Diagrams. This can be proved by recalling the identity \begin{eqnarray} \sum_{j = 0}^{b-1} \left \lceil \tfrac{a(b-j)}{b} \right \rceil = \sum_{j = 0}^{a-1} \left \lceil \tfrac{b(a-j)}{a} \right \rceil. \end{eqnarray} (Going in the other direction, one can use the methods outlined here to give a neat combinatorial proof of this ceiling summation identity.)

In general, these integer partitions contain no $0$s, contain at least one $1$ and at most $a$ $1$s.

Question: Are these partitions a special (read named) subset of the standard partitions?

Problem 1: Determine all pairs $(a,b)$ such that $f(a,b)$ are the terms of an integer partition of $k$ for a fixed $k > 1$. Determine a simple way to find $k$ from $a$ and $b$ (and not by simply adding the terms of the defining relation).

Problem 2: Find other symmetries like $f(a,b) \leftrightarrow f(b,a)$.

(Motivation) For example, $f(2,3) = (4,2,1)$, $f(3,2) = (3,2,1,1)$, $f(1,5) = (6,1)$ and $f(5,1) = (2,1,1,1,1,1)$, which are dual integer partitions of $7$.

Problem 3: Give an interpretation to the sequence {$f(a,b)$} in terms of $a$ and $b$ for fixed $a$ or $b$.

(Motivation) The sequence {$f(1,b)$} consists of terms of the form $(2,1, \dots, 1)$ with $b + 1$ $1$s, which are integer partitions of $b+2$; {$f(2,b)$} consists of terms of the form $(3, 1), (3,1,1), (3,2,1)$ or $(3, 2, \dots, 2, 1, \dots, 1)$ which are each integer partitions of those integers greater than 3 not divisible by $3$; {$f(3,b)$} consists of special integer partitions of integers congruent to {$1,2,5$} mod $6$. Similarly, {$f(4,b)$} consists of integer partitions of integers congruent to {$1, 2, 3$} mod $5$ or {$1,2,6,8$} mod $10$; {$f(5,b)$} consists of integer partitions of integers congruent to {$1, 2, 4$} mod $6$, etc.

Here is some Mathematica code that might be useful:

f[a_, b_] := Flatten[{a + 1, Table[Ceiling[a - j a/b], {j, 1, b - 1}], 1}];

a = 2; Table[Total@f[a, b], {b, 1, 100}]

Thanks!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Here's an answer to the second part of Problem 1: $$k = \frac{(a+1)(b+1) - \gcd(a,b) + 3}{2}.$$

According to your definition, $$k = 1 + (a+1) + \sum_{j=1}^{b-1} \left\lceil \frac{ja}{b} \right\rceil.$$ Now, $\left\lceil \frac{ja}{b} \right\rceil = \left\lfloor \frac{ja + b - 1}{b} \right\rfloor.$ (See, for example, Exercise 3.12, p.96, in Concrete Mathematics, 2nd edition.)

It is known that $$\sum_{j=0}^{b-1} \left\lfloor \frac{aj + x}{b} \right\rfloor = d \left\lfloor \frac{x}{d} \right\rfloor + \frac{(a-1)(b-1)}{2} + \frac{d-1}{2},$$ for any real number $x$, where $d = \gcd(a,b)$. (See, for example, Eq. 3.32, p. 94, of Concrete Mathematics, 2nd edition.) We have $x = b-1$.

Then $$d \left\lfloor \frac{b-1}{d} \right\rfloor = d\frac{b-1}{d} - d \left\{\frac{b-1}{d}\right\} = b-1 - d \left\{\frac{b}{d} - \frac{1}{d}\right\} = b - 1 - d \frac{d-1}{d} = b-d,$$ where $\{x\}$ denotes the fractional part of $x$. (The second-to-last step holds because $d | b$.)

Putting everything together yields $$k = a + 2 + b - d + \frac{(a-1)(b-1)}{2} + \frac{d-1}{2},$$ and then combining terms gets the rest.


The elements in $f(a,b)$ are closely related to Spec$(\frac{a}{b}) = \{\lfloor \frac{a}{b}\rfloor, \lfloor\frac{2a}{b}\rfloor, \lfloor\frac{3a}{b}\rfloor, \ldots \}$, although you want ceilings, and you want to stop when the multiplier is $b-1$. You may find the discussion of Spec$(\alpha)$ in Concrete Mathematics helpful. (In fact, when I looked at your problem I thought, "This reminds me of the discussion of spectra in Concrete Math," and then using results in there it wasn't too difficult to find the expression for $k$.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.