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

binomial-coefficients

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.

Best Answer

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.

Related Question