For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

4
votes
2answers
149 views

Number of way to move form $(1,1)$ to $(n,n)$ in a square grid taking exactly $k$ turns

Given a square grid of size $n \times n (n>2)$, find the number of ways to move form $(1,1)$ to $(n,n)$ using only right and down direction and taking exactly $k$ turns( a turn is a right move ...
23
votes
4answers
1k views

Number of vectors so that no two subset sums are equal

Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 ...
1
vote
3answers
294 views

Show that ${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$

Show that $${n\choose r}2^r 3^{n-r}=\sum_{k=r}^{n} {n \choose k} {k \choose r}2^k$$ Please help me showing the above identity. I tried to solve it in algebraic way and in combinatoric way, but ...
1
vote
5answers
170 views

$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}=?$

I was asked to find a closed formula for the sum $$\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}$$ could anyone give me an advice on how to get started?
1
vote
1answer
95 views

36 Teams split into 4 groups of 9. There are 9 events and 9 rounds. A teams must face all other teams in the other groups.

Okay here is my problem. I am not sure if this is possible or not as the 8 hours i have spent on this havn't been the best. There are 4 groups of 9 teams. So we have teams A1 to A9, B1 to B9, C1 to ...
2
votes
2answers
147 views

in how many ways $n$ white (identical ) balls and $n $ colorful (n different colors) balls can be placed in $2n $

in how many ways $n$ white (identical ) balls and $n $ colorful (n different colors) balls can be placed in $2n $ cells such that in each cell: $$$$a. at the most one ball. answer $_{2n}C_n\cdot n!$ ...
2
votes
1answer
66 views

Prove that between $1001$ numbers we can pick $3$ such that $1$ is the sum of the other $2$

As much as basic this question might be for you, I find it hard to solve. I need to prove that between $1001$ different numbers, smaller than $2000$, we can choose $3$ such that one of them would be ...
0
votes
1answer
50 views

in how many ways 10 adults 60 children (20 boys 40 girls) can be placed in a row,

In how many ways $10$ adults and $60$ children ($20$ boys $40$ girls) can be placed in a row, such that between $2$ adjacent adults are exactly $6$ kids? The answer is $7*10!*60!$. Why do we multiply ...
5
votes
2answers
223 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
2
votes
1answer
175 views

Two very difficult induction proofs; having trouble with the inductive step

$$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+1}\frac{n-2k-1}{k+1} = n-2 + \frac{1}{n+1}\binom{2n}{n}$$ $$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+2}\frac{n-2k-1}{k+1} = -n + ...
2
votes
1answer
81 views

Combinatorics - inclusion exclusion, check my answer

It's my second try to solve the question I posted here Combinatorics question - How many different ways to change sitting order I got some really good advice, but no one said the answer, I solved it, ...
2
votes
2answers
70 views

Generating functions - difficulty with question

Find the number of non-negative integers solutions to the equation $$x_1+x_2+x_3+x_4=12$$ when $x_1=2x_2+2$ and $x_3 \le x_4$. My try: Iv'e substituted $x_1$, thus the equation is ...
1
vote
1answer
73 views

23,000 sticks & 500 balls

I am trying to solve two questions that relate to self study. I phrased the questions in a way that makes sense to me, so please ask for clarification if my questions are unclear. Situation: 23,000 ...
3
votes
2answers
755 views

Number of ways to interleave two ordered sequences. [duplicate]

Suppose we have two finite, ordered sequences $x = (x_1,\dots,x_m)$ and $y = (y_1,\dots,y_n)$. How many ways can we create a new sequence of length $m+n$ from $x$ and $y$ so that the order of elements ...
0
votes
3answers
64 views

Proof of a common expression in Combinatorics. [duplicate]

I would like to know a mathematical proof of the following expression: $${\sum\limits_{r=0}^n {n\choose{r}} {=} {2^n}}$$ Thank you!
1
vote
5answers
106 views

expression for$\sum_{k=0}^{n}(k+1)(k+2)$

what is a closed expression for$\sum_{k=0}^{n}(k+1)(k+2)$? the answer says to look at Generating function $a_k=(k+1)(k+2)$ and derive twice $\dfrac{1}{x}=1+x+x^2+...$ so the solution starts: ...
2
votes
1answer
405 views

Probability of couples seating arrangements at a rectangular table

Problem: Suppose $n$ couples are seated at a rectangular table with husbands on one side and wives on the other. What is the probability that no husbands are seated directly across from their wives? ...
1
vote
1answer
34 views

Finding all “bad” triangles in a full-simple-graph

Let $G = \left\langle {V,E} \right\rangle$, a simple and complete graph with the size of $n$. Each edge in the graph can be colored with blue or red. A "bad" triangle defined to be a triangle ...
0
votes
2answers
82 views

Distribute 11 fish to 4 persons, where each person should have at least 1 fish and the fishes are not all identical

I have a problem that I have not been able to find a solution to: There are 9 black fishes, 1 yellow fish and 1 blue fish that are to be given to four (distinct) persons. Each person should have at ...
2
votes
1answer
963 views

Combination's problem (AMC 12A 2014)

A fancy bed and breakfast inn has 5 rooms, each with a distinctive color-coded decor. One day 5 friends arrive to spend the night. There are no other guests that night. The friends can room in any ...
1
vote
3answers
62 views

Combination - Probability. Probability within a set of 2

I am stuck on a homework question. The question is If there are 6 couples. (12 individuals) and 6 prizes are to be given out to these 12 individuals. What is the probability of a couple receiving a ...
1
vote
1answer
122 views

Solving a nontransitive dice problem

I have a dice problem I would require some help with (especially problem b). Here goes the problem: Player 1 and Player 2 are playing a dice game, where both first select one die and then they throw ...
2
votes
1answer
379 views

Combinations from two groups

I am stumped on a problem with two parts. First part I think I might have done correctly, Second part im lost From a group of 4 women and 6 men, In how many ways a committee consisting of 2 women ...
1
vote
2answers
328 views

Recursive formula for tiling checkerboard

The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper ...
0
votes
1answer
56 views

Combination of Choosing Identical Items into Identical Slots

Renee has a bag of $6$ candies, $4$ of which are sweet and $2$ of which are sour. Jack picks two candies simultaneously and at random. What is the chance that exactly $1$ of the candies he has picked ...
0
votes
1answer
36 views

Recursion $a_n=2a_{n+1}+8a_n$ with cardinality RxR

Recursion $a_{n+2}=2a_{n+1}+8a_n$ has a characteristic polynomial $t^2-2t-8$ with roots $t=-2,4$ so the set is the series of ${\alpha(-2)^n+\beta4^n}$ so why its cardinality is RXR? Fixed a typo ...
0
votes
2answers
52 views

Counting lists of length $100$ from the set $\{0,1,2\}$ such that the total is $n$

Let $b_n$ be the number of lists of length $100$ from the set $\{0,1,2\}$ such that the sum of their entries is $n$. How does $b_{198}$ equal ${100\choose 2}+100$?
10
votes
1answer
252 views

Direct combinatorial proof of a sum identity on formal Lagrange polynomials

Let $k$ be a field and $K=k(x_0,x_1,\ldots, x_n)[x]$. Define $$\mathcal{L}_k(x)\triangleq \prod_{\substack{j=0\\ j\ne k}}^n\frac{x-x_j}{x_k-x_j}.$$ Is there a purely combinatorial way to show ...
0
votes
1answer
102 views

Stock cutting and column generation giving suboptimal answers?

I'm doing a stock cutting implementation. I use the delayed column generation approach. I'm getting suboptimal answers with the following simple case: raws length: 630 in. demands: 10 x ...
1
vote
1answer
1k views

Formula for binary sequences of length m with no n consecutive 1s?

Formula for binary sequences of length $m$ with no $n$ consecutive $1$s? I know The number of binary strings of length $m$ without consecutive $1$s is the Fibonacci number $F_{m+2}$. But how about ...
4
votes
2answers
111 views

Counting tilings of a $2\times n$ board

Let $n=>1$ be an integer and consider a $2*n$ board $B_n$ consisting of $2n$ cells,each one having sides of length one. This picture shows $B_{13}$: For $n=>1$, let $a_n$ be the number of ...
2
votes
1answer
537 views

How many ways to distribute $k$ indistinguishable balls over $m$ of $n$ distinguishable bins of finite capacity $l$?

Lets assume the non-trivial case $k < l \cdot m$. Each bin can receive a maximum of $l$ balls. I need distribute $k$ balls over $n$ bins so that some $m < n$ bins are occupied (not necessarily ...
0
votes
2answers
137 views

Combinations of coins

If I have 8 dollars, 7 50c pieces, 4 25c pieces and 3 10c pieces in a container, how many way are there to take 6 coins from the container? First there are questions which are raised, what if we ...
3
votes
1answer
74 views

Number of combinations subject to constraints

Consider the set of all possible vectors consist of $n$ positive integers, $x_1,x_2,...,x_n$, such that $1 \le x_i \le K$ ($K$ is a positive integer) for all $i$. There are of course $K^n$ such ...
0
votes
0answers
48 views

Optimal substructure with regard to making change.

Suppose we have a set of integers $\{a_1,a_2\dots,a_n\}$. with the property that any integer number is of the form $c_1a_1+c_2a_2\dots+ c_n a_n$ with all the $c's being non-negative integers. The ...
2
votes
2answers
223 views

Articles on matchstick puzzles

There are many ingenious puzzles involving matchsticks that are arranged as squares, rectangles or triangles, and can be moved under some restrictions (for a lot of examples see ...
2
votes
2answers
161 views

Proving strings [duplicate]

We consider strings of n characters, each character being a, b, c, or d, that contain an even number of as. (0 is even.) Let $E_n$ be the number of such strings.Prove that for any integer $n ...
3
votes
2answers
483 views

Probability of a specific boy and a specific girl sitting next to each other

There are $5$ boys and $4$ girls in a class. The boys and girls are seated at a movie theater in a boy-girl fashion. What is the probability that a specific boy, Andrew, is seated next to a specific ...
2
votes
0answers
502 views

How should I count visitors to a website that receives visitors from 3 locations?

I'm doing a programming exercise, these are the instructions: TLDR version of problem below Priority Our website receives visitors from 3 locations and the number of unique visitors from each of ...
2
votes
2answers
60 views

$\sum_{k=0}^n k \binom{n}k=n\cdot2^{n-1}$

I need to prove that $\sum_{k=0}^n k \binom{n}k=n\cdot2^{n-1}$ using Combinatorial argument I know this can be done by differentiating binomial expansion of $(1+x)^n$ and then putting $x=1$ , but ...
1
vote
1answer
48 views

Permutation (without repeating)- (basic)

I have problems solving and understanding the following task from the combinatorics: We have two sets: $\mathcal A=${$x; (x\in Z)$ $\land$ $(-6 \le x \lt 0)$} and $\mathcal B=${$n; (n\in N) \land ...
2
votes
1answer
224 views

Recursion- to pave 2xn rectangle

Can you explain the recursion for the number of ways to pave rectangle of size $2\times n$ with tiles of size: $1\times 1$, $1\times 2$, $2\times 1$. When $a_n$ is the possible ways to pave ...
1
vote
2answers
239 views

Ways to color an octagon's vertices with three colors?

In how many ways can we color the 8 vertices of an octagon each red, green, or blue, so that no two adjacent vertices are the same color? I think there should be something to do with Catalan numbers ...
2
votes
2answers
56 views

Is it true that $\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3} = \binom{n}{3}\binom{n-3}{k-3}$?

I was asked to find a closed formula for $$\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3}$$ To remove the $\sum$ if you will. Here's my reasoning, let's say we have a football team with $n$ players. First we ...
2
votes
1answer
68 views

Prove that in each coloring of a $4\times7$ board in two colors there's a square that all four of it's corners are colored by the same color

Prove that in each coloring of a $4\times7$ board in two colors there's a square that all four of it's corners are colored by the same color. This is a pigeon hole principle question and I have a ...
13
votes
3answers
431 views

Show that $\sum_{k=0}^n\binom{2n}{2k}^{\!2}-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove the identity: $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
0
votes
1answer
44 views

Proving if equation is $O(\log n)$

How do I prove if \begin{equation} 2\log(n^{2}\log n) = O(\log n) \end{equation} is true? I began by trying to find a $C$ where \begin{equation} 2\log(n^{2}\log n) < O(\log n) \end{equation} ...
4
votes
2answers
293 views

How many strings contain every letter of the alphabet?

Given an alphabet of size $n$, how many strings of length $c$ contain every single letter of the alphabet at least once? I first attempted to use a recurrence relation to work it out: $$ T(c) = ...
2
votes
1answer
64 views

Generating function for combinatorial problem

Find the number of possibilities to divide $n$ balls into $3$ cells, such that: In the first cell there must be at least one ball. No limitations for middle cell. In right cell, the number of ...
1
vote
2answers
400 views

How many ways are there to arrange a basket with 12 fruits comprised of 4 different kind of fruits with no more than 4 of the same kind

In how many ways is it possible to make a basket with 12 fruits comprised of passionflower, lychee, mango and berries where the number of each kind of fruit isn't higher than 4 ? So this is ...