Re: Consecutive Numbers

SirKnight wrote:


"Maury Barbato" <mauriziobarbato@xxxxxxxx> wrote in
message
news:5576058.15533.1244996553955.JavaMail.jakarta@nitr
ogen.mathforum.org...
rossum wrote:

On Sat, 13 Jun 2009 14:02:36 EDT, Maury Barbato
<mauriziobarbato@xxxxxxxx> wrote:

Hello,
let k <= m <= n three positive integers.
Let S(k,m,n) be the number of subsets of
{1,...,n} with the following properties:

(1) S contains m elements

(2) S contains at least a sequence of at least k
consecutive numbers (that is, there exist j such
that j, j + 1, ..., j + k - 1 are in S)

I don't know the answer, except in the trivial
cases k = m or m = n. Do you have some idea?

Thank you for your attention.
My Best Regards,
Maury Barbato
Can you answer the question for S(1, m, n)?
Can you answer the question for S(2, m, n)?
Can you extrapolate from there?

rossum


Obviously, S(1,m,n) = (n choose m), but I don't
know how to find S(2,m,n). Some hint?

Thank you for your attention.
Maury Barbato

S(2,m,n) = C(n, m) - C(n+1-m, m).


That's right! We can simply figure out the numbers
of subsets which contain only sequences of length
1. Let P(m,n) the set of all subsets of {1,...,n}
which contain m elements and P(1,m,n) the set of
all subsets of {1,...,n} which contain only
"sequences" of length 1. The map

s:P(m,n - m + 1) -> P(1, m, n)

defined by (a_1 < a_2 < ... < a_m)

s({a_1, ..., a_m}) = {a_1, a_2 + 1, ..., a_m + m - 1)

is a bijection. So the result.

But off-hand I can't figure out what S(3,m,n) is.



Neither I can!

Thank you very much for your help.
Maury Barbato
.

Relevant Pages

  • Re: Consecutive Numbers
    ... On Sun, 14 Jun 2009 12:22:03 EDT, Maury Barbato ... You have an S with sequences 1 long. ...
    (sci.math)
  • Re: How many bijections are there from A to A?
    ... There is an injection from this into all sequences comprising natural ... there is an injection from permutations over N to R. ... As there is an injection in both directions, it must be a bijection. ...
    (sci.math)
  • Re: Cantor Confusion
    ... >> I can't so you can not show a bijection. ... I give a surjection on all existing paths. ... But the set of all sequences of edges is NOT countable, ... One is not separating individual paths but sets of paths with each set ...
    (sci.math)
  • Re: Infinte strings of digits
    ... > Since the sequences in each equivalence class ... > are a countable set, ... In fact no "reasonably definable" such bijection ...
    (sci.math)
  • Re: Infinte strings of digits
    ... > Since the sequences in each equivalence class ... > are a countable set, ... In fact no "reasonably definable" such bijection ...
    (sci.logic)
Quantcast