Wikipedia:Reference desk/Archives/Mathematics/2019 April 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 16

Recurrence Relation

Given the recurrence:

$\forall m,n>0.\ T(n,m)=\min(\{m\}\cup \{T(a,b)+T(n-a,c)+T(n,m-bc)\ |a,\ b,\ n-a,\ c,\ n,\ m-bc\ >\ 0,\ b\leq a!,\ c\leq (n-a)!\})$

What is $T(n,n!)$? (I am intersted only in the asymptotic growth, and the no initial condition is needed, since in the "initial cases" the rightmost set is empty)

David (talk) 19:09, 16 April 2019 (UTC)

Are the inputs all taken to be positive integers? Nonnegative integers? (In the latter case, it is not clear to me that this is well-defined, in that there may be cycles in terms of which values depend on which others; in the former, at least some of the weak inequalities should be strict.) Is there a context for the question (e.g., permutation enumeration)? --JBL (talk) 23:01, 16 April 2019 (UTC)

Yes, it's about permutation enumeration.

I edited my question. Is it clear now? David (talk) 06:24, 17 April 2019 (UTC)

@עברית: no, because if a, b must always be less than m and n, then the only possibility is a = b = 1, which I don't think is what you intend.--Jasper Deng (talk) 10:07, 17 April 2019 (UTC)

@Jasper I don't see why the only possibility is a=b=1. David (talk) 10:43, 17 April 2019 (UTC)

As you stated it, n and m are independent variables, with a, b, and c dependent variables that must satisfy the stated inequalities for all valid pairs n,m. Probably not what you intended. --{{u|Mark viking}} {Talk} 18:48, 17 April 2019 (UTC)

What I mean is: for each pair n,m we get a (possibly empty) set of numbers with a,b,c that are depending on this specific pair n,m. David (talk) 21:14, 17 April 2019 (UTC)

And then we take the minimum over all such a, b, c? Then isn't this function bounded?--Jasper Deng (talk) 19:12, 18 April 2019 (UTC)

:Perhaps it would help to give some additional context on what type of permutation you're trying to enumerate. As it stands the recursion seems random and complicated and some sort of combinatorial interpretation of what T(n, m) is supposed to represent might go a long way to explain why someone would find it interesting. Also, do you have a closed form expression for T(1, m) or T(n, 1)? You might compute some values for small n and m and plug them into OEIS to see if they match known sequences. --RDBury (talk) 23:40, 18 April 2019 (UTC)

The first terms of T(n,n!) are 1,1,2,6,24,81,245 and I couldn't find it in OEIS.

Unfortunately, the context is too complicated...:\ David (talk) 10:56, 19 April 2019 (UTC)