1
vote
1answer
29 views

Algorithm for retrieving all the permutations (randomized) for a vector sequence 1…N with only unique values

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$). I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
2
votes
2answers
24 views

MNTILE SPOJ Tiling patterns

We have tiles of size 2 * 1. We need to arrange the tiles to get the floor size of m * n. For ...
1
vote
1answer
40 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
1
vote
1answer
48 views

Infinite series for recurrence

Question 1 If I define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \tag 1$ (where $a_n$ are $3\times 3$ constant matrices indexed with n), then can we re-write $\sum_{n \ge 1} a_{n-1} \frac{z^n}{n!} ...
1
vote
0answers
41 views

Recurrence relation for Binary String Question

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is: "Given an infinite length random binary string, what is ...
3
votes
1answer
48 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 & = & ...
1
vote
1answer
27 views

Recurrence relation and combinatorics

I am reading p.4 of the article http://mercercountymathcircle.files.wordpress.com/2014/03/recurrence_relations.pdf which consider the following problem: Find the units digit of ...
1
vote
0answers
73 views

Need help with these recurrence relations

I had received some challenging recurrence last week, I did most of them except this and also one of its kind. It states Given $a_0=0$ and $a_1=1$, solve these recurrence relations: ...
1
vote
2answers
39 views

Generating function satisfying a second degree equation

I got this problem in an exercise list: Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation: $$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, ...
1
vote
1answer
71 views

Divide and Conquer (recurrence relation problem)…

The problem: (a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers. (b) Give a recurrence relation for ...
3
votes
2answers
56 views

Solving combinatorical problem using characteristic polynomial

How many $6$ length strings above $\left\{1,2,3,4\right\}$ are there such that $24$ and $42$ aren't allowed. The suitable recurrence relation for this problem is: $a_{n+2} = 2a_{n-1} + ...
1
vote
2answers
62 views

Counting numbers with the digit 5: How to express recurrence relation in closed form?

I figured out the algorithm for finding the count of numbers containing the digit 5 for any power of 10. What is the correct way to express y in this formula? $f(x) = 9y + (x/10)$ Where y is ...
1
vote
2answers
53 views

Is there a standard recurrence relation to solve this?

I have infinite supply of $m\times 1$ and $1\times m$ bricks.I have to find number of ways I can arrange these bricks to construct a wall of dimensions $m\times n$. My problem is how can I approach ...
0
votes
1answer
45 views

Stirling number of the second kind recurrence relations

I am interested to understand why the following recurrence relations of the Stirling number so the second kind hold using counting arguments ...
-2
votes
1answer
42 views

N balls of k colors on a cirlce, no two neighboring balls have same color - recursive algorithm

Suppose we have N balls of k different colors. What is the number of arrangements of these N balls on a circle with no two neighboring balls having the same color? Actually, the task is to make up a ...
1
vote
5answers
109 views

A non-homogenous linear recurrence: Why does my method fail?

I'm trying to solve this recurrence relation: $$a_m = 8 \cdot a_{m-1} + 10^{m-1}, a_1=1$$ By the change of variable $\displaystyle b_m = \frac{a_m}{10^m}$ I obtained this linear non-homogenous ...
2
votes
3answers
152 views

Fibonacci polynomials and factorization redux

I recently asked a question about factorizing a certain expression involving Fibonacci and Lucas polynomials. That question had a very simple and nice answer, but now I've come across another similar ...
2
votes
1answer
55 views

Number of ways to derive the number 14 using a recursive definition of EVEN numbers?

I have the following recursive definition for the construction of EVEN Numbers- [RULE 1]: 2 is an EVEN number. [RULE 2]: If x is an EVEN number and y is an EVEN number, then x+y is also an EVEN ...
7
votes
1answer
303 views

How to prove this sequence of inequalities

The number $c_{g}(n)$ is defined by the recurrence \begin{equation} c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) , \end{equation} with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$. ...
3
votes
2answers
101 views

Deriving a (tricky, I think?) recurrence relation

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at. "Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), ...
0
votes
2answers
46 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
1answer
46 views

Count how many arrays of a specific type exist - O(N) Dynamic Programming

Consider an array of N + 2 binary digits (1 and 0), which contains at least one '1' and three '0'. The last and first digit of the array is 0. Given two numbers, let's say p and q, determine how many ...
1
vote
0answers
62 views

Solving a Recurrence Relation With Summation and Tau Function

How can I solve the following: $$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$ Where $d(n)$ is the Tau function, and v is the set of values dividing n. e.g. $d(18) = ...
0
votes
2answers
45 views

Ways to add a number using just 1's, 5's, 10's, 25's, 50's

given the set $\{1, 5, 10, 25, 50\}$, in how many ways, can you combine this numbers to get a specific number. For example, 11 can be shaped as $1\cdot11$, or $5\cdot112 + 1\cdot111$, or $10\cdot111 + ...
1
vote
0answers
33 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...
3
votes
2answers
83 views

Is there a closed-form solution to this recurrence?

A friend and I were examining polynomials of the form $p_n (x) = x (x+1) (x+2) \cdots (x+n -1)$ and we were trying to come up with some kind of closed form for the coefficients when the polynomial is ...
2
votes
1answer
70 views

Combinatorics on letters

How many "words" of length n is it possible to create from {a,b,c,d} such that a and b are never next to each other?
0
votes
0answers
46 views

Removing the Summation (Closed Form)

The following question from "Combinatorics of Permutations" : $$ E[X] = \sum\limits_{k = 2}^n \frac{k\cdot T(n,k)}{n!} $$ where $$ T(n,k) = k \cdot T(n-1, k) + 2 \cdot T(n-1, k-1) + (n-k) \cdot ...
0
votes
0answers
13 views

General expression for this reccurent derivative?

I stumbled upon a problem that can be distilled to: Let $\Delta_m(x)$ be some function that depends on $x$ such that $$ \delta_{x}\Delta_m(x) = \Delta_{m+1}(x)$$ where $\delta_{x} $ is the ...
1
vote
2answers
35 views

Find the linear reccurence of degree at most 2 of most 2 for the following sequence

Suppose $a_0,a_1,a_2$ satisfy the recurrence $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}$ for $n\ge3$ Let $c_n=a_{n+1}-a_n$ for $n\ge1$ and $c_0=0$ Find a linear recurrence of degree at most 2 for the ...
4
votes
3answers
159 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
0
votes
2answers
44 views

How to find the linear recurrence in this case?

Suppose $c_0$, $c_1$, $c_2$ satisfies the recurrence $c_n = 3c_{n−1} − 3c_{n−2} + c_{n−3}$ for $n ≥ 3$. Let $a_n = c_{n+1} - c_n$ for $n \geq 1$, and $a_0 = 0$, how to find a linear recurrence of ...
1
vote
2answers
70 views

How to find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / b(x)$?

Consider the sequence $c_0, c_1, c_2,\ldots$ satisfying $c_i =2\cdot 3^i − i^2\cdot(−1)^i$. Let $c(x) = c_0 + c_1x + c_2x^2 + \ldots$ Find polynomials $a(x)$ and $b(x)$ such that $c(x) = a(x) / ...
0
votes
2answers
77 views

Recurrence relation of order $n$: $f(n) = \dfrac{1}{k-1}\sum\limits_{i=1}^n {n \choose i} f(n-i)$.

I came across this recurrence relation while looking for a closed form for $S(n,k) = \sum\limits_{i=0}^\infty \dfrac{i^n}{k^i}$.After a few manipulations, I came across this recurrence relation: $f(n) ...
5
votes
1answer
298 views

Purely combinatorial proof and simplification of identity involving factorials and summations

While trying to decompose factorials into summations, I came up with the following identity $$(n+2)! = 2^{n+1} + \sum\limits_{k=0}^{n-1}\sum\limits_{i=0}^{n-1-k}\sum\limits_{S \subseteq ...
3
votes
2answers
74 views

recursion-consecutive numbers

what is the number of subsets of the set {k∈N|1≤k≤n} with no two consecutive numbers? The answer says: $$a_n=a_{n-1}+a_{n-2}$$ with the starting conditions: $$a_0=1, a_1=2$$1. why does $a_1=2$? $$$$ ...
2
votes
1answer
33 views

Four or More Heads in a Coin Toss

How would one write a recursion for the number of ways to get 4 or more heads in a row in 10 tosses of a coin? Would it suffice to use the recursion H(n)=H(n-1)+H(n-2)+H(n-3)+H(n-4) for the number of ...
0
votes
2answers
92 views

Combinatorics - Check my answer, sitting order, round table.

$n$ people are sitting at a round table with $n$ seats at a restaurant. The restaurant has only 2 dishes, steak and salad. How many ways are there for the diners to choose a dish, such that no 2 ...
0
votes
1answer
70 views

number of ways to fill a 2D grid

We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
2
votes
2answers
55 views

Question with recurrence - Check my answer and suggest better ideas

Every morning when he gets up, Oria leaves the house for a walk. he walks exactly $n$ steps. He can walk only forward, right, or left, and he will never turn left immediately after he turned right, ...
0
votes
2answers
47 views

Recurrence relation - Show that a sum of a sequence is zero

We are given the following sequence: $f(n)=4f(n-1)-5f(n-2)$, $f(0)=f(1)=a$ where $a$ is some value in $\mathbb C$. We are asked to show that $$\sum_{n=0}^{\infty}\frac{f(n)}{3^n}=0$$ First thing I ...
2
votes
3answers
108 views

Solving recurrence relation with generating functions - Nearly got the answer

I'm trying to solve the following recurrence relation (Find closed formula) using generating functions: $f(n)=10f(n-1)-25f(n-2)$, $f(0)=0$, $f(1)=1$ I'm having a small difficulty at the end and can ...
0
votes
1answer
62 views

Period of recurrence relation mod p

For a recurrence relation like $$f(n)=((k-2)*f(n-1)+(k-1)*f(n-2) )\bmod p$$ with initial conditions .This recurrence holds for n>=4 $$\begin{align}f(1)&=k \bmod p\\ f(2)&=k*(k-1) \bmod ...
2
votes
5answers
106 views

Finding a recurrence relation in combinatorics

First, my English is not that good so please don't laugh. I need to find a recurrence relation for : The number of words with the length of n that could be composed from the letters A,B,C,D, so the ...
0
votes
1answer
79 views

How many words can you make with {1,2,3,4} such that difference between 2 letters is 1

Hello and happy new year. I've been struggling with this question and I really need some help. The question is, find a recurrence relation that demonstrates how many words of length $n$ can we write ...
2
votes
5answers
64 views

stuck trying to solve nonhomogeneous recurrence relation

hello and happy new year! I'm trying to solve this question: We are required to find the solution (direct formula) of the following recurrence relation: $b(n)=b(n-1)+n-1$, $b(0)=0$. What I did: I ...
2
votes
1answer
113 views

Closed form solution to a recurrence relation (from a probability problem)

Is there a closed form solution to the following recurrence relation? $$P(i,j) = \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$ where $P(i,j)=0$ for $j<5$. The ...
0
votes
1answer
61 views

Recurrence relation question - check my answers! Basic questions.

I had a chat with a friend about these questions (they are homework questions) , and we argued about the solution. I would just like an outside opinion about my answers: 1) $n \geq 2$ people are ...
0
votes
1answer
88 views

Recurrence relation - simple question. Homework. Permutations with a twist,

I think I solved it but I would love someone to tell me if I'm wrong. the question is as follows: $n$ people are sitting on a bench with $n$ seats. Find a recursive equation that calculates how many ...
2
votes
1answer
73 views

Recurrence relations - simple questions, please verify my answers.

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving ...