[seqfan] Re: A279196: a plausible meaning?

[Neil Sloane]

Max, A363933 looked like you had forgotten about it - it had been in limbo
for 3 weeks.  I think you just forgot to submit it, so I approved it.
Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com



On Wed, Jun 28, 2023 at 1:30 PM Max Alekseyev <maxale at gmail.com> wrote:

> I've started a draft for the new sequence: https://oeis.org/draft/A363933
> Comments and extension are welcome.
>
> Regards,
> Max
>
>
> On Tue, Jun 27, 2023 at 10:48 PM Max Alekseyev <maxale at gmail.com> wrote:
>
>> After a bit more research, it looks like Luc got a correct meaning of the
>> terms in A279196, while its current definition is incorrect.
>> Namely, to match its terms one needs to additionally require that the
>> quotient of division of P(x,y) by (x+y-1) also has nonnegative coefficients.
>> If this requirement is violated, then we have a mismatch already for n =
>> 5, when there exist 14 polynomials (rather than a(5)=13) satisfying the
>> current definition of A279196:
>>
>> x^3*y + x^2*y^2 + x*y^2 + x^2 + y   =   1 + (x+y-1) * (x^2*y + x*y + x +
>> 1)
>> x^2*y^2 + x*y^3 + x^2*y + x^2 + y   =   1 + (x+y-1) * (x*y^2 + x*y + x +
>> 1)
>> x^3 + 2*x^2*y + x*y^2 + y   =   1 + (x+y-1) * (x^2 + x*y + x + 1)
>> x^4 + x^3*y + x^2*y + x*y + y   =   1 + (x+y-1) * (x^3 + x^2 + x + 1)
>> x^3*y + x^2*y^2 + x^3 + x*y + y   =   1 + (x+y-1) * (x^2*y + x^2 + x + 1)
>> x^3*y + x^2*y^2 + x*y^2 + y^2 + x   =   1 + (x+y-1) * (x^2*y + x*y + y +
>> 1)
>> x^2*y^2 + x*y^3 + x^2*y + y^2 + x   =   1 + (x+y-1) * (x*y^2 + x*y + y +
>> 1)
>> x^2*y + 2*x*y^2 + y^3 + x   =   1 + (x+y-1) * (x*y + y^2 + y + 1)
>> x^2*y^2 + x*y^3 + y^3 + x*y + x   =   1 + (x+y-1) * (x*y^2 + y^2 + y + 1)
>> x*y^3 + y^4 + x*y^2 + x*y + x   =   1 + (x+y-1) * (y^3 + y^2 + y + 1)
>> x^2*y + x*y^2 + x^2 + x*y + y^2   =   1 + (x+y-1) * (x*y + x + y + 1)
>> x^3 + x^2*y + 2*x*y + y^2   =   1 + (x+y-1) * (x^2 + x + y + 1)
>> x*y^2 + y^3 + x^2 + 2*x*y   =   1 + (x+y-1) * (y^2 + x + y + 1)
>> x^3 + y^3 + 3*x*y   =   1 + (x+y-1) * (x^2 - x*y + y^2 + x + y + 1)
>>
>> All but the last one have quotients with nonnegative coefficients.
>> Perhaps, it's worth correcting the definition of A279196, and adding a
>> new sequence with the old definition.
>>
>> Regards,
>> Max
>>
>> On Tue, Jun 27, 2023 at 5:23 PM Max Alekseyev <maxale at gmail.com> wrote:
>>
>>> Hi Luc,
>>>
>>> From your translation of languages, it seems to follow that in the
>>> formula
>>> degrade^<n>(P) = P + (x+y-1) * Q_n
>>> the coefficients of Q_n are nonnegative, aren't they?
>>>
>>> If so, let's consider n=5 and the polynomial
>>> x^3 + 3xy + y^3 = 1 + (x + y - 1) * (x^2 + y^2 - xy + x + y + 1)
>>> It satisfies the definition of A279196 but cannot be obtained by
>>> degradation.
>>> Do I miss something?
>>>
>>> Regards,
>>> Max
>>>
>>>
>>> On Tue, Jun 27, 2023 at 3:47 PM Luc Rousseau <luc_rousseau at hotmail.com>
>>> wrote:
>>>
>>>> Dear SeqFans,
>>>>
>>>>
>>>> In 1971 Richard Guy sent a letter to Neil Sloane outlining some integer
>>>> sequences; one of them is A279196,
>>>> "Number of polynomials P(x,y) with nonnegative integer coefficients
>>>> such that P(x,y)==1 (mod x+y−1) and P(1,1)=n".
>>>>
>>>> 1, 1, 2, 5, 13, 36, 102, 295, 864.
>>>>
>>>> In 2017 in a Winter Fruits talk (https://vimeo.com/201218446), Neil
>>>> said about A279196:
>>>> "I don't even know what the [...] polynomials are for the first few
>>>> values, so it might be interesting to look into this."
>>>>
>>>> = = = =
>>>>
>>>> Unaware of this context, a few days ago, I imagined this:
>>>> let the initial configuration be one token at (0, 0).
>>>> A configuration can be "degraded": to do so, { choose a nonempty pile
>>>> of tokens in it, say that at (i, j); remove one token from that pile; then
>>>> add one token at (i + 1, j) and one token at (i, j + 1) }.
>>>> The process being nondeterministic, define a(n) as the number of
>>>> distinct configurations one can possibly get after (n - 1) "degradations"
>>>> of the initial configuration.
>>>>
>>>> A brute force program that I coded gave:
>>>>
>>>> 1, 1, 2, 5, 13, 36, 102, 295, 864, 2557, 7624, 22868, 68920, 208527,
>>>> 632987, 1926752.
>>>>
>>>> Superseeker then showed me that this sequence was extending A279196's
>>>> known terms. Are the two sequences the same? I discovered the
>>>> above-mentionned context.
>>>>
>>>> It appears I can prove a(n) <= A279196(n) (see below); and I am asking:
>>>> has anyone any insights to prove or disprove the equality?
>>>>
>>>> = = = =
>>>>
>>>> Translating languages, from the piles of tokens to polynomials, is
>>>> easy: C*x^i*y^j means that the height of the pile at (i,j) is C.
>>>> The mod(x+y−1) sounds like a bridge between the two definitions,
>>>> because clearly:
>>>>
>>>> degrade(C*x^i*y^j) = (C−1)*x^i*y^j + x^(i+1)*y^j + x^i*y^(j+1) =
>>>> C*x^i*y^j + (x+y−1)*(x^i*y^j)
>>>>
>>>> Now, write P = Sum_{i,j} C[i,j]*x^i*y^j, and degrade P. We have to
>>>> choose an (i0,j0) to actually degrade; this gives:
>>>>
>>>> degrade(P) = (Sum_{(i,j)!=(i0,j0)} C[i,j]x^i*y^j) + (C[i0,j0]*x^i0*y^j0
>>>> + (x+y−1)(x^i0*y^j0))
>>>>
>>>> degrade(P) = P + (x+y−1)*(x^i0*y^j0)
>>>>
>>>> Applying "degrade" several times lets the cofactor of (x+y−1) grow
>>>> accordingly; we can write:
>>>>
>>>> degrade^<n>(P) = P + (x+y−1) * Q_n
>>>>
>>>> where Q_n keeps the record of where we took the tokens. The fact we
>>>> took exactly n tokens can be transcripted Q_n(1,1)=n. This implies:
>>>>
>>>> degrade^<n−1>(1)(1,1) = 1+(1+1−1)*(n−1) = n.
>>>>
>>>> Thus the polynomials of the degradation problem satisfy Richard Guy's
>>>> axioms and a(n) <= A279196(n).
>>>> But are there other polynomials that do? Was the degradation problem
>>>> the meaning Richard Guy had in mind, was the definition by polynomials a
>>>> way to make it succinct?
>>>>
>>>>
>>>> Best regards,
>>>> Luc
>>>>
>>>> P.S.: for essentially the same speech in a more comfortable, LaTeX
>>>> form, here is a Math StackExchange thread:
>>>>
>>>> https://math.stackexchange.com/questions/2127914/polynomials-px-y-with-nonnegative-integer-coefficients-such-that-px-y-eq
>>>>
>>>>
>>>>
>>>> --
>>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>>
>>>