This tag is for basic 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)

10
votes
3answers
256 views

binomial coefficient

Prove that $$ \frac{1}{\sqrt{1-4t}} \left(\frac{1-\sqrt{1-4t}}{2t}\right)^k = \sum\limits_{n=0}^{\infty}\binom{2n+k}{n}t^n, \quad \forall k\in\mathbb{N}. $$ I tried already by induction over $k$ but i ...
0
votes
1answer
19 views

Number of ways to divide variables into two categories

I'm looking for a possible solution to find out the maximum number of combinations that can be derived from the given variables. If I'm not mistaken, I think permutations and combinations is the way ...
4
votes
0answers
21 views

Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal

Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same. I tried a bunch of equations but ...
0
votes
1answer
15 views

Distribute N items in K sets with minimum overlap

I am working on an optimization problem to distribute N distinct items (each of the items is available in infinite quantity), among K sets. Each set should have T items. (The constraint of T can be ...
1
vote
1answer
220 views

Number of ways to write a given even number as a sum of two odd numbers

Assume we are given an even number, say $2m$. Now take an even number $6 \le 2k \le 2m.$ Question, how many ways there are to write $2k$ as a sum of two odd integers $2v+1$ and $2h+1$, where $3 \le ...
0
votes
1answer
32 views

Subtraction game between alice and bob

Alice and Bob decide to play a number game. Both play alternately, Alice playing the first move. In each of their moves, they can subtract a maximum of k and a minimun of 1 from n ( ie.each of them ...
5
votes
3answers
78 views

Make $n$ cents with $1$-cent, $2$-cent, and $3$-cent coins

I encountered the following problem in Herber Wilf's book Generatingfunctionology: Prove that, in country that has $1$-cent, $2$-cent, and $3$-cent coins only, the number of ways of changing ...
1
vote
2answers
89 views

About putting $n$ distinct balls into $n$ distinct boxes.

Let the balls be labelled $1,2,3,..n$ and the boxes be labelled $1,2,3,..,n$. Now I want to find, What is the expected value of the minimum value of the label among the boxes which are non-empty ...
1
vote
2answers
26 views

Finding the number of solutions to an equation under bounds of $x$

I need to find the number of solutions to this equation under the following circumstances. $$x_1 + x_2 + x_3 = 20$$ where $x_1, x_2, x_3 \in \Bbb Z$ and $1\le x_1 \le 4$, $ 2\le x_2 \le 10$ and ...
3
votes
1answer
365 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
0
votes
1answer
248 views

Probability matching problem

Arriving at party n guests throw their hats into pile. When they leave they each take a hat that is chosen randomly from the pile. We want to compute the probability of the event $A$ that at least one ...
27
votes
6answers
3k views

Prove that the 25 people can be seated in this way

5 mathematicians, 5 biologists, 5 chemists, 5 physicists, and 5 economists sit around a large round table. Prove that the 25 people can be seated such that, if A and B are two different people with ...
5
votes
3answers
736 views

Grouping items into groups

This is a chug-plug formula given in my book : 1.The number of ways in which mn different items can be divided equally int m groups, each containing n objects and the order of the groups is not ...
3
votes
1answer
26 views

A Multi-Sport Tournament for 8 Teams

I would like to organize a tournament with 8 teams. Each team will play 4 games. The catch is no team can play the same team twice and no team can play the same sport twice. Help pls
2
votes
1answer
69 views

An estimate involving gaps in a subsemigroup of $(\mathbb N,+)$

I think this question can be solved by a high school student, maybe there is some trick on it or I'm forgetting something. Before my question, some background is required: Definition: A ...
0
votes
1answer
27 views

Value of an iterated sum

I am interested in the number of function evaluations required to numerically evaluate an iterated integral of the form $$ \int_0^t \int_{t_1}^t \cdots \int_{t_{n-1}}^t f(t_1,\ldots,t_n) dt_n\cdots ...
-2
votes
1answer
41 views

Possible Numbers formed? [on hold]

6-digit numbers formed using three 3's and three 4's?
4
votes
3answers
187 views

Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$

I just found this identity but without any proof, could you just give me an hint how I could prove it? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$ I know that $$2^n = ...
0
votes
1answer
56 views

Are there magic knight tours on a $6\times6$ or $10\times10$ board?

In mathworld, magic tour, it is mentioned that for odd $n$, only semimagic knight tours are possible on a $n\times\ n$ - board. For $n = 8$, it has been verified that there are no magic knight ...
0
votes
2answers
136 views

How many distinguishable ways are there to place all twelve animals in a circle?

Here is a problem I made up! A zoo keeper has 12 animals: 3 indistinguishable black horses, 1 gray horse, 4 indistinguishable lions, and 4 indistinguishable giraffes. He wants to arrange them all in ...
4
votes
1answer
256 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
0
votes
2answers
31 views

Problem of distribution [on hold]

If I have 15 dogs (=) and I want to distribute between 4 boys. How many different ways can do it, if each boy has to get at least a dog?
0
votes
1answer
32 views

Number of binary vectors of length $2^m$ with exactly $n$ $1$s

Consider the set $S_n$ defined as follows: $$S_n =\{b : b\text{ is a binary vector of length $2^m$ where exactly $n$ $1$s are present} \}.$$ Here $n$ is ranging from $1$ to $2^m$. Clearly $m$ is a ...
0
votes
0answers
26 views

Block design: derived designs

I am now study some theorems of block design. I have a question about the derived designs. Let $B$ be the oringinal design $t-(v,k, \lambda)$. Suppose we omit one of the points, say $P$, then we have ...
1
vote
1answer
55 views

How can I distribute 15 pennies (1 cent) and 17 nickels (5 cents)?

How can I distribute 15 pennies (1 cent) and 17 nickels (5 cents), between four children, with the following restriction: A child receives at leat 1 penny and 3 nickels The children 2,3 and 4, ...
5
votes
2answers
36 views

What is the maximum possible number of elements of $S$?

This is an interesting problem I found. Let there be a 2-digit sequence that can start with 0, like 04 or 93. Let a "nudge" be defined as exactly one of the following operations: 1) Increasing one ...
0
votes
2answers
118 views

Representative choices of four out of eleven students with three majors

I am majoring in philosophy and currently im taking a logic course. I am having trouble with this question and I think you all mathematicians could help me out. There are five philosophy majors, four ...
4
votes
0answers
26 views

For the exponential operator $e^{f(x)\frac d{dx}}= \sum_{i=0}^\infty F_i(x) \frac{d^i}{dx^i}$, is there a formula for the $F_i$ in terms of $f$?

Consider the operator $$ e^{ f(x) \frac{d}{dx} } = \sum_{i = 0}^\infty \frac{1}{i!} \left(f \frac{d}{dx} \right)^i $$ If one commutes the derivatives with the powers of $ f $, then there are functions ...
2
votes
1answer
62 views

Proving combinatorial identity with the product of Stirling numbers of the first and second kinds

$$ \sum_{k} \left[\begin{array}{c} n\\k \end{array}\right] \left\{\begin{array}{c} k\\m \end{array}\right\} = {n \choose m} \frac{\left( n-1\right)!}{\left(m-1 \right)!}, \quad \text{for } n,m > 0 ...
6
votes
5answers
249 views

Identity for $\sum\limits_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j}$?

I have run across the following multinomial series: $$ \sum_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j} $$ Here, $d>1$. This seems like a formula which has either a well-known identity, ...
0
votes
0answers
37 views

Kempe chain color swaps in a partially colored map

Question: In this partially Tait's colored map, using only Kempe chain color swaps (as many as wanted), how many differently colored maps can I have? This map has these Kempe chains: (R,G) - 1 - ...
2
votes
1answer
43 views

How many ways are there to divide $100$ different balls into $5$ different boxes so the last $2$ boxes contains even number of balls?

How many ways are there to divide $100$ different balls into $5$ different boxes so the last $2$ boxes contains even number of balls? I tried to think about tylor function but got stuck. Thanks.
2
votes
2answers
45 views

A cog wheel math puzzle

A machine has 4 cog wheels in connection. The largest wheel has 242 teeth and the others have 66,48 and 26 respectively. How many rotations must the largest wheel make before each of the wheel is back ...
1
vote
3answers
80 views

Number of groups containing at least 1 and at most k elements

In Counting of the elements in a set, I've been answered that the number of ways of grouping $n$ elements in $n_{G}$ groups such that each group contains at least 1 element is $$ {n-1 \choose ...
0
votes
4answers
97 views

How many subsets of $\{1, 2, …, n\}$ contain $1$ and how many don't? [on hold]

Consider the set $A = \{1, 2, …, n\}$ (a) How many subsets of A contain $1$? I got $ 2^n - 2^{n-1}$ (b) How many subsets of A do not contain $1$? I got $2^{n-1}$ (c) Use the pigeonhole principle ...
4
votes
2answers
104 views

Number of solutions of $x_1 + x_2 + x_3 + x_4 = 14$ such that $x_i \le 6$

Let $x_1, x_2, x_3, x_4$ be nonnegative integers. (a) Find the number of solutions to the following equation: $$ x_1 + x_2 + x_3 + x_4 = 14 $$ I got $17 \choose 3$ for this. ...
2
votes
2answers
38 views

Probability problem: n different balls in n different boxes

Problem Suppose $n$ different balls are distributed in $n$ different boxes. Calculate the probability that each box is not empty when distributed the balls. I'll define the sample space as ...
1
vote
1answer
78 views

If $P(n, k)$ is the number of partitions of $n$ elements into $k$ sets, then $P(n, k) = kP(n-1, k) + P(n-1, k-1)$ [on hold]

A partition of the set $\{1, 2, \dots , n\}$ into $k$ parts is a way of writing the set as a disjoint union of k subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup \{2, 3\} \cup \{5\}$ is a ...
0
votes
1answer
33 views

Counting antichains in the limit $n \rightarrow \infty$.

By the Dedekind number function, let us mean the function $M : \mathbb{N} \rightarrow \mathbb{N}$ given by asserting that $M(n)$ is the number of antichains present in $\mathcal{P}(X)$, where $X$ is ...
3
votes
3answers
452 views

Probability of having at least $K$ consecutive zeros in a sequence of $0$s and $1$s

I have a sequence of length $N$ consisting of $M$ ones and $N-M$ zeros. I am trying to find the number of possible arrangements that produce a sequence in which there exist at least K consecutive ...
11
votes
4answers
2k views

Combinatorial proof of a binomial coefficient summation.

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that: $$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$ I was told this is supposed to use a ...
3
votes
1answer
44 views

Sufficient condition for $n$

There are $n$ people (distinct men and women) sitting around the table. After the break they will sit around the table again. What is the sufficient condition for $n$ such that there always exists $2$ ...
2
votes
1answer
66 views

How many patterns of length 3?

I asked another question that I guess is too hard to be answered, so I have to change the problem: how many patterns with length three we can draw on an android device?
7
votes
1answer
125 views

The Day Camp Stacking Game

My friend works at a day camp as a counselor and he told me about an interesting game he plays with his group of kids. You have a perfectly shuffled, regular $52$-card deck and a group of $2 \leq n ...
14
votes
1answer
236 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
0
votes
0answers
39 views

Find solutions to given equation

Find all integer solutions $x$ for $0 < x < 10^9$ of the equation: $$x=b\cdot s(x)^a+c,$$ where $a$, $b$, $c$ are some predetermined constant values and function $s(x)$ determines the sum of ...
8
votes
0answers
425 views

How strong is the statement that Thompson F is amenable?

Justin Moore's proof turned out to have an error I just attended Justin Moore's talk on this today. Since I am neither a group theorist nor a combinatorist, and is not familiar with ultrafilters I ...
0
votes
1answer
19 views

How to show a triple represents all possible selections?

Let $Y=\{y_1, y_2, y_3,y_4,y_5\}$ Then, the choices of selecting 3 objects (repetitions allowed) from $Y$ can be represented by the triple $(y_{i_1},y_{i_2},y_{i_3})$ where $i_1 \le i_2 \le i_3$. Is ...
0
votes
2answers
91 views

Sample space of possible outcomes for a knockout tournament

I would like to confirm if my answer is correct for the following question: A conventional knock-out tournament begins with $2^n$ competitors and has $n$ rounds. There are no play-offs for the ...
2
votes
1answer
69 views

Sum of Catalan numbers

What is $C_1 +C_2 + C_3 +... + C_n$, where each $C_i$ is Catalan number? I want to know if we can bound this sum by some function of $n$. I am looking for an upper bound. For sure it is less than ...