1
$\begingroup$

I am having difficulty framing this properly.

How many non-decreasing integer sequences are there of length $n$, where each element is bound between $1$ and $m$ inclusive, such that the longest streak of length $l$ is the only streak of that length present?

What I tried:

$$F(n,m,l) = \sum_{k=1}^{l} \sum_{s=0}^{n-k} \sum_{d=1}^{m} F(s,d-1,k-1) F(n-(s+k),m-d,k-1)$$

$l$ is the longest streak length, $m$ is the maximum digit possible (minimum digit is $1$), and $n$ is the length of the sequence. $s$ is the starting position of the streak (if the first element has index $0$ and the last element has index $n-1$). $d$ is the digit being allocated to the streak.

So I suppose I am trying to compute $F(n,m,n)$.

$\endgroup$
  • $\begingroup$ Question 1: do yo mean sequences of integers? Question 2: what did you try, where are you stuck? $\endgroup$ – J.-E. Pin Aug 7 '15 at 16:29
  • $\begingroup$ @J.-E.Pin Yes, integers. And I tried making a function for it but the stopping condition is hard to determine. $\endgroup$ – user259511 Aug 7 '15 at 16:30
  • $\begingroup$ @J.-E.Pin Updated post with my attempt. Edited question for clarity, I had been asking the wrong thing technically $\endgroup$ – user259511 Aug 7 '15 at 16:32
  • $\begingroup$ (Strongly) related question: Counting non-decreasing sequences with a single long-streak $\endgroup$ – J.-E. Pin Aug 7 '15 at 16:41
  • $\begingroup$ It seems like you are insisting, through your recursion, that you get maximum length repetitive strings of specified maximum length for all possible maximum lengths, whereas the question seems to indicate that only the global maximum length repetitive string needs to occur once and only once (lower length repetitive strings can happen not at all, or more than once, for each length). $\endgroup$ – user2566092 Aug 7 '15 at 16:45
0
$\begingroup$

Here's a way to get an explicit (in terms of summations) solution provided for starters you know or can find a variant of "stars and bars" construction, which gives the number of non-negative integer assignments to $m$ variables that add up to $n$. The variant would be restricting the maximum value of each of the integers to be $l - 1$.

Clearly, since your sequence is non-decreasing, a given valid sequence (without the longest length repeated value constraint) is equivalent to choosing $m$ non-negative integers that add up to $n$. If you can somehow get the constraint that no integer is greater than $l - 1$, where $l$ is the length of the unique streak of maximal length, then you can first choose maximum streak length $l$ and the starting position of the streak of length $l$ and the value for that streak, and then all you need to do is, for left and right of the maximal streak, count how many ways you can get a certain number of non-negative integers to add up to a particular number, such that no integer is greater than $l - 1$. This would mean that your formula, instead of being recursive, would be a triple summation over starting position of longest streak between $1$ and the total length $n$, and the length $l$ of the longest streak, and the value $d$ that is repeated in the longest streak. Clearly for different $d,l$ and starting position of the longest streak, these cases are disjoint so there is no over-counting or anything.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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