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)

1
vote
0answers
25 views

Counting zeros in a factorial(terminal + zeros in between digits)

The usual counting zeros in a factorial asks to count only the terminal zeros.This question, which also asks to count the zeros that are in between digits,for example, 8! (40320, has a zero between 4 ...
1
vote
2answers
74 views

Pulling aces from a split deck

I have a normal deck of 52. I pull the aces, deal it in to 4 piles of 12, and put an ace in each pile. I shuffle each pile like a monkey on meth. I flip cards from one pile, and when I see its ace ...
0
votes
0answers
16 views

Quotients in exterior products

I just started learning exterior products. The way I understand it, one can associate a subspace with with a bunch of spanning vectors using an alternating multilinear form. The 'k-blade' remains ...
0
votes
3answers
19 views

Game of Score Four

How many possible sequences of length 64 and made from the characters 0123456789ABCDEF are there, where each character appears exactly 4 times. (This is no homework! I am trying to calculate an upper ...
2
votes
0answers
20 views

Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
2
votes
0answers
37 views

the numer of monic irreducible polynomials of degree $3$ in $\mathbb{F}_q$

I want to know how hany monic irreducible polynomials of degree $3$ there are in a field $\mathbb{F}_q$. The whole number of monic polynomials of degree three is $q^3$. Now I want to find out how ...
0
votes
2answers
40 views

Boxes and colored balls with replacement

Suppose there are $n+1$ boxes numbered from $0$ to $n$. The $i$-th box contains $i$ white balls and $n-i$ black balls. A box is chosen randomly and a ball is selected from the box, after that the ...
1
vote
1answer
63 views

Prove $1! + 2! + . . . + n! < (n + 1)!$ using mathematical induction [duplicate]

$1! + 2! + . . . + n! < (n + 1)!$ This question has left me stumped for quite some time. I am not sure how to approach it. (I am really bad at induction).
2
votes
2answers
94 views

Pólya's urn scheme, proof using conditional probability and induction

Problem An urn contains $B$ blue balls and $R$ red balls. Suppose that one extracts successively $n$ balls at random such that when a ball is chosen, it is returned to the urn again along with $c$ ...
1
vote
3answers
62 views

Explanation for the number of partitions of $\{1,\dots,n\}$ into $k$ parts

A partition of the set $\{1, 2, . . . , 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 ...
2
votes
1answer
28 views

Sum of combinations of the n by consecutive k

In a book, I found that the sum of combinations: $\binom{n}{k} + \binom{n}{k+1} +\cdots+ \binom{n}{n}$, where k starts from 0, equals $2^n$. It is possible to express this statement via sum: $2 + ...
1
vote
1answer
31 views

Dice, balls and boxes probability problem (conditional probability)

Problem Suppose there are two boxes $A$ and $B$ such that $A=\{\text{5 red balls and 3 white balls}\}$, $B=\{\text{1 red ball and 2 white balls}\}.$ A dice is thrown, if the result is $3$ or $6$, a ...
2
votes
1answer
43 views

Colored balls in three boxes (conditional probability problem)

Problem Suppose there are three boxes numbered with twenty balls in each of them. The first box contains twenty white balls; the second, fifteen, and the third,ten; the rest of the balls are black. ...
1
vote
1answer
56 views

Find all the compositions of two function. [closed]

I need to know that given two functions $f(x)=\frac{x-3}{x-2}$ and $g(x)=3-x$ in how many forms do I can compose these two functions, I have: $f \circ g, g\circ f, f\circ f, g\circ g, f\circ ...
2
votes
1answer
75 views

A possible incorrect application of Law of Large numbers

A friend left this teaser for me. He asked me to first compute: $$ \lim_{n \to \infty} \frac{\binom{2n}{n}}{2^{2n}}$$ Using Stirling's approximation (and another method), I got the answer as $0$. ...
0
votes
0answers
33 views

Sum of digits of numbers in a range

Given an integer N. For each pair of integers (L, R), where 1 ≤ L ≤ R ≤ N we can find the number of distinct digits that appear in the decimal representation of at least one of the numbers L L+1 ... ...
2
votes
2answers
28 views

MNTILE SPOJ Tiling patterns

We have tiles of size 2 * 1. We need to arrange the tiles to get the floor size of m * n. For ...
0
votes
1answer
81 views

Find if permutation is possible

Given a permutation of natural integers from 1 to N, inclusive. Initially, the permutation is 1, 2, 3, ..., N. We are also given M pairs of integers, where the i-th is (Li,Ri). In a single turn we ...
2
votes
1answer
48 views

Counting problem, given a finite field and number variables

Let $F_5= {0,1,2,3,4}$ the finite field with 5 elements and let $S=F_5[x_1, x_2, x_3, x_4, x_5, x_6, x_7]$ the ring of polynomials over the $F_5$ field with 7 variables. 1) How many monomials of ...
2
votes
2answers
67 views

Alternating sum of binomial coefficients is equal to zero [duplicate]

Prove without using induction that the following formula:$$\sum_{k=0}^n (-1)^k\binom{n}{k}=0$$ is valid for every $n\ge1$. Progress For each odd $n$ we can use the ...
1
vote
2answers
29 views

Ice cream combinatorics question

An ice cream shop sells ice creams in $5$ possible flavours: vanilla, chocolate, strawberry, mango and pineapple. How many combinations of $3$ scoops cone are possible? [note: repetition of flavours ...
0
votes
2answers
75 views

If bridges between islands collapse independently with probability $p$, what is the probability that islands remain connected?

This is a follow-up to Probability Question: Bridge problem. There are $n$ islands in the ocean. Each island is linked by a single bridge to each other island. The probability of each bridge ...
1
vote
1answer
45 views

Probability Question: Bridge problem

There are $n$ islands in the ocean. Each island is linked by a single bridge between each and every unique pair of islands to ensure no island is isolated from the others. The probability of each ...
1
vote
1answer
32 views

Probability formula related to distribution balls in boxes.

Problem Suppose there is a distribution of $N$ distinct balls in $n$ different boxes such that each ball has the same probability to be in any box. Let $A_i=\{\text{the i-th box is not empty}\}$. ...
2
votes
2answers
126 views

Numbers of ways to buy a dozen bagels of various types, and eat them

Three types of bagels: honey, blueberry, and sesame seed. Assume that bagels of each type are indistinguishable. (a) How many ways are there to buy a dozen bagels? $(3 + 12 - 1) \choose 12$ because ...
1
vote
1answer
25 views

Finding a set of pairs that “cover” all combinations of a larger set

Sorry for the probably-confusing title but I'm not too familiar with this area and don't know the right terminology. That makes searching for solutions hard too. The problem is relatively simple: ...
1
vote
1answer
57 views

Iterations of Pascal's Identity

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
8
votes
2answers
178 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
29 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 ...
0
votes
1answer
26 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 ...
0
votes
1answer
79 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 ...
1
vote
2answers
38 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 ...
5
votes
3answers
98 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 ...
3
votes
1answer
31 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
0
votes
1answer
35 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 ...
-3
votes
1answer
45 views

Possible Numbers formed? [closed]

6-digit numbers formed using three 3's and three 4's?
-2
votes
1answer
42 views

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

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
38 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
2answers
98 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
1answer
62 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, ...
33
votes
5answers
4k 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
2answers
44 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 ...
5
votes
0answers
37 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
73 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 ...
0
votes
1answer
73 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 ...
2
votes
1answer
46 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
58 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 ...
0
votes
0answers
51 views

Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
2
votes
2answers
47 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 ...
0
votes
4answers
143 views

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

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