Mixing
![Find representatives for cosets. [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Pick pairs of sequences with certain properties
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Assume $qinmathbbN=1,2,dots$ to be the size of some field $F$ and consider all sequences $mathbfa$ of length $k-1$ with elements generated from $F=0,1,dots q-1$. There are $q^k-1$ of them, say $mathbfa_1, mathbfa_2, dots, mathbfa_q^k-1$
Now take each of these sequences and attach the sum of its digits modulo $q$ to the end of the sequence to get the $mathbfb$-sequences of the form
$$
mathbfb_ij=
left{
beginarrayll
mathbfa_ij, & textif jin1,dots,k-1 \
sumlimits_m=1^k-1a_im (mathrmmod q), & textif j=k\
endarray
right.
$$
for all $iin1,dots,q^k-1$. In the above definition, I have assumed that $mathbfa_ij$ denotes the $j$-th element of the sequence $mathbfa_i$ and that the indexing starts from 1.
To demonstrate this, let $q=2$, $k=3$. Then the sequences would be
begineqnarray*
mathbfb_1&=&000\
mathbfb_2&=&011\
mathbfb_3&=&101\
mathbfb_4&=&110
endeqnarray*
My problem is the following: Let $winmathbbN$ with $2leq wleq k$. How many ordered pairs ($mathbfb_i,mathbfb_j$) for $ineq j$ of $b$-sequences differ at exactly $w$ positions and coincide at the remaining $k-w$ positions? Denote this quantity by $N_w$
By saying ordered pairs I mean that if ($mathbfb_i,mathbfb_j$) is a valid pair for a specific value of $w$ then ($mathbfb_j,mathbfb_i$) is also a valid pair for that $w$ and should be counted.
For the above example and for $w=2$ the idea is to take the sequences $mathbfb_1$, $mathbfb_2$, $mathbfb_3$ and $mathbfb_4$ one at a time and see which of the remaining sequences differ by the current sequence at exactly $w=2$ positions. In this case, all of the pairs ($mathbfb_1,mathbfb_2$), ($mathbfb_1,mathbfb_3$), ($mathbfb_1,mathbfb_4$), ($mathbfb_2,mathbfb_1$), ($mathbfb_2,mathbfb_3$), ($mathbfb_2,mathbfb_4$), ($mathbfb_3,mathbfb_1$), ($mathbfb_3,mathbfb_2$), ($mathbfb_3,mathbfb_4$), ($mathbfb_4,mathbfb_1$), ($mathbfb_4,mathbfb_2$), ($mathbfb_4,mathbfb_3$) satisfy the condition for $w=2$. So the answer is $N_w=N_2=12$ pairs.
It seems that the general formula for $w=2$ is
$$N_2=kchoose 2q^k-1(q-1)$$
My thought was simple: first fix two positions $m,n$ for the simple case of $mneq k$ and $nneq k$, and take a sequence $mathbfb_i$. Then find all $mathbfb_j$'s that differ from $mathbfb_i$ at these positions only. Since $mathbfb_i$ is fixed you have $q-1$ options for $m$-th position but for the $n$-th position you have only one value that would give the same sum of digits modulo $q$. Taking all possible $m,n$ gives $kchoose 2$ options and then taking each sequence gives $q^k-1$ options.
For $w=3$ I think that the answer is
$$N_3=kchoose 3q^k-1(q-1)(q-2)$$
but I cannot prove it. However
$$N_4=kchoose 4q^k-1(q-1)(q-2)(q-3)$$
seems to be wrong and I cannot generalize the idea.
abstract-algebra sequences-and-series finite-fields coding-theory
asked Aug 2 at 13:31
mgus
622616
add a comment |Â
up vote
2
down vote
favorite
Assume $qinmathbbN=1,2,dots$ to be the size of some field $F$ and consider all sequences $mathbfa$ of length $k-1$ with elements generated from $F=0,1,dots q-1$. There are $q^k-1$ of them, say $mathbfa_1, mathbfa_2, dots, mathbfa_q^k-1$
Now take each of these sequences and attach the sum of its digits modulo $q$ to the end of the sequence to get the $mathbfb$-sequences of the form
$$
mathbfb_ij=
left{
beginarrayll
mathbfa_ij, & textif jin1,dots,k-1 \
sumlimits_m=1^k-1a_im (mathrmmod q), & textif j=k\
endarray
right.
$$
for all $iin1,dots,q^k-1$. In the above definition, I have assumed that $mathbfa_ij$ denotes the $j$-th element of the sequence $mathbfa_i$ and that the indexing starts from 1.
To demonstrate this, let $q=2$, $k=3$. Then the sequences would be
begineqnarray*
mathbfb_1&=&000\
mathbfb_2&=&011\
mathbfb_3&=&101\
mathbfb_4&=&110
endeqnarray*
My problem is the following: Let $winmathbbN$ with $2leq wleq k$. How many ordered pairs ($mathbfb_i,mathbfb_j$) for $ineq j$ of $b$-sequences differ at exactly $w$ positions and coincide at the remaining $k-w$ positions? Denote this quantity by $N_w$
By saying ordered pairs I mean that if ($mathbfb_i,mathbfb_j$) is a valid pair for a specific value of $w$ then ($mathbfb_j,mathbfb_i$) is also a valid pair for that $w$ and should be counted.
For the above example and for $w=2$ the idea is to take the sequences $mathbfb_1$, $mathbfb_2$, $mathbfb_3$ and $mathbfb_4$ one at a time and see which of the remaining sequences differ by the current sequence at exactly $w=2$ positions. In this case, all of the pairs ($mathbfb_1,mathbfb_2$), ($mathbfb_1,mathbfb_3$), ($mathbfb_1,mathbfb_4$), ($mathbfb_2,mathbfb_1$), ($mathbfb_2,mathbfb_3$), ($mathbfb_2,mathbfb_4$), ($mathbfb_3,mathbfb_1$), ($mathbfb_3,mathbfb_2$), ($mathbfb_3,mathbfb_4$), ($mathbfb_4,mathbfb_1$), ($mathbfb_4,mathbfb_2$), ($mathbfb_4,mathbfb_3$) satisfy the condition for $w=2$. So the answer is $N_w=N_2=12$ pairs.
It seems that the general formula for $w=2$ is
$$N_2=kchoose 2q^k-1(q-1)$$
My thought was simple: first fix two positions $m,n$ for the simple case of $mneq k$ and $nneq k$, and take a sequence $mathbfb_i$. Then find all $mathbfb_j$'s that differ from $mathbfb_i$ at these positions only. Since $mathbfb_i$ is fixed you have $q-1$ options for $m$-th position but for the $n$-th position you have only one value that would give the same sum of digits modulo $q$. Taking all possible $m,n$ gives $kchoose 2$ options and then taking each sequence gives $q^k-1$ options.
For $w=3$ I think that the answer is
$$N_3=kchoose 3q^k-1(q-1)(q-2)$$
but I cannot prove it. However
$$N_4=kchoose 4q^k-1(q-1)(q-2)(q-3)$$
seems to be wrong and I cannot generalize the idea.
abstract-algebra sequences-and-series finite-fields coding-theory
asked Aug 2 at 13:31
mgus
622616
Just that you know: $0,1,ldots,q-1$ does not form a field (assuming arithmetic modulo $q$) unless $q$ is a prime number. Mind you, this probably won't have an impact on your question, because it seems to be about combinatorics mostly.
– Jyrki Lahtonen
Aug 4 at 7:52
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Assume $qinmathbbN=1,2,dots$ to be the size of some field $F$ and consider all sequences $mathbfa$ of length $k-1$ with elements generated from $F=0,1,dots q-1$. There are $q^k-1$ of them, say $mathbfa_1, mathbfa_2, dots, mathbfa_q^k-1$
Now take each of these sequences and attach the sum of its digits modulo $q$ to the end of the sequence to get the $mathbfb$-sequences of the form
$$
mathbfb_ij=
left{
beginarrayll
mathbfa_ij, & textif jin1,dots,k-1 \
sumlimits_m=1^k-1a_im (mathrmmod q), & textif j=k\
endarray
right.
$$
for all $iin1,dots,q^k-1$. In the above definition, I have assumed that $mathbfa_ij$ denotes the $j$-th element of the sequence $mathbfa_i$ and that the indexing starts from 1.
To demonstrate this, let $q=2$, $k=3$. Then the sequences would be
begineqnarray*
mathbfb_1&=&000\
mathbfb_2&=&011\
mathbfb_3&=&101\
mathbfb_4&=&110
endeqnarray*
My problem is the following: Let $winmathbbN$ with $2leq wleq k$. How many ordered pairs ($mathbfb_i,mathbfb_j$) for $ineq j$ of $b$-sequences differ at exactly $w$ positions and coincide at the remaining $k-w$ positions? Denote this quantity by $N_w$
By saying ordered pairs I mean that if ($mathbfb_i,mathbfb_j$) is a valid pair for a specific value of $w$ then ($mathbfb_j,mathbfb_i$) is also a valid pair for that $w$ and should be counted.
For the above example and for $w=2$ the idea is to take the sequences $mathbfb_1$, $mathbfb_2$, $mathbfb_3$ and $mathbfb_4$ one at a time and see which of the remaining sequences differ by the current sequence at exactly $w=2$ positions. In this case, all of the pairs ($mathbfb_1,mathbfb_2$), ($mathbfb_1,mathbfb_3$), ($mathbfb_1,mathbfb_4$), ($mathbfb_2,mathbfb_1$), ($mathbfb_2,mathbfb_3$), ($mathbfb_2,mathbfb_4$), ($mathbfb_3,mathbfb_1$), ($mathbfb_3,mathbfb_2$), ($mathbfb_3,mathbfb_4$), ($mathbfb_4,mathbfb_1$), ($mathbfb_4,mathbfb_2$), ($mathbfb_4,mathbfb_3$) satisfy the condition for $w=2$. So the answer is $N_w=N_2=12$ pairs.
It seems that the general formula for $w=2$ is
$$N_2=kchoose 2q^k-1(q-1)$$
My thought was simple: first fix two positions $m,n$ for the simple case of $mneq k$ and $nneq k$, and take a sequence $mathbfb_i$. Then find all $mathbfb_j$'s that differ from $mathbfb_i$ at these positions only. Since $mathbfb_i$ is fixed you have $q-1$ options for $m$-th position but for the $n$-th position you have only one value that would give the same sum of digits modulo $q$. Taking all possible $m,n$ gives $kchoose 2$ options and then taking each sequence gives $q^k-1$ options.
For $w=3$ I think that the answer is
$$N_3=kchoose 3q^k-1(q-1)(q-2)$$
but I cannot prove it. However
$$N_4=kchoose 4q^k-1(q-1)(q-2)(q-3)$$
seems to be wrong and I cannot generalize the idea.
abstract-algebra sequences-and-series finite-fields coding-theory
asked Aug 2 at 13:31
mgus
622616
Assume $qinmathbbN=1,2,dots$ to be the size of some field $F$ and consider all sequences $mathbfa$ of length $k-1$ with elements generated from $F=0,1,dots q-1$. There are $q^k-1$ of them, say $mathbfa_1, mathbfa_2, dots, mathbfa_q^k-1$
Now take each of these sequences and attach the sum of its digits modulo $q$ to the end of the sequence to get the $mathbfb$-sequences of the form
$$
mathbfb_ij=
left{
beginarrayll
mathbfa_ij, & textif jin1,dots,k-1 \
sumlimits_m=1^k-1a_im (mathrmmod q), & textif j=k\
endarray
right.
$$
for all $iin1,dots,q^k-1$. In the above definition, I have assumed that $mathbfa_ij$ denotes the $j$-th element of the sequence $mathbfa_i$ and that the indexing starts from 1.
To demonstrate this, let $q=2$, $k=3$. Then the sequences would be
begineqnarray*
mathbfb_1&=&000\
mathbfb_2&=&011\
mathbfb_3&=&101\
mathbfb_4&=&110
endeqnarray*
My problem is the following: Let $winmathbbN$ with $2leq wleq k$. How many ordered pairs ($mathbfb_i,mathbfb_j$) for $ineq j$ of $b$-sequences differ at exactly $w$ positions and coincide at the remaining $k-w$ positions? Denote this quantity by $N_w$
By saying ordered pairs I mean that if ($mathbfb_i,mathbfb_j$) is a valid pair for a specific value of $w$ then ($mathbfb_j,mathbfb_i$) is also a valid pair for that $w$ and should be counted.
For the above example and for $w=2$ the idea is to take the sequences $mathbfb_1$, $mathbfb_2$, $mathbfb_3$ and $mathbfb_4$ one at a time and see which of the remaining sequences differ by the current sequence at exactly $w=2$ positions. In this case, all of the pairs ($mathbfb_1,mathbfb_2$), ($mathbfb_1,mathbfb_3$), ($mathbfb_1,mathbfb_4$), ($mathbfb_2,mathbfb_1$), ($mathbfb_2,mathbfb_3$), ($mathbfb_2,mathbfb_4$), ($mathbfb_3,mathbfb_1$), ($mathbfb_3,mathbfb_2$), ($mathbfb_3,mathbfb_4$), ($mathbfb_4,mathbfb_1$), ($mathbfb_4,mathbfb_2$), ($mathbfb_4,mathbfb_3$) satisfy the condition for $w=2$. So the answer is $N_w=N_2=12$ pairs.
It seems that the general formula for $w=2$ is
$$N_2=kchoose 2q^k-1(q-1)$$
My thought was simple: first fix two positions $m,n$ for the simple case of $mneq k$ and $nneq k$, and take a sequence $mathbfb_i$. Then find all $mathbfb_j$'s that differ from $mathbfb_i$ at these positions only. Since $mathbfb_i$ is fixed you have $q-1$ options for $m$-th position but for the $n$-th position you have only one value that would give the same sum of digits modulo $q$. Taking all possible $m,n$ gives $kchoose 2$ options and then taking each sequence gives $q^k-1$ options.
For $w=3$ I think that the answer is
$$N_3=kchoose 3q^k-1(q-1)(q-2)$$
but I cannot prove it. However
$$N_4=kchoose 4q^k-1(q-1)(q-2)(q-3)$$
seems to be wrong and I cannot generalize the idea.
abstract-algebra sequences-and-series finite-fields coding-theory
asked Aug 2 at 13:31
mgus
622616
asked Aug 2 at 13:31
mgus
622616
asked Aug 2 at 13:31
mgus
622616
asked Aug 2 at 13:31
mgus
622616
622616
Just that you know: $0,1,ldots,q-1$ does not form a field (assuming arithmetic modulo $q$) unless $q$ is a prime number. Mind you, this probably won't have an impact on your question, because it seems to be about combinatorics mostly.
– Jyrki Lahtonen
Aug 4 at 7:52
add a comment |Â
Just that you know: $0,1,ldots,q-1$ does not form a field (assuming arithmetic modulo $q$) unless $q$ is a prime number. Mind you, this probably won't have an impact on your question, because it seems to be about combinatorics mostly.
– Jyrki Lahtonen
Aug 4 at 7:52
Just that you know: $0,1,ldots,q-1$ does not form a field (assuming arithmetic modulo $q$) unless $q$ is a prime number. Mind you, this probably won't have an impact on your question, because it seems to be about combinatorics mostly.
– Jyrki Lahtonen
Aug 4 at 7:52
Just that you know: $0,1,ldots,q-1$ does not form a field (assuming arithmetic modulo $q$) unless $q$ is a prime number. Mind you, this probably won't have an impact on your question, because it seems to be about combinatorics mostly.
– Jyrki Lahtonen
Aug 4 at 7:52
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
Let $a_1,a_2,ldots,a_n$ be sequences of length $nge 1$ with $a_i in F, i=1,2,ldots,n$. Let $S(n)$ be the number of such sequences with all $a_i neq 0$. Let $Z(n)$ be the number of such sequences with all $a_i neq 0$ and $sum_i=1^na_i = 0 pmod q$.
Obviously, we have $S(n)=(q-1)^n$. It's also easy to see that $Z(1)=0$.
We have the following recurrence relation:
For $n ge 1$:
$$Z(n+1) = S(n) - Z(n)$$
Proof: Any sequence $a_1,a_2,ldots,a_n+1, a_i neq 0, i=1,2,ldots,n+1, sum_i=1^n+1a_i = 0 pmod q$ has $sum_i=1^na_i neq 0 pmod q$, as otherwise we'd have $a_n+1 = 0 pmod q$ and thus $a_n+1 = 0$.
In the other direction, any sequence $a_1,a_2,ldots,a_n, a_i neq 0, i=1,2,ldots,n, sum_i=1^na_i neq 0 pmod q$ can be extended by exactly one $a_n+1 in F, a_n+1 neq 0$ such that $sum_i=1^n+1a_i = 0 pmod q$; we have $a_n+1=-sum_i=1^na_i pmod q$ (which exists and is unique in $F$), and the condition $sum_i=1^na_i neq 0 pmod q$ makes sure that $a_n+1 neq 0$. $blacksquare $.
With mathematical induction, it is now easy to prove that
Lemma 1:
$$Z(n) = (q-1)frac(q-1)^n-1-(-1)^n-1q$$
This gives $Z(2)=q-1, Z(3)=(q-1)(q-2),$ but $Z(4)=(q-1)(q^2-3q+3)$, which threw off the OP.
But what does this have to do with the original problem?
First, it's easy to see that $Z(n)$ also counts the number of sequences with $a_i neq f_i$ and $sum_i=1^na_i=sum_i=1^nf_i pmod q$, where $f_i in F, i=1,2,ldots,n$ is a fixed sequence of numbers from $F$. Choosing $a'_i=a_i-f_i pmod q, i=1,2,ldots,n$ transforms this problem into the former one.
Second, for the original problem, select any $b_i$: This allows $q^k-1$ choices.
The $w$ differences between $b_i$ and any potential $b_j$ can occur in 2 ways:
- The $w$ differences are all before index $k$, and
- There are $w-1$ differences before index $k$, and one difference in index $k$.
For possibility 1, we have to choose the $w$ indices among the $k-1$ existing, this leads to $k-1 choose w$ index choices. In each of those $w$ indices ($s_1, s_2, ldots, s_w$), the sequence $b_j$ must differ from $b_i$ ($b_is_r neq b_js_r, r=1,2,ldots,w$) , but the sum of the values must be equal ($sum_r=1^w b_is_r = sum_r=1^w b_js_r pmod q$), because at index $k$ we have equality between $b_i$ and $b_j$, which means $sum_r=1^k-1 b_ir = sum_r=1^k-1 b_jr pmod q$. But since $b_i$ and $b_j$ only differ in the index set $s_r, r=1,2,ldots w$, the latter is the same as the former.
That s exactly the problem we tackled above, that means once the index set is chosen, we have Z(w) possibilities to choose the elements of $b_j$ that are supposed to be different from $b_i$. Alltogether this means
$$k-1 choose w Z(w) $$
different $b_j$ for possibility 1.
For possibility 2, we have to choose the $w-1$ indices for difference between $b_i$ and $b_j$, so $k-1 choose w-1$ possibilites to arrive at an index set $s_r, r=1,2,ldots,w-1$. But now, since we want a difference also in the 'calculated' index $k$, we want the sums $sum_r=1^w-1 b_is_r$ and $sum_r=1^w-1 b_js_r $ to be different $pmod q$.The number of sequences to be chosen thus is $S(w-1) - Z(w-1)$: All such sequences minus the number of sequences where the sums are the same. We know from the proof above that $S(w-1) - Z(w-1) = Z(w)$. Taken together with the number choices for the index set, we see that the number of sequences $b_j$ under possibility 2 is
$$k-1 choose w-1 Z(w)$$
Adding the values for possibiliites 1 and 2, we get that for each $b_i$ there are exactly
$$k-1 choose w Z(w) + k-1 choose w-1 Z(w) = (k-1 choose w + k-1 choose w-1) Z(w) = k choose w Z(w)$$
$b_j$ that differ from $b_i$ in exactly $w$ indices.
Recalling that there are $q^k-1$ possible $b_i$, this makes the count of ordered pairs $(b_i,b_j)$ with $b_i,b_j$ differing in exactly $w$ indices
$$N_w = k choose wq^k-1 Z(w) = k choose wq^k-1 (q-1)frac(q-1)^w-1-(-1)^w-1q $$
As I wrote above, the special form of $Z(w)$ for small $w$ might one lead to a different assumption on the general form of $Z(w)$
answered Aug 3 at 3:09
Ingix
2,085125
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Let $a_1,a_2,ldots,a_n$ be sequences of length $nge 1$ with $a_i in F, i=1,2,ldots,n$. Let $S(n)$ be the number of such sequences with all $a_i neq 0$. Let $Z(n)$ be the number of such sequences with all $a_i neq 0$ and $sum_i=1^na_i = 0 pmod q$.
Obviously, we have $S(n)=(q-1)^n$. It's also easy to see that $Z(1)=0$.
We have the following recurrence relation:
For $n ge 1$:
$$Z(n+1) = S(n) - Z(n)$$
Proof: Any sequence $a_1,a_2,ldots,a_n+1, a_i neq 0, i=1,2,ldots,n+1, sum_i=1^n+1a_i = 0 pmod q$ has $sum_i=1^na_i neq 0 pmod q$, as otherwise we'd have $a_n+1 = 0 pmod q$ and thus $a_n+1 = 0$.
In the other direction, any sequence $a_1,a_2,ldots,a_n, a_i neq 0, i=1,2,ldots,n, sum_i=1^na_i neq 0 pmod q$ can be extended by exactly one $a_n+1 in F, a_n+1 neq 0$ such that $sum_i=1^n+1a_i = 0 pmod q$; we have $a_n+1=-sum_i=1^na_i pmod q$ (which exists and is unique in $F$), and the condition $sum_i=1^na_i neq 0 pmod q$ makes sure that $a_n+1 neq 0$. $blacksquare $.
With mathematical induction, it is now easy to prove that
Lemma 1:
$$Z(n) = (q-1)frac(q-1)^n-1-(-1)^n-1q$$
This gives $Z(2)=q-1, Z(3)=(q-1)(q-2),$ but $Z(4)=(q-1)(q^2-3q+3)$, which threw off the OP.
But what does this have to do with the original problem?
First, it's easy to see that $Z(n)$ also counts the number of sequences with $a_i neq f_i$ and $sum_i=1^na_i=sum_i=1^nf_i pmod q$, where $f_i in F, i=1,2,ldots,n$ is a fixed sequence of numbers from $F$. Choosing $a'_i=a_i-f_i pmod q, i=1,2,ldots,n$ transforms this problem into the former one.
Second, for the original problem, select any $b_i$: This allows $q^k-1$ choices.
The $w$ differences between $b_i$ and any potential $b_j$ can occur in 2 ways:
- The $w$ differences are all before index $k$, and
- There are $w-1$ differences before index $k$, and one difference in index $k$.
For possibility 1, we have to choose the $w$ indices among the $k-1$ existing, this leads to $k-1 choose w$ index choices. In each of those $w$ indices ($s_1, s_2, ldots, s_w$), the sequence $b_j$ must differ from $b_i$ ($b_is_r neq b_js_r, r=1,2,ldots,w$) , but the sum of the values must be equal ($sum_r=1^w b_is_r = sum_r=1^w b_js_r pmod q$), because at index $k$ we have equality between $b_i$ and $b_j$, which means $sum_r=1^k-1 b_ir = sum_r=1^k-1 b_jr pmod q$. But since $b_i$ and $b_j$ only differ in the index set $s_r, r=1,2,ldots w$, the latter is the same as the former.
That s exactly the problem we tackled above, that means once the index set is chosen, we have Z(w) possibilities to choose the elements of $b_j$ that are supposed to be different from $b_i$. Alltogether this means
$$k-1 choose w Z(w) $$
different $b_j$ for possibility 1.
For possibility 2, we have to choose the $w-1$ indices for difference between $b_i$ and $b_j$, so $k-1 choose w-1$ possibilites to arrive at an index set $s_r, r=1,2,ldots,w-1$. But now, since we want a difference also in the 'calculated' index $k$, we want the sums $sum_r=1^w-1 b_is_r$ and $sum_r=1^w-1 b_js_r $ to be different $pmod q$.The number of sequences to be chosen thus is $S(w-1) - Z(w-1)$: All such sequences minus the number of sequences where the sums are the same. We know from the proof above that $S(w-1) - Z(w-1) = Z(w)$. Taken together with the number choices for the index set, we see that the number of sequences $b_j$ under possibility 2 is
$$k-1 choose w-1 Z(w)$$
Adding the values for possibiliites 1 and 2, we get that for each $b_i$ there are exactly
$$k-1 choose w Z(w) + k-1 choose w-1 Z(w) = (k-1 choose w + k-1 choose w-1) Z(w) = k choose w Z(w)$$
$b_j$ that differ from $b_i$ in exactly $w$ indices.
Recalling that there are $q^k-1$ possible $b_i$, this makes the count of ordered pairs $(b_i,b_j)$ with $b_i,b_j$ differing in exactly $w$ indices
$$N_w = k choose wq^k-1 Z(w) = k choose wq^k-1 (q-1)frac(q-1)^w-1-(-1)^w-1q $$
As I wrote above, the special form of $Z(w)$ for small $w$ might one lead to a different assumption on the general form of $Z(w)$
answered Aug 3 at 3:09
Ingix
2,085125
add a comment |Â
up vote
0
down vote
Let $a_1,a_2,ldots,a_n$ be sequences of length $nge 1$ with $a_i in F, i=1,2,ldots,n$. Let $S(n)$ be the number of such sequences with all $a_i neq 0$. Let $Z(n)$ be the number of such sequences with all $a_i neq 0$ and $sum_i=1^na_i = 0 pmod q$.
Obviously, we have $S(n)=(q-1)^n$. It's also easy to see that $Z(1)=0$.
We have the following recurrence relation:
For $n ge 1$:
$$Z(n+1) = S(n) - Z(n)$$
Proof: Any sequence $a_1,a_2,ldots,a_n+1, a_i neq 0, i=1,2,ldots,n+1, sum_i=1^n+1a_i = 0 pmod q$ has $sum_i=1^na_i neq 0 pmod q$, as otherwise we'd have $a_n+1 = 0 pmod q$ and thus $a_n+1 = 0$.
In the other direction, any sequence $a_1,a_2,ldots,a_n, a_i neq 0, i=1,2,ldots,n, sum_i=1^na_i neq 0 pmod q$ can be extended by exactly one $a_n+1 in F, a_n+1 neq 0$ such that $sum_i=1^n+1a_i = 0 pmod q$; we have $a_n+1=-sum_i=1^na_i pmod q$ (which exists and is unique in $F$), and the condition $sum_i=1^na_i neq 0 pmod q$ makes sure that $a_n+1 neq 0$. $blacksquare $.
With mathematical induction, it is now easy to prove that
Lemma 1:
$$Z(n) = (q-1)frac(q-1)^n-1-(-1)^n-1q$$
This gives $Z(2)=q-1, Z(3)=(q-1)(q-2),$ but $Z(4)=(q-1)(q^2-3q+3)$, which threw off the OP.
But what does this have to do with the original problem?
First, it's easy to see that $Z(n)$ also counts the number of sequences with $a_i neq f_i$ and $sum_i=1^na_i=sum_i=1^nf_i pmod q$, where $f_i in F, i=1,2,ldots,n$ is a fixed sequence of numbers from $F$. Choosing $a'_i=a_i-f_i pmod q, i=1,2,ldots,n$ transforms this problem into the former one.
Second, for the original problem, select any $b_i$: This allows $q^k-1$ choices.
The $w$ differences between $b_i$ and any potential $b_j$ can occur in 2 ways:
- The $w$ differences are all before index $k$, and
- There are $w-1$ differences before index $k$, and one difference in index $k$.
For possibility 1, we have to choose the $w$ indices among the $k-1$ existing, this leads to $k-1 choose w$ index choices. In each of those $w$ indices ($s_1, s_2, ldots, s_w$), the sequence $b_j$ must differ from $b_i$ ($b_is_r neq b_js_r, r=1,2,ldots,w$) , but the sum of the values must be equal ($sum_r=1^w b_is_r = sum_r=1^w b_js_r pmod q$), because at index $k$ we have equality between $b_i$ and $b_j$, which means $sum_r=1^k-1 b_ir = sum_r=1^k-1 b_jr pmod q$. But since $b_i$ and $b_j$ only differ in the index set $s_r, r=1,2,ldots w$, the latter is the same as the former.
That s exactly the problem we tackled above, that means once the index set is chosen, we have Z(w) possibilities to choose the elements of $b_j$ that are supposed to be different from $b_i$. Alltogether this means
$$k-1 choose w Z(w) $$
different $b_j$ for possibility 1.
For possibility 2, we have to choose the $w-1$ indices for difference between $b_i$ and $b_j$, so $k-1 choose w-1$ possibilites to arrive at an index set $s_r, r=1,2,ldots,w-1$. But now, since we want a difference also in the 'calculated' index $k$, we want the sums $sum_r=1^w-1 b_is_r$ and $sum_r=1^w-1 b_js_r $ to be different $pmod q$.The number of sequences to be chosen thus is $S(w-1) - Z(w-1)$: All such sequences minus the number of sequences where the sums are the same. We know from the proof above that $S(w-1) - Z(w-1) = Z(w)$. Taken together with the number choices for the index set, we see that the number of sequences $b_j$ under possibility 2 is
$$k-1 choose w-1 Z(w)$$
Adding the values for possibiliites 1 and 2, we get that for each $b_i$ there are exactly
$$k-1 choose w Z(w) + k-1 choose w-1 Z(w) = (k-1 choose w + k-1 choose w-1) Z(w) = k choose w Z(w)$$
$b_j$ that differ from $b_i$ in exactly $w$ indices.
Recalling that there are $q^k-1$ possible $b_i$, this makes the count of ordered pairs $(b_i,b_j)$ with $b_i,b_j$ differing in exactly $w$ indices
$$N_w = k choose wq^k-1 Z(w) = k choose wq^k-1 (q-1)frac(q-1)^w-1-(-1)^w-1q $$
As I wrote above, the special form of $Z(w)$ for small $w$ might one lead to a different assumption on the general form of $Z(w)$
answered Aug 3 at 3:09
Ingix
2,085125
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Let $a_1,a_2,ldots,a_n$ be sequences of length $nge 1$ with $a_i in F, i=1,2,ldots,n$. Let $S(n)$ be the number of such sequences with all $a_i neq 0$. Let $Z(n)$ be the number of such sequences with all $a_i neq 0$ and $sum_i=1^na_i = 0 pmod q$.
Obviously, we have $S(n)=(q-1)^n$. It's also easy to see that $Z(1)=0$.
We have the following recurrence relation:
For $n ge 1$:
$$Z(n+1) = S(n) - Z(n)$$
Proof: Any sequence $a_1,a_2,ldots,a_n+1, a_i neq 0, i=1,2,ldots,n+1, sum_i=1^n+1a_i = 0 pmod q$ has $sum_i=1^na_i neq 0 pmod q$, as otherwise we'd have $a_n+1 = 0 pmod q$ and thus $a_n+1 = 0$.
In the other direction, any sequence $a_1,a_2,ldots,a_n, a_i neq 0, i=1,2,ldots,n, sum_i=1^na_i neq 0 pmod q$ can be extended by exactly one $a_n+1 in F, a_n+1 neq 0$ such that $sum_i=1^n+1a_i = 0 pmod q$; we have $a_n+1=-sum_i=1^na_i pmod q$ (which exists and is unique in $F$), and the condition $sum_i=1^na_i neq 0 pmod q$ makes sure that $a_n+1 neq 0$. $blacksquare $.
With mathematical induction, it is now easy to prove that
Lemma 1:
$$Z(n) = (q-1)frac(q-1)^n-1-(-1)^n-1q$$
This gives $Z(2)=q-1, Z(3)=(q-1)(q-2),$ but $Z(4)=(q-1)(q^2-3q+3)$, which threw off the OP.
But what does this have to do with the original problem?
First, it's easy to see that $Z(n)$ also counts the number of sequences with $a_i neq f_i$ and $sum_i=1^na_i=sum_i=1^nf_i pmod q$, where $f_i in F, i=1,2,ldots,n$ is a fixed sequence of numbers from $F$. Choosing $a'_i=a_i-f_i pmod q, i=1,2,ldots,n$ transforms this problem into the former one.
Second, for the original problem, select any $b_i$: This allows $q^k-1$ choices.
The $w$ differences between $b_i$ and any potential $b_j$ can occur in 2 ways:
- The $w$ differences are all before index $k$, and
- There are $w-1$ differences before index $k$, and one difference in index $k$.
For possibility 1, we have to choose the $w$ indices among the $k-1$ existing, this leads to $k-1 choose w$ index choices. In each of those $w$ indices ($s_1, s_2, ldots, s_w$), the sequence $b_j$ must differ from $b_i$ ($b_is_r neq b_js_r, r=1,2,ldots,w$) , but the sum of the values must be equal ($sum_r=1^w b_is_r = sum_r=1^w b_js_r pmod q$), because at index $k$ we have equality between $b_i$ and $b_j$, which means $sum_r=1^k-1 b_ir = sum_r=1^k-1 b_jr pmod q$. But since $b_i$ and $b_j$ only differ in the index set $s_r, r=1,2,ldots w$, the latter is the same as the former.
That s exactly the problem we tackled above, that means once the index set is chosen, we have Z(w) possibilities to choose the elements of $b_j$ that are supposed to be different from $b_i$. Alltogether this means
$$k-1 choose w Z(w) $$
different $b_j$ for possibility 1.
For possibility 2, we have to choose the $w-1$ indices for difference between $b_i$ and $b_j$, so $k-1 choose w-1$ possibilites to arrive at an index set $s_r, r=1,2,ldots,w-1$. But now, since we want a difference also in the 'calculated' index $k$, we want the sums $sum_r=1^w-1 b_is_r$ and $sum_r=1^w-1 b_js_r $ to be different $pmod q$.The number of sequences to be chosen thus is $S(w-1) - Z(w-1)$: All such sequences minus the number of sequences where the sums are the same. We know from the proof above that $S(w-1) - Z(w-1) = Z(w)$. Taken together with the number choices for the index set, we see that the number of sequences $b_j$ under possibility 2 is
$$k-1 choose w-1 Z(w)$$
Adding the values for possibiliites 1 and 2, we get that for each $b_i$ there are exactly
$$k-1 choose w Z(w) + k-1 choose w-1 Z(w) = (k-1 choose w + k-1 choose w-1) Z(w) = k choose w Z(w)$$
$b_j$ that differ from $b_i$ in exactly $w$ indices.
Recalling that there are $q^k-1$ possible $b_i$, this makes the count of ordered pairs $(b_i,b_j)$ with $b_i,b_j$ differing in exactly $w$ indices
$$N_w = k choose wq^k-1 Z(w) = k choose wq^k-1 (q-1)frac(q-1)^w-1-(-1)^w-1q $$
As I wrote above, the special form of $Z(w)$ for small $w$ might one lead to a different assumption on the general form of $Z(w)$
answered Aug 3 at 3:09
Ingix
2,085125
Let $a_1,a_2,ldots,a_n$ be sequences of length $nge 1$ with $a_i in F, i=1,2,ldots,n$. Let $S(n)$ be the number of such sequences with all $a_i neq 0$. Let $Z(n)$ be the number of such sequences with all $a_i neq 0$ and $sum_i=1^na_i = 0 pmod q$.
Obviously, we have $S(n)=(q-1)^n$. It's also easy to see that $Z(1)=0$.
We have the following recurrence relation:
For $n ge 1$:
$$Z(n+1) = S(n) - Z(n)$$
Proof: Any sequence $a_1,a_2,ldots,a_n+1, a_i neq 0, i=1,2,ldots,n+1, sum_i=1^n+1a_i = 0 pmod q$ has $sum_i=1^na_i neq 0 pmod q$, as otherwise we'd have $a_n+1 = 0 pmod q$ and thus $a_n+1 = 0$.
In the other direction, any sequence $a_1,a_2,ldots,a_n, a_i neq 0, i=1,2,ldots,n, sum_i=1^na_i neq 0 pmod q$ can be extended by exactly one $a_n+1 in F, a_n+1 neq 0$ such that $sum_i=1^n+1a_i = 0 pmod q$; we have $a_n+1=-sum_i=1^na_i pmod q$ (which exists and is unique in $F$), and the condition $sum_i=1^na_i neq 0 pmod q$ makes sure that $a_n+1 neq 0$. $blacksquare $.
With mathematical induction, it is now easy to prove that
Lemma 1:
$$Z(n) = (q-1)frac(q-1)^n-1-(-1)^n-1q$$
This gives $Z(2)=q-1, Z(3)=(q-1)(q-2),$ but $Z(4)=(q-1)(q^2-3q+3)$, which threw off the OP.
But what does this have to do with the original problem?
First, it's easy to see that $Z(n)$ also counts the number of sequences with $a_i neq f_i$ and $sum_i=1^na_i=sum_i=1^nf_i pmod q$, where $f_i in F, i=1,2,ldots,n$ is a fixed sequence of numbers from $F$. Choosing $a'_i=a_i-f_i pmod q, i=1,2,ldots,n$ transforms this problem into the former one.
Second, for the original problem, select any $b_i$: This allows $q^k-1$ choices.
The $w$ differences between $b_i$ and any potential $b_j$ can occur in 2 ways:
- The $w$ differences are all before index $k$, and
- There are $w-1$ differences before index $k$, and one difference in index $k$.
For possibility 1, we have to choose the $w$ indices among the $k-1$ existing, this leads to $k-1 choose w$ index choices. In each of those $w$ indices ($s_1, s_2, ldots, s_w$), the sequence $b_j$ must differ from $b_i$ ($b_is_r neq b_js_r, r=1,2,ldots,w$) , but the sum of the values must be equal ($sum_r=1^w b_is_r = sum_r=1^w b_js_r pmod q$), because at index $k$ we have equality between $b_i$ and $b_j$, which means $sum_r=1^k-1 b_ir = sum_r=1^k-1 b_jr pmod q$. But since $b_i$ and $b_j$ only differ in the index set $s_r, r=1,2,ldots w$, the latter is the same as the former.
That s exactly the problem we tackled above, that means once the index set is chosen, we have Z(w) possibilities to choose the elements of $b_j$ that are supposed to be different from $b_i$. Alltogether this means
$$k-1 choose w Z(w) $$
different $b_j$ for possibility 1.
For possibility 2, we have to choose the $w-1$ indices for difference between $b_i$ and $b_j$, so $k-1 choose w-1$ possibilites to arrive at an index set $s_r, r=1,2,ldots,w-1$. But now, since we want a difference also in the 'calculated' index $k$, we want the sums $sum_r=1^w-1 b_is_r$ and $sum_r=1^w-1 b_js_r $ to be different $pmod q$.The number of sequences to be chosen thus is $S(w-1) - Z(w-1)$: All such sequences minus the number of sequences where the sums are the same. We know from the proof above that $S(w-1) - Z(w-1) = Z(w)$. Taken together with the number choices for the index set, we see that the number of sequences $b_j$ under possibility 2 is
$$k-1 choose w-1 Z(w)$$
Adding the values for possibiliites 1 and 2, we get that for each $b_i$ there are exactly
$$k-1 choose w Z(w) + k-1 choose w-1 Z(w) = (k-1 choose w + k-1 choose w-1) Z(w) = k choose w Z(w)$$
$b_j$ that differ from $b_i$ in exactly $w$ indices.
Recalling that there are $q^k-1$ possible $b_i$, this makes the count of ordered pairs $(b_i,b_j)$ with $b_i,b_j$ differing in exactly $w$ indices
$$N_w = k choose wq^k-1 Z(w) = k choose wq^k-1 (q-1)frac(q-1)^w-1-(-1)^w-1q $$
As I wrote above, the special form of $Z(w)$ for small $w$ might one lead to a different assumption on the general form of $Z(w)$
answered Aug 3 at 3:09
Ingix
2,085125
answered Aug 3 at 3:09
Ingix
2,085125
answered Aug 3 at 3:09
Ingix
2,085125
answered Aug 3 at 3:09
Ingix
2,085125
2,085125
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870062%2fpick-pairs-of-sequences-with-certain-properties%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Just that you know: $0,1,ldots,q-1$ does not form a field (assuming arithmetic modulo $q$) unless $q$ is a prime number. Mind you, this probably won't have an impact on your question, because it seems to be about combinatorics mostly.
– Jyrki Lahtonen
Aug 4 at 7:52