9
votes
2answers
231 views

Faster formula to compute sum over partitions

Let $f$ be a function from the positive integers to the real numbers (or some ring...). Let $$(\star) \quad F(n) = \sum_{n_1 \leq \cdots \leq n_j\atop n_1 + \cdots + n_j = n} f(n_1) \cdots f(n_j), $$ ...
1
vote
0answers
103 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
0
votes
1answer
107 views

Solving a two dimensional non-homogenous linear recurrence

How one can solve the following recurrence: \begin{align} X[i,0] &=0 \quad \forall i =1,\ldots, m\\ X[m,n] &= a_n X[m,n-1]+b_n \sum_{i=k_m}^{m-1}X[i,i] +c_n \end{align} Where $a_i\ge 1 ,~ 0 ...
22
votes
4answers
958 views

Multiplying by irrational numbers in combinatorial problems

This is getting no attention on stackexchange. Everybody knows that the number of derangements of a set of size $n$ is the nearest integer to $n!/e$. It had escaped my attention until last week, ...
0
votes
0answers
67 views

Approximate closed-form solution for a recurrence

Find an (approximate) closed-form solution for $S(m, b)$. $$S(m,b)=\sum_{i=0}^{\lfloor (e-1)/2\rfloor}{e \choose i}S(m-1, b-i) \quad + \sum_{i=\lfloor (e-1)/2\rfloor+1}^{\min(b,e)}{e\choose ...
6
votes
3answers
533 views

References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...
4
votes
3answers
695 views

Linear Recurrence Relations in 2 Variables with Variable Coefficients

Consider the following recurrence relation: $$-2a_{n,m} +a_{n-1,m}+a_{n,m-1}=0,$$ where $a_{n,m} \in \mathbb{C}.$I would like a purely combinatorial way to understand the subspace of solutions to this ...
1
vote
2answers
97 views

A recursive Double sequence related to uniform Cardinal B-spline

Given a sequence $A_n(k)$ defined as follows: $A_0(0)=1$, $A_0(k)=0$ for all nonzero integers $k$ and $$A_{n}(k)=(n+1-k)^2A_{n-1}(k-1)+2(n(n+1)-k^2)A_{n-1}(k)+(n+1+k)^2A_{n-1}(k+1)$$ for all positive ...
14
votes
3answers
507 views

A question on the Laurent phenomenon

This question is motivated by my answer to 109955. It gives a recurrence relation satisfied by a function $P(n)$ whose terms a priori are rational functions (of three variables) with complicated ...
1
vote
1answer
191 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...