3
votes
2answers
82 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
45 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
39 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
58 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
33 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
30 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
77 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
52 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
36 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
11 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
30 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
156 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
43 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
68 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
279 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
57 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
28 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
75 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
53 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
53 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
44 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
79 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
50 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
81 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
63 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
59 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
0answers
97 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
53 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
70 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
63 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 ...
0
votes
1answer
36 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
3
votes
1answer
49 views

Find the number of ways that 2n people may be paired.

Question: Find the number of ways that 2n people may be paired. I have figured this problem out, and I'm fairly certain that there are $\frac{(2n)!}{2^{n} n!}$ ways. However, I cannot seem to work ...
2
votes
3answers
71 views

Solve the recursion $a_{n} = n a_{n-1} + (n+1)!$

Define the sequence $\{a_{n}\}$ by $a_{n} = n a_{n-1} + (n+1)!$ for $n \geq 1$ and setting $a_{0} = 1$. Solve this recursion completely. I can solve this rather easily by an induction argument, where ...
1
vote
2answers
150 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
1
vote
1answer
102 views

Devise recurrence formula for restricted strings over alphabet $\left\{0,1,2\right\}$.

Let $A_n$ denote set of strings over characters $\left\{0,1,2\right\}$ of length $n$ which do not contain substring $22$. Moreover let $B_n$ denote set of strings which both do not contain ...
2
votes
2answers
48 views

Combinatorics arrangement on chessboard

How many ways we can fill $n\times n$ chessboard (with any number of pawns) so that out of every two pawns, one of them was to the left and and down from the second? My ideas: I think that this task ...
2
votes
0answers
34 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
3
votes
1answer
74 views

Generating and solving recurrence relations

I am trying to do this question but don't know where to go from here: The question: For $n\ge1$ let $t_n$ be the number of ways to tile the squares of a 2xn checkerboard using 1x2(which can be rotated ...
0
votes
2answers
62 views

Recursive formula to the number of words length n with restrictions

Looking for recursive formula to the number of words length $n$ with the letters $A,B,C $and the following restrictions: neither $AB$ nor $CA$ can occur as a string in the word. I tried to build a ...
1
vote
1answer
88 views

A self-convolution formula that counts bracket expressions

Problem: Consider an alphabet of size $m+2$, consisting of the two bracket symbols $\ [ \ ] \ $ plus $m$ non-bracket symbols ($m \ge 0$). Define $f_m(n)$ to be the number of length-$n$ strings on this ...
1
vote
1answer
161 views

Combinatorics recurrence relation - n digit ternary sequences (non homogenous)

I had a combinatorics problem that I was hoping someone could help with: Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any ...
1
vote
1answer
163 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
0
votes
2answers
31 views

Number of ways to arrange n identical stones into piles

Given, there are n stones which are identical. How many ways can the stones be arranged into piles. Suppose if n=4 , we can make one pile with 4 stones or 2 piles with 3,1 or 2,2 or 3 piles with 1,1,2 ...
2
votes
1answer
77 views

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a ...
1
vote
1answer
161 views

Combinatorics - Recurrence relation with n letter sequences

I had a particular question about a recurrence relation: Find a recurrence relation for the number of $n$-letter sequences using the letters $A, B, C$ such that any $A$ not in the last position of ...
2
votes
1answer
213 views

Recurrence relation and ternary sequences

I had a question that I need some help on: Find and solve a recurrence relation for the number of n-digit ternary sequences with no consecutive digits being equal As I worked this out, I ...
2
votes
2answers
201 views

Nonhomogeneous Recurrence Relations

Solve the nonhomogeneous recurrence relation $$h_{n}=3h_{n-1}-2$$ $$n\geq 1$$ $$h_{0}=1$$ I have been told to approach this type of problem using two steps. First, solve the corresponding ...
2
votes
0answers
129 views

Induction proof of a recurrence relation

I have some trouble with an induction proof for the following problem. There is a vending machine that only takes coins of value 1 and 5 respectively. Let $S_n$ be the number of different ...
0
votes
1answer
44 views

Exponential Generating Function - Bona (3rd Edition) Ch. 8 #29

Let $a_0 = 0$, and let $a_{n+1} = (n-1)a_n + n!$ for $n \ge 0$. Find an explicit formula for $a_n$. I have gotten to the point where I have $\sum_{n \ge 0}a_{n+1}\frac{x^{n+1}}{(n+1)!}=\sum_{n \ge ...