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)

0
votes
1answer
65 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
53 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
268 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
104 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
2answers
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
569 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
140 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
235 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
168 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
535 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
504 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
49 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
303 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
277 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
69 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 ...
14
votes
3answers
447 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
47 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
364 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
453 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 ...
2
votes
2answers
86 views

Where is the mistake in this argument about number of different balls with replacement

Out of $N$ distinguishable balls, I draw $A$ balls with replacement. On average, there are $$B=N\left(1-\left(1-\frac 1 N\right)^A\right)$$ different balls. I am interested in how many times a drawn ...
0
votes
2answers
83 views

Tree (graph theory)

In how many trees with $ n $ vertices the number of leaves is exactly:a.$2$ b.$n-1$ Why in $b$ Inclusion–exclusion principle need to be used while in $a$ Factorial? answer for a is: $(nC2)*(n-2)!$ ...
3
votes
2answers
184 views

Number-Theoretic Coin Puzzle

There are three piles of coins. You are allowed to move coins from one pile to another, but only if the number of coins in the destination pile is doubled. For example, if the first pile has 6 coins ...
0
votes
1answer
209 views

Creative easy combinatorics problems. [closed]

I would like cool problems of the following style: how many marbles need to be taken out of a jar to guarantee we have one of each color? I need some cool problems for some classes I want to give to ...
5
votes
1answer
460 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 ...
6
votes
3answers
2k views

count the ways to fill a $4\times n$ board with dominoes

After solving this problem from SPOJ (count the ways to fill a 4xn board with 2x1 dominoes) I found a different solution while searching on internet. This solution uses the recurrence relation $f(n) ...
2
votes
2answers
550 views

How am I counting the possibilities incorrectly in this combinatorics problem?

I've been working through some problems in Statistical Inference Second Edition (George Casella, Roger L. Berger), one of which is this already discussed problem. While the answer given makes sense, ...
3
votes
5answers
298 views

Prove an equality using combinatorial arguments

$$n \cdot {2^{n - 1}} = \sum\limits_{k = 1}^n {k\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array}} \right)} $$ The left-hand side can describe the number of possibilities choosing a ...
1
vote
3answers
125 views

In how many ways can one distribute ten distinct pizzas among four students with exactly two students getting nothing?

In how many ways can one distribute ten distinct pizzas among four students with exactly two students getting nothing? How many ways have at least two students getting nothing? For the first part I ...
0
votes
2answers
34 views

Number of possibilities arranging $k$ balls in $t$ cells.

What is the number of possibilities arranging $k$ balls in $t$ cells, where: More then one ball in a cell is allowed. balls are different (e.g. every ball has a unique color). I understood the ...
4
votes
2answers
243 views

Is it possible to be “too good” at Spider Solitaire?

There was a similar question here: Losing at Spider Solitaire However, what I'm asking is different. The game has a rule that it would not deal the next ten cards, unless there is already a card in ...
2
votes
1answer
44 views

simple combinatorics question - what did I do wrong?

I was asked the following question. I solved it, I thought my solution is correct, but it turns out I was mistaken, I'd like to know why. Question: How many ways are to order 4 sets $(A,B,C,D)$ such ...
5
votes
0answers
461 views

Counting simple quadrilaterals in a rectangular lattice.

I've been trying to make an algorithm to find the number of all possible simple quadrilaterals in a N*M lattice. I already have a brute force solution but since this is a Project Euler problem I ...
2
votes
1answer
97 views

Combinatorics - possibly pigeon hole, 100 by 100 matrix with numbers from 1 to 100

We are given a $100$ by $100$ matrix. Each number from $\{1,2,...,100\}$ appears in the matrix exactly a $100$ times. Show there is a column or a row with at least $10$ different numbers. I'd like a ...
0
votes
1answer
55 views

What kind of formula would I use to get all possible outcomes?

I am into a CCG, and I got a question come to mind "how many possible out comes are there for deck combinations?" The game is broken into three: Main Character (6 cards available, only one deck), ...
1
vote
2answers
123 views

Calculating how many integers are between $0$ to $9999$ that has all of the digits $2,5,8$

Calculate how many integers between $0$ to $9999$ that has the digits $2,5,8$. That is integers that has each of the three numbers at least once. This is similar to How many numbers between $0$ ...
1
vote
4answers
57 views

Subsets and combinatorics

Let $A = \{1,\ldots,n\}$. Also, consider $y$, a subset of $A$ with the size of $k$. What is the number of subsets, such that $x \subset y$ ($x\ne y$). I know the answer is $2^k-1$, but cannot ...
3
votes
2answers
129 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$? $$$$ ...
0
votes
1answer
91 views

Product formula for $\sum_{k=0}^n\frac{(-1)^k}{2k+1}\binom{n}{k}$ [duplicate]

How to prove the following identity: $$\sum_{k=0}^n\frac{(-1)^k}{2k+1}\binom{n}{k}=\prod_{k=1}^n\frac{2k}{2k+1}$$
2
votes
1answer
166 views

Pick balls of unequal weights from a given set of balls

It all started with this Q: There are 8 balls. Four of them weigh X grams each, and the other four weigh Y grams each. Your task is to find two balls having different weights. You have a ...
-1
votes
1answer
261 views

Integer linear combinations of coprime integers

Consider the finite set $S=\{s_1,s_2,\dots,s_n\}$ such that $GCF(s_1,s_2,\dots,s_n)=1$. Show that $\exists n$ such that $n$ cannot be written as $n=c_1s_1+c_2s_2+\dots+c_ns_n \forall c_i,s_i \in ...
-1
votes
1answer
161 views

Proving Big O(1) [closed]

How do I determine if the below is true or false? \begin{equation} 17^{100} + \frac{1}{n} = O(1)? \end{equation} I have tried using the c and No method but still can not come up with a solution.
1
vote
1answer
56 views

Maximum Number Of Points (Combinatorics)

The problem is like the following. Let $n$ blue lines, no two of which are parallel and no three concurrent, be drawn on a plane. An intersection of two blue lines is called a blue point. ...
2
votes
1answer
80 views

Finding the super-mean (NOT the mean) of a set of numbers.

the super-mean is found by grouping pairs of numbers and finding the average successively until there is just one number. For example, $$(1-2-3-4-5) \to ((1+2)/2,(2+3)/2,(3+4)/2,(4+5)/2) \\ ...