# Tagged Questions

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.

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 ...
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 ...
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$?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
48 views

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 ...
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 ...
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 ...
49 views

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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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), ...
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$ ...
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 ...
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$?  ...
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}$$
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 ...
261 views