Pascal's triangle, estimate row value by fixed row and maximum yields.

Question

let res be the max yields. Let col be a fixed positive integer. Let $f(row)=\binom{\text{row}}{\text{col}}=A$, what is the largest value for row such that $f(row) \leq A$?

Standard Pascal's triangle expression:

$\binom{\text{row}}{\text{col}} = \frac{\text{row}!}{\text{col}!(\text{row-col})!} = \text{result}$

Update

I am archiving a regression program, which takes raw data of two-dimensional vertexes, and return a function correspond to the rule. It can be called which pass in x and return a y value.

In this procedure, generator yields different amount of sample data from the raw data. For example, in simplest linear regression

$y = kx + b$

which takes a minimum points of 2, [x1, y1], [x2, y2], for working out the coefficients k and b.

Here comes the part which is the most relevant to this question.

if the raw data contains n vertexes, then the amount of iteration equal to

$\binom{\text{n}}{\text{required}} = \frac{\text{n}!}{\text{required}!(\text{n-required})!} = \text{yields}$

for instance, for linear regression, required is equal to 2. for 10 dots:

$\binom{\text{10}}{\text{2}} = \frac{\text{10}!}{\text{2}!(\text{10-2})!} = \text{45}$

However, the original design of my program is to iterate all through the amount of yields, for example, when n=10, required=2 which res=45, do an iteration of 45.

The problem is:


    n<20> required<2>: res<190>
    n<40> required<2>: res<780>
    n<60> required<2>: res<1770>
    n<80> required<2>: res<3160>
    n<100> required<2>: res<4950>
    n<120> required<2>: res<7140>
    n<140> required<2>: res<9730>
    n<160> required<2>: res<12720>
    n<180> required<2>: res<16110>

when n>=16, it freezes and overloads the machine, the fan is very loud.

Therefore, I seek for a way,

with known required, by limiting the largest amount of iteration, how many dots do I need to extract from raw data?

which the question can be briefed to:

$\binom{\text{n}}{\text{required}} = \frac{\text{n}!}{\text{required}!(\text{n-required})!} = \text{yields}$

with known the regression takes required vertexes, set a maximum iteration of yields, find a suitable n value.

Thanks very much for reading till the end. I am sorry if anything I have written doesn't make sense to you. Any help is appreciable.

I am confused, please tell me if I have misinterpreted your question. My interpretation is: for $k,n \in \mathbb{Z^+}, k \leq n$, with $k$ a fixed value, let $f(n) = \binom{n}{k}.$ Then you are asking for which value of $n$, $f(n)$ achieves a maximum. However, $f(n)$ is a strictly increasing function, given that $k$ is a fixed positive integer. What am I missing here? — user2661923, Sep 22 '20 at 08:30
@user2661923 Sorry to get u confused, I will put more details in — Weilory, Sep 22 '20 at 08:57
Let $A =$ the fixed # of yields. Let $k$ be a fixed positive integer. Let $f(n) = \binom{n}{k}.$ Are you asking : what is the largest value for $n$ such that $f(n) \leq A$? — user2661923, Sep 22 '20 at 12:42
I just rejected an attempt to add computer code to my answer. I'm not sure if the attempt came from you. If so, I'd like to explain. On mathSE we don't generally include specific code in a math oriented answer. That being said, there is no question that you can (in general, with known values for $A$ and $k$) use a computer program to search for the appropriate value of $n$ more tightly, by having the computer program compute $\log[g(n)]$ for each $n$. I omitted this (perhaps better) approach because it steps outside the boundary of the purely mathematical. — user2661923, Sep 23 '20 at 02:39

user2661923 · Accepted Answer · 2020-09-23T01:30:13.403

With respect to the comments following your query, with both $A$ and $k$ fixed, I don't know of any way of precisely computing the largest value of $n$ such that $\binom{n}{k} \leq A.$ However, I think a lower bound and an upper bound for the precise value of $n$ can be supplied, purely from the definition of $\binom{n}{k}.$

Let $B = A \times k!$.

Let $g(n) \equiv (n) \times (n-1) \times \cdots \times (n - [k-1]).$

Then you want the largest $n$ so that $g(n) \leq B.$

$g(n) < n^k,$ so if $n$ is chosen so that $n^k < B$,
then this guarantees that $g(n) < B.$

$n^k < B \iff k \log n < \log B \iff \log n < \frac{\log B}{k}.$

Therefore, a lower bound for $n$ is given by
choosing the largest $n$ such that $\log n < \frac{\log B}{k}.$

Similar analysis can be used to provide an upper bound for $n$.

Let $m = (n - [k-1]).$
Clearly, $g(n) > m^k.$
Further, if $\log m > \frac{\log B}{k}$
Then $\log m^k = k \times \log m > \log B ~\Rightarrow $
$m^k > B.$

Therefore, an upper bound for $n$ is given by
choosing the smallest $n$ such that $\log (n - [k-1]) > \frac{\log B}{k}.$

Note, that the above approach merely provides a starting point for (perhaps) attaining tighter bounds. Tighter bounds can be sought by trying to more accurately determine the geometric mean of $g(n).$

That is, you are looking for some value $r$ where $[n - (k-1)] < r < n$
and $r^k = g(n).$

It is known that the geometric mean of (for example) the integers $i$
such that $ [n - (k-1)] \leq i \leq n$
is less than the arithmetic mean of the integers in this range
(i.e. the average $V_n ~= \frac{n + [n - (k-1)]}{2}).$

This means that the first part of the above analysis, which used the idea
that $n^k > g(n)$
may instead use the idea that $(V_n)^k > g(n)$.

Repeating the analysis re the search for a lower bound for $n$
this means that a tighter (i.e. larger) lower bound can be computed
by choosing the largest $n$ such that $\log (V_n) < \frac{\log B}{k}.$

However, we have now reached the boundary of where my knowledge can offer any support.

Pascal's triangle, estimate row value by fixed row and maximum yields.

Update

1 Answers1