A combinatory problem
 

Let M be the maximal ways that (Q1 Q2 Q3 … Qn)^m can be split into different non-square sub-products. For example,

for n = m = 3, we have {Q1,Q2,Q3,Q12,Q13,Q23}.

For n = m = 4, we have {Q1,Q2,Q3,Q4,Q12,Q13,Q14,Q23,Q24,Q34}.

Note that:
1) The total # of Qi appearances over the sub-products cannot exceed m.
2) Qi^2 & (QiQj^2)^4 are not allowed (i.e. these are square sub-products ).
3) QiQj = QjQi (i.e. these are treated exactly the same so it gets only one count) .
4) It is easy to show that if n = m then M = n(n+1)/2 .

The problem is what are the reasonable upper bounds for the value of M when n < m ? I don’t know the answer yet.

Regards

Joseph

You need to do a much better job explaining whatever question you're trying to ask. I think I've managed to figure out that by Q12, you really mean Q1Q2. I still have no clue what you mean when you say "non-square subproduct" (saying Qi^2 & (QiQj^2)^4 are not allowed seems to indicate (QiQj^2)^2 would be allowed, and under any reasonable convention that should be a square subproduct). It's also not entirely clear what M is, and in what sense you want it to be maximal. I think your question would be much clearer if you phrased it in terms of having a collection of mn labeled balls, where the labels run from 1-n and each label appears on m balls.

Kevin,

Two examples should look like

for n = m = 3, we have {Q1,Q2,Q3,Q1Q2,Q1Q3,Q2Q3} and M = 3 * 4 / 2.

For n = m = 4, we have {Q1,Q2,Q3,Q4,Q1Q2,Q1Q3,Q1Q4,Q2Q3,Q2Q4,Q3Q4} ant M = 4 * 5 / 2.

No square sub-products allowed means that any sub-product (or a factor) of
(Q1 Q2 Q3 … Qn)^m cannot be a square. It is easy to see that if no restrictions for sub-products at all, we would have M = n *m (i.e. Qi repeated m times, where 1 <= < i <= n). Thank your for your comment.


Joseph

Joseph,

What does m have to do with the problem, if anything? You are not allowing square-factors, so the power of any factor in the subproduct is at most 1. Also, why do you not allow Q1Q2Q3 in the first example?

Are you just asking how to many pairs you can form?

[QUOTE=Zeta-Flux;172448]so the power of any factor in the subproduct is at most 1.[/QUOTE]

I'm not sure about this. He said "non-square" not "square-free".

The question still doesn't make sense. In your first example, (Q1Q3)*(Q2Q3)*(Q1Q3)=(Q1Q2Q3)^2 is a square subproduct.

[QUOTE=Kevin;172461]The question still doesn't make sense. In your first example, (Q1Q3)*(Q2Q3)*(Q1Q3)=(Q1Q2Q3)^2 is a square subproduct.[/QUOTE]

If you multiply all the subproducts in that set {Q1,Q2,Q3,Q12,Q13,Q23}, you get (Q1Q2Q3)^3. i.e, that set is one way of decomposing (Q1Q2Q3)^3 into non-square subproducts.

Right, but {Q1,Q1,Q1,Q2,Q2,Q2,Q3,Q3,Q3} (under his notation) also works, which he said doesn't satisfy the restriction he's trying to describe. So it's apparently not enough for the individual groupings to be not squares, the restriction has to do with a relation between the groupings.

It would be helpful if the OP described exactly what they mean by "sub-product" (or posed the question in a less obtuse setting, like grouping numbered balls...).

Let me restate our problem as follows:

Let S be the maximal collection of distinct non-square factors of

(Q1 Q2 Q3 … Qn)^m.

Note: S is a maximal collection iff M = #{S} is maximal . For example,

for n = m = 3, we have S ={Q1,Q2,Q3,Q1Q2,Q1Q3,Q2Q3} and M = #{S} = 6.

For n = m = 4, we have S = {Q1,Q2,Q3,Q4,Q1Q2,Q1Q3,Q1Q4,Q2Q3,Q2Q4,
Q3Q4} and M = #{S} = 10.

Moreover, for the case n = m, we have

maximal S = {Q1,Q2,Q3,…Qm,
Q1Q2,Q1Q3, …Q1Qm,
Q2Q3,Q2Q4, … Q2Qm}
Q3Q4,Q3Q5,… Q3Qm}
……………………….
Q(n-1)QnQm},

where all Qi ’s appearances are exactly equal to m.
It is not difficult to observe that in order to make M maximal, the structure of any member of S must be as simple as possible. What is the maximal S looks like when n < m ?

Note that: for the case n = m = 3, if S contains (Q1Q2Q3)^3 we would have S = {(Q1Q2Q3)^3 } and M = 1.

{Q1,Q1,Q1,Q2,Q2,Q2,Q3,Q3,Q3} is not allowed because of Q1 repeated 3 times.


Joseph

Let me re-formulate the problem as I understand it:

Given positive integers m,n, represent n-component vector (m,m,...,m) as the sum of distinct n-component vectors of non-negative integers, such that the number of summands is maximum and there is no summand with all components even.

Example for n = m = 3:
(3,3,3) = (1,0,0) + (0,1,0) + (0,0,1) + (1,1,0) + (1,0,1) + (0,1,1)
is a required sum with 6 summands.

Is that a correct understanding?

[QUOTE=jchein1;172415]4) It is easy to show that if n = m then M = n(n+1)/2 .[/quote]
This can be generalized as follows:
if [tex]m = {n-1\choose 0} + {n-1\choose 1} + \dots + {n-1\choose k-1}[/tex] for some k,
then [tex]M = {n\choose 1} + {n\choose 2} + \dots + {n\choose k}.[/tex]
A particular case m = n corresponds to k = 2.